RSS

  

RSS

パズル


パ：サッカー２・５問題

  • いわいまさか
  • at 2014/7/18 18:59:57

問題サッカー２・５
　サッカーで１１人いて
　背番号が１～１１番までついている。
　背番号１の人からパスをつないでいって、
　全員に１回ずつボールがまわって
　最終的に背番号１１の人がゴールした。
　全部で１０回あるパスのどれもが、
　背番号の差で２か５になっていた。
　さて、どんなパスまわしだったでしょうか？

　答えは唯一解。
　いかがでしょうか？

＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃

これをSCIPで解いてみようということで。

最初、手で入力文を書いていたけれど、やっぱ無理だと思い、C#で書くことにした。

パス（方向も考えて）があったかなかったを表す変数

x0103
  1:背番号１の人から背番号2の人へのパスがあった。（方向あり）
　0:なかった

x0503
  1:背番号5の人から背番号3の人へのパスがあった。（方向あり）
　0:なかった

入るパス
　背番号1に入るパスは0本なので
　   x0301+x0603=0
　背番号３に入るパスは１本なので
 　　x0103+x0503+x0803=1
　他の人もいっしょ

出るパス
　背番号3から出るパスは1本なので
　　 x0301+x0305+x0308=1
　他の人もいっしょ

　背番号11から出るパスは0本なので
　　 x1106+x1109=0

**********************************
でだいたい答えが出るのだが。

１番スタートから１１番ゴールは成り立ってるけど
それの中に入らないでパス回しをしているやつが出てきちゃう場合があって。

例えば、実際に出たまちがった解は
　1->6->4->2->7->9->11　　3⇔5
　１から11までパス回しうまくいってるけど、
　まてよ3と5はパス練習してるだけじゃん。という。

　「送られたきた人には返してはいけない」というルールを追加しても、
　３人でぐるぐる回されるとやっぱりだめなので。

**********************************
　ループ防止の方策

今回、途中でのループ防止のために入れた手は、
「その人が何番目の人かわかるようにして、
11人目が背番号11になるようにする」

その人が何人目の選手かを表す変数を導入して
v1=1      (背番号１の人は１番目の選手）
v11=11   (背番号11の人は11番目の選手）

v2(背番号２の人は何番目の選手か）
v3（背番号３の人は何番目の選手か）
・・・
v10
は未定。

そして、出てくるパスの候補全部に対して
背番号３から背番号５にパスがあったとしたら
背番号５は何人目かといういと背番号３が何人目だったかに
１を足せばよい。

　 if(x0305)
　 {
  　 v05 = v03+1
 　}else{
   　そうじゃないかも
 　}
　を書いてあげるといい。

不等式で、「そうじゃない」というところを書くと
なんか必死な感じになるが、

d0305 = v05-v03  
d0305   <=    100 * x0305 -  99
d0305   >=  -100 * x0305 + 101

で一応できた。

パスをつなぐところは「入るパス、出るパス」で書いてあるので、
何人目かしっかり数えてやると、ちゃんと１１人はまってないと
計算が合わなくなるというしかけ。

scip用の入力テキストファイル
1to11.lp.txt

ループ封じのこの書き方は、（他の書き方は、まだわからないが）
人数が11人から22人に増えたときに、
問題テキストの増え方が、倍程度（リニア）なのがリーズナブル。
2乗で増えていかない。

scipにかけると最初に出るこたえは、
 x0103
 x0207
 x0305
 x0402
 x0510
 x0604
 x0709
 x0806
 x0911
 x1008
がＯＮ。
パス回しで　1->3->5->10->8->6->4->2->7->9->11。

もとの問題分のSubjectに
１番目の答えと同じ答えが出ないように
 x0103+x0207+x0305+x0402+x0510+x0604+x0709+x0806+x0911+x1008<=9
を加えて
scipにかけると
解なしになる

なので唯一解。


  • コメント (2)
  • トラックバック (0)
トラックバックURL :
http://www.iwai-masaka.jp/tb.cgi/56104

コメントを書く


コメント

面白そうなので、考えてみた。
時計版から12時を除いて、2違いと5違いを結ぶと、4-2-7と8-10-5の繋がりは確定する。唯一解があることから、対称なルートを探すと、比較的容易に解にたどり着けた。

時計版は対称解がイメージしやすい！