[石取りゲーム]碁石がn個(ただしn≧1)あります。2人でこの碁石を交互に取っていくゲームをします。ルールは次の通りです。最初からn個全ての碁石を取ることは出来ない。1個以上取らなくてはならない。前の人が取った個数の2倍より多くの碁石は取れない。最後の碁石を取ったほうが勝ち。2人は、それぞれ最善の手を尽くす。このとき、後手必勝となるのはnがいくつのときでしょうか?nが小さい方から5つ答えて下さい。2.解答例1碁石の数がn個のとき、前の人が何個取ったか(mとします)によって条件が変わってきますので、それぞれ考える必要があります。下表では、各(n、m)に対してSは先手必勝、Gは後手必勝の場合を示しています。m≧1のときを考えます。n≦2mなら先手は全ての碁石を取ることが出来るので先手必勝。(上記灰色の部分)以下は、水色の部分を考えます。(n、m)=(3、1)のとき:1個とれば(2、1)、2個とれば(1、2)の状態になるが、いづれも次の先手(すなわち後手)が必勝形なので、後手必勝。(n、m)=(4、1)のとき:1個とれば(3、1)の後手(すなわち現在の先手)必勝状態になるので先手必勝。(n、m)=(5、1)、(5、2)のとき:1個とれば(4、1)、2個とれば(3、2)、3個((5、1)のときを除く)とれば(2、3)の状態になるが、いづれも次の先手必勝形なので、後手必勝。(n、m)=(6、1)、(6、2)のとき:1個とれば(5、1)の後手必勝形になるので先手必勝。(n、m)=(7、1)、(7、2)、(7、3)のとき:2個とれば(5、2)の後手必勝形になるので先手必勝。(n、m)=(8、1)、(8、2)、(8、3)のとき:次は(7、1)、(6、2)、(5、3)、(4、4)、(3、5)、(2、6)のいづれかの状態になるが、どれも先手必勝形になるので、後手必勝。(n、m)=(9、1)、(9、2)、(9、3)、(9、4)のとき:1個とれば(8、1)の後手必勝形になるので先手必勝。(n、m)=(10、1)、(10、2)、(10、3)、(10、4)のとき:2個とれば(8、2)の後手必勝形になるので先手必勝。(n、m)=(11、2)、(11、3)、(11、4)、(11、5)のとき:3個とれば(8、3)の後手必勝形になるので先手必勝。(n、m)=(11、1)のとき:3個は取れないので、次は(10、1)、(10、2)のいづれかの状態になるが、どれも先手必勝形になるので、後手必勝。(n、m)=(12、1)、(12、2)、・・・、(12、5)のとき:1個とれば(11、1)の後手必勝形になるので先手必勝。(n、m)=(13、1)、(13、2)、・・・、(13、6)のとき:次は(12、1)、(11、2)、(10、3)、・・・、(1、12)のいづれかの状態になるが、どれも先手必勝形になるので、後手必勝。m=0の場合(すなわちゲーム開始時の先手番:紫色の部分)を考えます。n=2、3、5、8、13のとき:次の手は、どれも先手必勝形になるので、後手必勝。n=4、6、7、9、10、11、12、14のとき:次の手は、右上方向の対角線上にあるが、その中に後手必勝形が含まれるので先手必勝。答:2、3、5、8、13。