ニム

ニム (nim) は、2人で行うレクリエーション数学ゲームの一つである。ルーツは古代中国からあるとされ、16世紀初めの西欧で基本ルールが完成したが、名前については、一般的に1901年にハーバード大学のチャールズ・L・バウトンによって名付けられたとされる。

このゲームの必勝法は、組合せ論による。組合せ論的には先手と後手どちらが勝つか、勝ちが保証されるためにはどのようにコインを取ればよいか、その勝利の戦略を決めることにある。

ゲームのルール[編集]

2人のプレイヤーがいくつかのコインの山からコインを取り合う。ゲームの目的は、最後のコインを取ることである（コインの代わりに石や豆を使ってもよい）。

まず、コインの山を複数準備する。山の数や各山のコインの枚数は（プレイヤー同士で合意すれば）自由に決めてよい。
2人のプレイヤーの順番は交互である。じゃんけん等で先手を決める。
各々のプレイヤーは自分の順番のとき、コインの山を1つ選んでその山から1枚以上のコインを取り去る（複数の山からコインを取ったり、コインを一枚も取らなかったりするのは反則である）。これが終わったら次のプレイヤーの手番になる。
すべての山のコインがなくなったとき、ゲームは終わりである。そして、最後のコイン（複数のときもある）を取ったときのプレイヤーが勝者である。

必勝法[編集]

山が二つの場合[編集]

特殊な場合として、2つのコインの山AとBでそれぞれの山のコインの数をa枚、b枚とする。このときの必勝法を考える。まずAとBの山のコインの数が異なるときを考える。先手は、AとBの山のコインの数が同じになるように、コインの数の多い方の山からコインを取る。そのあと、先手は自分の順番のとき、後手の取るのを真似ればよい。つまり、後手が片方の山からc枚コインを取ったとしたら、先手はもう一方の山から、同じ数のc枚だけコインを取ればよい。これが先手の必勝法である。

もしAとBの山の数が同じならば、先手の取るのを真似ることで後手が勝つことになる。

一般の場合[編集]

コインの山の数を $N$ とし、各山のコインの枚数を $A_{1},\,\dots ,\,A_{N}$ とする。

$S=A_{1}\oplus \cdots \oplus A_{N}$ とおき、 $S\neq 0$ ならば先手が必勝法を持ち、 $S=0$ ならば後手が必勝法を持つ。 $\oplus$ はビットごとの排他的論理和である。

ビットごとの排他的論理和が 0 になるようにコインを取る戦略が必勝法である。

証明[編集]

先手がコインを取り除いた後の各山のコインの枚数を $B_{1},\,\dots ,\,B_{N}$ とし、 $T=B_{1}\oplus \cdots \oplus B_{N}$ とする。コインが $k$ 番目の山から取り除かれるとき、 $A_{l}\oplus B_{l}=0\;(l\neq k)$ である。排他的論理和は結合法則と交換法則および $X\oplus X=0$ をみたすため、次の等式が成り立つ。

{\begin{aligned}T&=S\oplus S\oplus T\\&=S\oplus (A_{1}\oplus B_{1})\oplus \cdots \oplus (A_{n}\oplus B_{n})\\&=S\oplus A_{k}\oplus B_{k}\end{aligned}}

次の二つの補題から従う。

補題1: $S=0$ のとき、任意の操作について $T\neq 0$ である。

証明: $A_{k}\oplus B_{k}\neq 0$ であることから明らかである。

補題2: $S\neq 0$ のとき、ある操作について $T=0$ である。

証明: $S$ の 0 でないビットのうち最も桁の大きいものの位置を $d$ 番目とする。 $A_{k}$ の $d$ 番目のビットが 0 でないような $k$ を一つ選ぶ（このような $k$ は必ず存在する）。 $S\oplus A_{k}<A_{k}$ であるため、 $k$ 番目の山から何枚かのコインを取り除いて $B_{k}=S\oplus A_{k}$ 枚にすることができる。このとき、 $T=0$ となる。