id:yshl:20061018:1161168055 の棒取りゲームについて必勝法を考えてみる。

三山崩しの必勝法や棒取りゲームの説明を見てしまったので自力とは言えない。紹介してもらった本は読んでませんが。

A:全ての棒が 1 本ずつ孤立している時

互いに 1 本ずつ取り合っていくしかない。

• 奇数個の時は必敗
• 偶数個の時は必勝

B:棒が 2 本以上連続しているカタマリが 1 組、1 本孤立した棒が n (=0,1,2,...) 個ある時は必勝

先手は 1 本孤立した棒だけが奇数個残るように取ると A の状態になるので勝ち。

棒が 2 本以上連続しているカタマリが 2 組以上ある時

必勝、必敗状態の判定は三山崩しとほぼ同じ。
連続してならんでいる棒の数を 2 進数で表し、各桁の 1 の数を数える。全ての桁で偶数個の 1 がある場合を C、奇数個のものがある場合を D とする。
例えば

3  0  1  1
5  1  0  1
7  1  1  1



















-









 2個2個3個

は 1 の位に 1 が 3 個あるので D

3  0  1  1
5  1  0  1
6  1  1  0



















-









 2個2個2個

は 1,2,4 の位に 1 が 2 個ずつですべて偶数なので C
C からは D か B の状態にしか移れず、D からは必ず C の状態に移れるので、C は必敗状態、D は必勝状態である。

C からどのように棒を取っても B か D の状態に移る

棒が 2 本以上連続しているカタマリが 2 組以上あるので、棒を取った後のカタマリの数は 1 組以上ある。

残ったカタマリが 1 組の場合

B の状態に移っている。

残ったカタマリが 2 組以上ある場合

q 個棒が連続して並んでいる列の r+1 番目から q-s 番目の棒を取ったとする。取った後は r 個と s 個棒が連続した状態ができる。q、r、s の関係は 1≦r+1≦q-s≦q より、0<r、0<s、r+s+1≦q となる。
もし棒を取った後も各位の 1 の数が全て偶数だとすると、

• q を 2 進数で表した時に 1 になっている桁は r と s のどちらかが 1。
• q を 2 進数で表した時に 0 になっている桁は r と s が両方とも 0 または 1。

より、q≦r+s という関係になる。これは r+s+1≦q と矛盾。
よって棒を取った後は、いずれかの位の 1 の数が奇数になっている。つまり D の状態に移っている。

D から適切に連続した棒を取れば C の状態にすることができる

1 が奇数個ある最大桁が p の位とする。p の位が 1 になっている数を一つとり、q とする。q を 2 進数で表し、1 が奇数個ある桁の 1 と 0 を反転させた数を r とする。q を r に変えれば全ての桁で 1 の数が偶数になる。
q と r を比較すると、q の p の位の数は 1、r の p の位の数は 0 なので、q>r である。よって、 q から q-r を引けば q を r に変えることができる。
よって q 個棒が連続したカタマリの端から q-r 個棒を取ると、C の状態にすることができる。

棒を取った後でも 2 本以上連続しているカタマリが 2 組以上あることの確認

• 棒が 2 本以上連続しているカタマリが 3 組以上ある場合、どのように棒を取ってもカタマリは 2 組以上残る。
• 2 本以上連続しているカタマリが 2 組ある D 状態から、上のような方法で棒を取るとする。
  • 1 本孤立した棒を取る場合はカタマリは 2 組残る。
  • カタマリから棒を取る場合。2 本以上連続しているカタマリが 2 組で後は 1 本孤立した棒である時、棒の数を 2 進数で表すと、カタマリは 2 の位以上に 1 になっている桁があり、孤立した棒は 1 の位にしか 1 がない。そこで、棒を取らない方のカタマリの 2 の位以上にある 1 になっている桁に着目する。上の取り方で棒を取ると、取った後のカタマリの着目している桁は 1 になっている。よって棒を取った後のカタマリも 2 本以上連続している。