nim
math次のような2人で行うゲームをnimと言うらしい。そして、これには簡単な必勝戦略があるそうだ。
- 最初、小石が積まれた山が複数個ある
- 交互に、任意に1つの山を選び1個以上の石を取り除く
- 石がなくなるまで繰り返し、最後の石を取った方が勝ち
このゲームの状態は、山の数だけの整数で表現される。任意の状態が与えられたとき、先手必勝か後手必勝かを、以下の基準で判断できる。
各山の石の個数をs[1], s[2], .. , s[N]とすると、
先手必勝 ⇔ s[1] xor s[2] xor ... xor s[N] != 0
証明のポイント
s[1] xor s[2] xor ... xor s[N] != 0のとき、うまく行動を選べばs[1] xor s[2] xor ... xor s[N] = 0にできるs[1] xor s[2] xor ... xor s[N] = 0のとき、どう行動してもs[1] xor s[2] xor ... xor s[N] != 0になってしまう
1の行動の選び方
s[1] xor s[2] xor ... xor s[N]を計算し、最左の1を探す。その場所を右からpビット目とする。- 右からpビット目が1であるような数字を
s[i]から探す。 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について
すべての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が必ず残る）後手必勝状態ではない。
したがって現在考えている条件（後手必勝状態からスタートする）に適さないため考えなくて良い。