第15問の解答


1.問題

問題図
n個碁石並んでいます
次のルールで、2人碁石を交互に取っていきます。
  • 個数はあらかじめ分かっています。
  • 交互に1個か、または連続した2個碁石を取っていきます。
  • ルールA)最後に石を取ったほうが勝ちとします。
  • ルールB)最後に石を取ったほうが負けとします。

このゲームでは、先手後手とも最善の手をとっていくと、最初のの値によって
  ・先手必ず勝つ手順がある(先手必勝
  ・後手必ず勝つ手順がある(後手必勝
2通りに分かれます。

(1)ルールAでゲームをした場合、1≦n≦9のとき、
  後手必勝となるのはいくつといくつのときでしょうか?
(2)ルールBでゲームをした場合、1≦n≦9のとき、
  後手必勝となるのはいくつといくつのときでしょうか?

(参考)JavaScriptを用いてゲームができます。


2.解答例1(清川育男さん、ちゃめさん、サンデー毎日願望男さん、tomhさん、ありさのお父さん他)

(設問1)

結論からいうと、全ての場合で先手必勝になります。

先手の取る必勝手は次の通り。

参考図1

(設問2)

結論からいうと、1、4、9個後手必勝になります。

第14問の補足と同様にして帰納法で考えます。

残った碁石の状態を、連続した石の個数を大きい順に並べて、

参考図2

のように表すこととします。

下表で、青色先手必勝赤色後手必勝を表します。

各状態の上にマウスを置くと次の手を、
 先手必勝の場合は、後手必勝となるものを1手だけ、
 後手必勝の場合は、次の手(全て先手必勝)を全て
その手の判定結果を下の欄に表示します。

0 [0] -
1 [1] -
2 [2] [1,1]
3 [3] [2,1] [1,1,1]
4 [4] [3,1] [2,2] [2,1,1] [1,1,1,1]
5 [5] [4,1] [3,2] [3,1,1] [2,2,1] [2,1,1,1] 以下略
6 [6] [5,1] [4,2] [4,1,1] [3,3] [3,2,1] 以下略
7 [7] [6,1] [5,2] [4,3] 以下略
8 [8] [7,1] [6,2] [5,3] [4,4] 以下略
9 [9] 省略