M 個の石の山と N 個の石の山がある。
二人で交互に一度ずつ石を取っていく。
片方の山から石を取るか、或いは両方の山から同数ずつ石を取れ、
最後の石を取ったほうが負けとなる。
後手必勝となるのはどのような場合か?
M〜Nがある数値の時
M〜Nって何?M-Nなら分かるが。
MとNで大きい方から小さい方を引く
違う。(0,1)は後手必勝なので、
(M,M+1) (M, 1) (1, M)但し M ≧ 1 は先手必勝。
そうすると(2,2)はそこからどのような手をとっても
次の手番に先手必勝の状態にしかならないので後手必勝。なので
(M+2, M+2) (M+2, 2) (2, M+2)は先手必勝。
そうすると(3, 5) (5. 3)はそこからどのような手をとっても
次の手番に先手必勝の状態にしかならないので後手必勝。なので(以下略
543 :
132人目の素数さん:2008/09/08(月) 23:20:18
一応ageて宣伝してみよう
N, M ≦ 100 の範囲で後手必勝になるものの一覧:
(0,1) (1,0) (2,2) (3,5) (4,7) (5,3) (6,10) (7,4) (8,13) (9,15)
(10,6) (11,18) (12,20) (13,8) (14,23) (15,9) (16,26) (17,28) (18,11) (19,31)
(20,12) (21,34) (22,36) (23,14) (24,39) (25,41) (26,16) (27,44) (28,17) (29,47)
(30,49) (31,19) (32,52) (33,54) (34,21) (35,57) (36,22) (37,60) (38,62) (39,24)
(40,65) (41,25) (42,68) (43,70) (44,27) (45,73) (46,75) (47,29) (48,78) (49,30) (50,81) (51,83) (52,32) (53,86) (54,33) (55,89) (56,91) (57,35) (58,94) (59,96)
(60,37) (61,99) (62,38) (65,40) (68,42) (70,43) (73,45) (75,46) (78,48) (81,50)
(83,51) (86,53) (89,55) (91,56) (94,58) (96,59) (99,61)
545 :
544:2008/09/09(火) 04:12:19
× ≦ 100
○ < 100
546 :
132人目の素数さん:2008/09/09(火) 08:41:54
お、頑張ったw
で比とかを取って見れば大体一定値になるのではないか?と
予想が付くよね。でそれを証明。
最終局免から帰納法でやってみようか
548 :
132人目の素数さん:2008/09/10(水) 01:46:51
答えだけ書いとくと、
a = (-1 + √5)/2 = 1.61803398874989484820458683436564 = (-1 + √5)/2
(黄金比の大きいほう)、[ ]をガウス記号(整数部分)として
(0,1),(2,2),
([na], [na] + n)及びその逆のときに後手必勝、その他のとき先手必勝となる。