第101問の解答


1.問題 [石取りゲーム

 碁石n個(ただしn≧1)あります。
 2人でこの碁石を交互に取っていくゲームをします。
 ルールは次の通りです。
  • 最初からn個全ての碁石を取ることは出来ない。
  • 必ず1個以上取らなくてはならない。
  • 前の人が取った個数の2倍より多くの碁石は取れない。
  • 最後の碁石を取ったほうが勝ち
  • 2人は、それぞれ最善の手を尽くす

このとき、後手必勝となるのはいくつのときでしょうか?
小さい方から5つ答えて下さい。


2.解答例1

碁石の数がn個のとき、前の人が何個取ったか(とします)によって条件が変わってきますので、それぞれ考える必要があります。

下表では、各(n、m)に対して先手必勝後手必勝の場合を示しています。

参考図1

まず、すなわちm≧1のときを考えます。

さて、m=0の場合(すなわちゲーム開始時の先手番:紫色の部分)を考えます。

 

答:2、3、5、8、13

以上