ニム

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

歴史的には、最初に必勝法が数学的に解決したゲームである^[1]。最善手を行うならば、どちらが勝つかは最初の個数の組で決まる（後述）。その必勝法と証明は組合せ論による。

ゲームのルール[編集]

有限個のコイン（石や豆でもよい）の山を有限個用意する。2人のプレイヤーが山からコインを好きな数ずつ交互に取り合っていく。

一度に取るコインは1つの山からとする。
回ごとに最低1個は取らなければいけないとする。

これを繰り返すと有限回で全てのコインがなくなるが、最後にコイン（複数でもよい）を取ったプレイヤーにより勝敗を決める。最後にコインを取った者を勝者とするルールは正規形と呼ばれている。

必勝法[編集]

山が2つの場合[編集]

特に山が2個の場合は、一般の場合よりも必勝法が簡単である。

山A, Bのコインの個数をそれぞれ $a, b$ とする。調べ上げていっても容易に類推されるように、後手必勝形は $a = b$ のときのみである。 $a \neq b$ ならば、先手が多い山から $a$ と $b$ の差だけコインを取ると、次に相手は $a \neq b$ にせざるを得なくなる。先手がこれを繰り返すと必ず勝つ。

$a = b$ ならば、後手が上記を実行すると必ず勝つ。

一般の場合[編集]

コインの山の数を $n$ とし、各山のコインの枚数を $A 1, \dots, A n$ とする。

$S=A_{1}\oplus \cdots \oplus A_{n}$ とおく。ただし、 $\oplus$ はビットごとの排他的論理和を表すものとする。

$S \neq 0$ のときは必ず $S = 0$ にでき、すると次に相手は $S \neq 0$ にせざるを得なくなる。これを繰り返すと必ず勝てる。 $S \neq 0$ ならば先手必勝、 $S = 0$ ならば後手必勝にできる。

証明[編集]

先手が $S$ の $A k$ からコインを取り除いて $B k$ になったとする。

T=A_{1}\oplus \cdots \oplus B_{k}\oplus \cdots \oplus A_{n}

とおく。排他的論理和は交換法則、結合法則および $X\oplus X=0$ を満たすため、次の等式が成り立つ。

{\begin{aligned}T&=\textstyle \bigoplus \limits _{i;i\neq k}A_{i}\oplus B_{k}\\&=\textstyle \bigoplus \limits _{i;i\neq k}A_{i}\oplus (A_{k}\oplus A_{k})\oplus B_{k}\\&=S\oplus A_{k}\oplus B_{k}\end{aligned}}

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

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

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

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

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

逆形[編集]

最後にコインを取った者を負けとするルールは「逆形」^[2]「逆型」「双対ゲーム」などと呼ばれている。一般に、組合せゲームの正規形と逆形では、プレイヤーが逆のことに最善を尽くすため、正規形の後手必勝形が逆形の後手必敗形とはなっていない。

実際に逆形ニムにおいては、必勝形、必勝法は次の通りである^[3]：

$n$ 個の山の内、コインが2個以上であるものの個数を $i$ とする。

$i = 0$ である後手必勝形は

1個だけの山が奇数個のみ。… (1)

である。

$i = 1$ のときは、

1個だけの山が奇数個なら、2個以上の山を空にすることで必勝形にできる。
1個だけの山が偶数個なら、2個以上の山を1個にすることで必勝形にできる。

故に $i = 1$ のときは必敗形である。

$i \geq 2$ のときは、プレイヤーがニム和を 0 にし続ければ、相手は $i = 1$ にせざるを得なくなる。

（なぜなら、 $i = 1$ のときのニム和は 0 でないから。）

故に、必勝形 $(A 1, \dots, A n)$ は

(1) または
2個以上の山が2個以上かつ、ニム和が 0 であるもの。

に限られる。//

脚注[編集]

^ Richard J. Nowakowski (Dalhousie University) The History of Combinatorial Game Theory - ウェイバックマシン（2012年1月18日アーカイブ分） 2009年1月24日。p.4
^ [組み合わせゲーム理論] 組み合わせゲームとゲーム木について | DevelopersIO（クラスメソッド株式会社）2018.03.23
^ 石取りゲーム(Nim) [いかたこのたこつぼ]

外部リンク[編集]

『ニム（複数山の石取りゲーム）の必勝法』 - 高校数学の美しい物語

この項目は、ゲームに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。

[1] Richard J. Nowakowski (Dalhousie University) The History of Combinatorial Game Theory - ウェイバックマシン（2012年1月18日アーカイブ分） 2009年1月24日。p.4

[2] [組み合わせゲーム理論] 組み合わせゲームとゲーム木について | DevelopersIO（クラスメソッド株式会社）2018.03.23

[3] 石取りゲーム(Nim) [いかたこのたこつぼ]

[1]

[2]

[3]