Nim について少しメモ

東京工業大学プログラミングコンテスト2015 の M - コインと無向グラフ を解こうとして Nim かなーと思って Nim について調べました。
今度はちゃんと Nim について理解できた気がしたのでざっくり書いていきます。

問題設定とかは以下の記事を参考にします。d.hatena.ne.jp

記事に書いてあるとおり, n1 ^ n2 ^ ... nk = 0 の時負けで, それ以外の時勝ちになります。これをちゃんと証明してみます。

まず, n1 = n2 = ... = nk = 0 のとき, xor は 0 になりますが, この時は確かにコインを取ることが出来ないので負けです。
あとは, それ以外の場合に 「負けの状態(n1^n2^...^nk = 0) からは勝ちの状態(n1^n2^...^nk!=0) に移動することしかできない」こと及び「勝ちの状態からは負けの状態に移動できる手が存在する」ことを示せば良いです。

負けの状態から勝ちの状態に移動できることは自明です。ni の値を変化させると, 元の ni と bit の値がずれるので, bit が変化した部分だけ 0 より大きくなります。よって, 勝ちの状態になりますね。

勝ちの状態から負けの状態になる手が存在するのはこれに比べると自明ではないです。
n1^n2^...^nk = x であるとしましょう。x は 0 でない整数なので, bit のどこかに必ず 1 があります。これらのうち, 一番上の桁の bit が m 桁目にあるとします。
ちょっとわかりにくいので例を挙げると, 例えば k = 3, n1 = 1, n2 = 2, n3 = 4 とすると, n1^n2^n3 = 7 です。7 は bit で表すと 111 なので, bit が立っている桁のうち, 一番大きい桁は 2 桁目(0, 1, 2 桁目の bit が立っている)ですね。よって m = 2 です。

さて, このように bit が立っている場合, 2^m (ここでの ^ は xor ではなくべき乗です)以上の値のコインがある皿が存在するはずです。そうしないと m bit 目の桁が立つわけが無いですから。そこで, 2^m 以上のコインがある皿を一つ選び, その皿から x - 2^m のコインが残るようにすれば, 残ったコインの状態 n1^n2^...^nk = 0 となります。x-2^m が「x から m bit 目の 1 を取った値」であることを考えればこれは明らかでしょう。また, x < 2^(m+1) より, x-2^m < 2^m なので, 選んだ皿からコインは必ず 1 枚以上減ります。
さっきの例を使うと, 2^m = 4 枚以上コインのある皿が存在するはずですが, 実際にコインが 4 枚ある皿がありますね。ここから, x-2^m = 7-4 = 3 枚のコインが残るようにコインを取る(つまり 1 枚だけコインを取る)と, n1^n2^n3 = 1^2^3 = 0 となり, 確かに負けの状態に遷移してくれました。

今まで謎の魔力として扱ってきた Nim でしたがこれでちゃんと理解できた気がします。