*Nim [#e7625e8d]

このページは競技プログラミングに興味のある方向けにNimを簡単に説明するページです

**Nimって何？ [#k4588ba5]

複数の山に積まれた石を順番に取り合って、最後の1個をとったプレイヤーが勝ちというゲームです~
このページで扱うNimのルールは以下の通りとします~
1.2人のプレイヤーで行う~
2.1つ以上の山が存在し、それぞれに1つ以上の石が積まれている~
3.石を取るプレイヤーは1つの山を選択し、そこから1つ以上の石をとる(全てとってもよい)~
4.プレイヤーが石を取ったら、石を取るプレイヤーが変更する~
5.最後の1個をとったプレイヤーの勝利とする(山に2個以上石があってもよい)~
(要するに、山から石を取れなくなったら負けということです)~

**必勝法はあるの？ [#x33c5e08]

あります。初期状態でどちらのプレイヤーが勝つかが決定されます

**どちらのプレイヤーが勝つかはどうやってわかるの？ [#g419eeb0]

初期状態の各山の石の数のxorをとり、それが0で無ければ先手必勝、0であれば後手必勝です~
具体的には山が3つあったとして各石の数が(5, 8, 9)の時は先手必勝、(1, 8, 9)の時は後手必勝です~

**必勝法はどういう手法？ [#l795eca6]
自分の手番で、各山の石の数のxorが0でない場合はxorが0になるように石を取ることを繰り返します~
これだけです~

**本当に？ [#t5d2a0d0]

本当です~

**証明してください。 [#lc3057e1]

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をとります。そして、「1である桁の中で最も大きい桁」を探し、その桁が1である山を探します(そのような山は必ず1つ以上あることは自明です)~
その山から適当に石をとり、「当該桁以下の値と同じになるように」石を取ります~
その山から適当に石をとり、「当該桁以下の値がxorの値と同じになるように」石を取ります~
そのような石の取り方があることは自明です~
したがって、xorを0にする取り方が必ず存在することになります~

**Nimの必勝法が競技プログラミングと関係あるの？ [#r254d119]

[[Grundy数]]をチェック！！！~
トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS