![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
このページは競技プログラミングに興味のある方向けにNimを簡単に説明するページです
複数の山に積まれた石を順番に取り合って、最後の1個をとったプレイヤーが勝ちというゲームです
このページで扱うNimのルールは以下の通りとします
1.2人のプレイヤーで行う
2.1つ以上の山が存在し、それぞれに1つ以上の石が積まれている
3.石を取るプレイヤーは1つの山を選択し、そこから1つ以上の石をとる(全てとってもよい)
4.プレイヤーが石を取ったら、石を取るプレイヤーが変更する
5.最後の1個をとったプレイヤーの勝利とする(山に2個以上石があってもよい)
(要するに、山から石を取れなくなったら負けということです)
あります。初期状態でどちらのプレイヤーが勝つかが決定されます
初期状態の各山の石の数のxorをとり、それが0で無ければ先手必勝、0であれば後手必勝です
具体的には山が3つあったとして各石の数が(5, 8, 9)の時は先手必勝、(1, 8, 9)の時は後手必勝です
自分の手番で、各山の石の数のxorが0でない場合はxorが0になるように石を取ることを繰り返します
これだけです
本当です
Nimは「山から石がなくなった状態を相手に押し付けたら勝ち」というゲームと言い換えることが出来ます
山に石が無い状態は各山の石の数のxorが0であることは自明です。よって、以下の2点を証明すればよいことになります
1.各山の石の数のxorが0であるとき、どのようなとり方をしても各山の石の数のxorを0にすることが出来ない
2.各山の石の数のxorが0でない時、各山の石の数のxorを0にするとり方が必ず存在する
補足すると、「各山の石の数のxorが0の状態を相手に押し付け続ければ、いつか石の数が0個の状態が来るから自分が勝つ」ということです
まず、1の証明です
各山の石の数のxorが0であるということは、「各桁に存在する1の数が偶数個である」ということです
山から石を取るという行為は「いずれかの山に相当する数値のビットを少なくとも一つ以上反転させる」ことに等しいです
反転したビットの桁に存在する1の数は必ず奇数になるため必ずxorが0でなくなります
したがって、各山の石の数のxorが0であるときどのようなとり方をしても各山の石の数のxorを0にすることは出来ないということになります
次に、2の証明です
まず山を一つ選び、それ以外の各山の石の数のxorをとります。そして、「選んだ山の石の数＞それ以外の各山の石の数のxor」となるかどうかを判定します
この条件を満たす山は少なくとも一つ以上存在しています(この部分の証明は省略)
そのような条件の山を見つけたら、選んだ山から(選んだ山の石の数 - それ以外の各山の石の数のxor)個の石を取れば残った各山の石の数のxorが0になります
Grundy数をチェック！！！
