面白い問題おしえて〜な 十四問目
M 個の石の山と N 個の石の山がある。
二人で交互に一度ずつ石を取っていく。
片方の山から石を取るか、或いは両方の山から同数ずつ石を取れ、
最後の石を取ったほうが負けとなる。
後手必勝となるのはどのような場合か？
二人で交互に一度ずつ石を取っていく。
片方の山から石を取るか、或いは両方の山から同数ずつ石を取れ、
最後の石を取ったほうが負けとなる。
後手必勝となるのはどのような場合か？
|
|
|
539 ：１３２人目の素数さん：2008/09/08(月) 16:13:22
M〜Nがある数値の時
540 ：１３２人目の素数さん：2008/09/08(月) 18:19:20
M〜Nって何？M-Nなら分かるが。
541 ：１３２人目の素数さん：2008/09/08(月) 20:48:16
MとNで大きい方から小さい方を引く
542 ：１３２人目の素数さん：2008/09/08(月) 23:17:32
違う。(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)はそこからどのような手をとっても
次の手番に先手必勝の状態にしかならないので後手必勝。なので（以下略
(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 ：１３２人目の素数さん：2008/09/08(月) 23:20:18
一応ageて宣伝してみよう
544 ：１３２人目の素数さん：2008/09/09(火) 04:10:32
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)
(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)
× ≦ 100
○ ＜ 100
○ ＜ 100
546 ：１３２人目の素数さん：2008/09/09(火) 08:41:54
お、頑張ったｗ
で比とかを取って見れば大体一定値になるのではないか？と
予想が付くよね。でそれを証明。
で比とかを取って見れば大体一定値になるのではないか？と
予想が付くよね。でそれを証明。
547 ：１３２人目の素数さん：2008/09/09(火) 10:06:06
最終局免から帰納法でやってみようか
548 ：１３２人目の素数さん：2008/09/10(水) 01:46:51
答えだけ書いとくと、
a = (-1 + √5)/2 = 1.61803398874989484820458683436564 = (-1 + √5)/2
（黄金比の大きいほう）、[ ]をガウス記号（整数部分）として
(0,1),(2,2),
([na], [na] + n)及びその逆のときに後手必勝、その他のとき先手必勝となる。
a = (-1 + √5)/2 = 1.61803398874989484820458683436564 = (-1 + √5)/2
（黄金比の大きいほう）、[ ]をガウス記号（整数部分）として
(0,1),(2,2),
([na], [na] + n)及びその逆のときに後手必勝、その他のとき先手必勝となる。