次のような2人で行うゲームをnimと言うらしい。そして、これには簡単な必勝戦略があるそうだ。

  • 最初、小石が積まれた山が複数個ある
  • 交互に、任意に1つの山を選び1個以上の石を取り除く
  • 石がなくなるまで繰り返し、最後の石を取った方が勝ち

このゲームの状態は、山の数だけの整数で表現される。任意の状態が与えられたとき、先手必勝か後手必勝かを、以下の基準で判断できる。

各山の石の個数をs[1], s[2], .. , s[N]とすると、

先手必勝 ⇔ s[1] xor s[2] xor ... xor s[N] != 0

証明のポイント

  1. s[1] xor s[2] xor ... xor s[N] != 0 のとき、うまく行動を選べばs[1] xor s[2] xor ... xor s[N] = 0にできる
  2. s[1] xor s[2] xor ... xor s[N] = 0 のとき、どう行動してもs[1] xor s[2] xor ... xor s[N] != 0になってしまう

1の行動の選び方

  1. s[1] xor s[2] xor ... xor s[N]を計算し、最左の1を探す。その場所を右からpビット目とする。
  2. 右からpビット目が1であるような数字をs[i]から探す。
  3. s[i]の右から1,2,..,pビット目を、全体のxorが0になるように選ぶ。このとき、pビット目は必ず1→0に反転する。また、それにより、得られた数字は元のs[i]より真に小さくなることが分かる。 i番目の山の石の個数を、このようにして得られた値になるように石を取り出せば、条件を満たす。

2の行動について

どのやまから石を取り除いても、その山の数字のどこかのビットは必ず反転する。その結果、全体のxorは0ではなくなる。

必勝法

上記のように先手がxor = 0の局面を後手に渡し続ける限り、後手の行動後のxorは0にはなり得ない。最後の石を取り除いた結果のxorは0なので、後手が最後の石を取り除くことは不可能である。

逆のパターン

ルールを反転して、「最後の石を取ったほうが負け」とするとどうなるかを考える。以下では、最後の石を取ったほうが・・「勝ち」のルールを順ルール、「負け」のルールを逆ルールと呼ぶ。

すぐに勝敗の判定できる状態として、すべてのiについてs[i] <= 1という状態を考える。この場合は1の個数が偶数なら先手必勝で奇数なら後手必勝となる。実は、それ以外の場合(つまり、少なくとも1つの山に2個以上の石がある)場合には、 順ルールと同様にs[i]のxor != 0なら先手必勝、それ以外では後手必勝となる。

これを示すには、次の2つを言えば良い。

  1. 先手必勝状態からは、適切に行動を選べば後手必勝状態を作れる
  2. 後手必勝状態からは、どうあがいても先手必勝状態しか作れない

1について

すべてのiについてs[i]<=1の場合は自明。よって、少なくとも1つのiについてs[i]>1 となるiがある状態を考える。 まず、先手必勝状態から順ルールと同様に行動することを考える。その結果、s[i]>1なる山ができる場合は、そのままで良い。 すべてのiについてs[i]<=1となる場合、xorが0という条件を満たしているはずなのでs[i]=1となる山の個数は偶数個である。 ここでs[i]=1となる山が0個になってしまう場合は、順ルールでの行動よりも1つ少ない石を取れば、石1個の山が1つだけという後手必勝状態を作れる。 s[i]=1となる山が2個以上ある場合は、順ルールでの行動よりも1つ余計に石を取れば、石1個の山が奇数個という後手必勝状態を作れる。

2について

1の山が奇数個という状態からは、1の山が偶数個、という状態(=先手必勝)しか作れない。

よって、s[i]のxorが0で少なくとも1つのiについてs[i] > 1のときを考える。 後手必勝の状態を作るには、奇数個の1の山だけを残すか、s[i]のxorを0に保つかのどちらかしかないが、後者は不可能である。 奇数個の1の山だけを残すためには、1つの山だけが2個以上で、残りは0個か1個という状態を与えられていなければならない。 しかし、そのよう状態はs[i]のxor != 0であり(右から2ビット目より大きいところに1が必ず残る)後手必勝状態ではない。 したがって現在考えている条件(後手必勝状態からスタートする)に適さないため考えなくて良い。

参考サイト

  1. 高校数学の美しい物語
  2. 内藤久資 1999年度名古屋大学数学高階講座