ニム（複数山の石取りゲーム）の必勝法
更新
ニム，山崩しゲーム，石取りゲームなどと呼ばれるゲームについて。ニムには2進法を用いた必勝法があります。
ニムのルールと例
ニムのルールと例
ニムにはいろいろなバージョンがあるようですが，今回解説するのは以下のルールです。
- 二人で行うゲーム。
- いくつかの山にいくつかの石がある。
- プレーヤーは交互に石を取っていく。このとき同時に取れるのは同じ山の石のみ。1回で1個以上最大何個でも取れる。
- 最後の石を取った方が勝ち。
以下では山の石の数を並べて などと表します。例えば は石の数が3の山，5の山，7の山が1つずつある状況です。また，プレーヤーを とします。
からスタートする。
が一つ目の山から2つ取る：残り
が三つ目の山から7つ全部取る：残り
が二つ目の山から4つ取る：残り
が二つ目の山から1つ取る：残り
が最後の石をとって勝利
必勝形について
必勝形について
ニムの必勝法について説明するための準備として「必勝形」なるものを定義します。
以下の状態を「必勝形」と言うことにします：
各山の石の数を2進数で表したとき，各桁の和が全て偶数である状態
（各桁の排他的論理和が であるような状態）
は2進数で表すと，
となる。各桁を足し算すると （排他的論理和は ）となり全て偶数なので必勝形。
は2進数で表すと，
となる。各々を足し算すると （排他的論理和は ）となり奇数が存在するので必勝形でない。
排他的論理和 のことを の ニム和と言ったりもします。
ちなみに，山が二つのときは，
が必勝形 となります。
確認してみてください。
ニムの必勝法の概略
ニムの必勝法の概略
ニムには「必勝法」が存在します。 自分の手番終了後に必勝形に持っていけば勝てるというものです。
※「必勝形」と言うとその状態で回ってきた方が有利っぽいので本当は「必敗形」と呼ぶべきかもしれませんが説明の都合上，ご容赦下さいm(__)m
スタートが「必勝形でない状態」ならば以下のようにすることで先手が勝てます。
スタートが「必勝形」なら立場が逆転するので後手が勝てます。
-
「必勝形でない状態」からうまく石を取れば「必勝形」になるので自分の手番終了後は常に「必勝形」になる。
-
「必勝形」からどのように石を取っても「必勝形でない状態」になるので相手の手番終了後は常に「必勝形でない状態」になる。
-
石がない状態（終了状態）は「必勝形」なので，終了状態は自分の手番終了後に来るはず！
3は自明ですが，1，2でうまくいく（赤字部分が正しい）ことは証明しなければなりません。とは言っても両方ともけっこう簡単です。
必勝法であることの証明
必勝法であることの証明
1について：
「全ての山のニム和」において である桁を反転させるような石の除き方をしたい。それは， ニム和の最高位が である山 を選ぶことで実現できる。
のとき。
は二進法で， であり，ニム和は となる。よって，１桁目と２桁目を反転させるような石の除き方をすればよい。
どの山から何個石を除くか？
ニム和の最高位は２桁目なので，２桁目が である山を選ぶ。つまり「 」の山（石の数が つの山）を選ぶ。
反転させたい桁（１桁目と２桁目）を反転させると になる。つまり，この山の石の数を 個にすればOK。
まとめると， の山の石を 個にすることで必勝形にできる。
（ニム和の最高位が である山を選んでいるので，反転させた後の数 がもともとの石の数より小さくなる。すなわち，石を除くことで山 の石の数を必ず 個にできる。）
2について：（全体のうち残りはそのままで つだけ値を変えるとどこかの桁の排他的論理和は必ず変わるので）どのように石を取ってもニム和は変化してしまいます。そのため必勝形（=ニム和が である状態）からどのように石を取っても「必勝形でない状態」になります。
※頭脳王で登場した考察ゲームは最後の石をとった人が負けというルールでした。ほとんど同様に必勝法が作れます。
友達とニムをやりたくなりますが，実戦で毎回2進数の和をカリカリ計算するのはなんかカッコ悪いですね。
Tag:難しめの数学雑学・ネタまとめ
