ニム

ニム (nim) は、2人で行うレクリエーション数学ゲームの一つである。ルーツは古代中国からあるとされ、16世紀初めの西欧で基本ルールが完成したが、名前については、一般的に1901年にハーバード大学のチャールズ・L・バウトンによって名付けられたとされる。
このゲームの必勝法は、組合せ論による。組合せ論的には先手と後手どちらが勝つか、勝ちが保証されるためにはどのようにコインを取ればよいか、その勝利の戦略を決めることにある。
ゲームのルール.
2人のプレイヤーがいくつかのコインの山からコインを取り合う。ゲームの目的は、最後のコインを取ることである（コインの代わりに石や豆を使ってもよい）。
必勝法.
山が二つの場合.
特殊な場合として、2つのコインの山AとBでそれぞれの山のコインの数をa枚、b枚とする。このときの必勝法を考える。まずAとBの山のコインの数が異なるときを考える。先手は、AとBの山のコインの数が同じになるように、コインの数の多い方の山からコインを取る。そのあと、先手は自分の順番のとき、後手の取るのを真似ればよい。つまり、後手が片方の山からc枚コインを取ったとしたら、先手はもう一方の山から、同じ数のc枚だけコインを取ればよい。これが先手の必勝法である。
もしAとBの山の数が同じならば、先手の取るのを真似ることで後手が勝つことになる。
一般の場合.
コインの山の数を formula_1 とし、各山のコインの枚数を formula_2 とする。
formula_3 とおき、formula_4 ならば先手が必勝法を持ち、formula_5 ならば後手が必勝法を持つ。formula_6 はビットごとの排他的論理和である。
ビットごとの排他的論理和が 0 になるようにコインを取る戦略が必勝法である。
証明.
先手がコインを取り除いた後の各山のコインの枚数を formula_7 とし、formula_8 とする。コインが formula_9 番目の山から取り除かれるとき、formula_10 である。排他的論理和は結合法則と交換法則および formula_11 をみたすため、次の等式が成り立つ。
次の二つの補題から従う。
補題1: formula_13 のとき、任意の操作について formula_14 である。
"証明": formula_15 であることから明らかである。
補題2: formula_16 のとき、ある操作について formula_17 である。
"証明": formula_18 の 0 でないビットのうち最も桁の大きいものの位置を formula_19 番目とする。
formula_20 の formula_19 番目のビットが 0 でないような formula_9 を一つ選ぶ（このような formula_9 は必ず存在する）。
formula_24 であるため、formula_9 番目の山から何枚かのコインを取り除いて formula_26 枚にすることができる。
このとき、formula_17 となる。
双対ゲーム.
ニムの勝ち負けを反転させたゲームを、ニムの双対ゲームと呼ぶ。すなわち、双対ゲームはニムと同じルールでゲームが展開していくが、通常のニムと違い最後のコインを取った方が負けになる。
双対ゲームの必勝法はニムの必勝法を反転させたものになっていない。