Nimの必勝法

取り敢えず答えさえ分かっていればいくらでも証明できるものだなぁ、という感じ。

Nimとは、N個の整数列が与えられたときに、0ではない要素を一つ選び、好きなだけ小さくするという操作を交互にやって、最終的にN個すべてを0にしたプレイヤーが勝ち、という二人ゲーム。

で、すべての整数の排他的論理和が0になるような初期盤面であれば負けで、そうでなければ勝ち、というのがNimの判定。以下証明、のようなもの。

まず、終状態はすべての整数が0なので、直前の全整数の排他的論理和が0であるとすると、矛盾する。これは排他的論理和の定義から、a^b=0⇔a=bとなるため。(Nimではいずれかの整数を1以上小さくしないといけないため、a=0かつb>0であるので、次の状態で排他的論理和が0になることはない。)つまりあるプレイヤーが常に排他的論理和が0で渡されるならば、決して勝つことはできない、ということである。(b>0と、N個の整数の総和が有限であることより、このようなステップはいつか終わる。)

次に、0ではない排他的論理和を持つ時、排他的論理和が0になるようにする方法が必ず存在することを示せば良い。N個の整数の排他的論理和Aの1である最上位をXビット目とすると、少なくとも一つXビット目が1の数Bが存在する。後はBからA^Bを引いた数だけ引いてやれば、全体としての排他的論理和は(A^B^(B-(B-A^B)))=A^B^(A^B)=0になる。

ちなみにA^Bという操作は、BのXビット以下に対する反転操作であり、かつA^BのXビット目は必ず0になるので、A^BはBよりも必ず小さくなる。これはB-A^Bが1以上の整数であることを意味している。またAもBも正整数であることを前提にしているので、A^Bが負数になることもない。