ニム

この項目では、ゲームについて説明しています。その他のニムについては「ニム (曖昧さ回避)」をご覧ください。

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

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

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

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

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

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

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

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

コインの山の数を n とし、各山のコインの枚数を A₁, …, A_n とする。

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

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

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

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

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

${\displaystyle {\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：${\displaystyle S=0}$ のとき、任意の操作について ${\displaystyle T\neq 0}$ である。

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

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

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

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

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

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

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

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

である。

i = 1 のときは、

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

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

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

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

故に、必勝形 (A₁, …, A_n) は

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

に限られる。//

• 不偏ゲーム
• ニム和
• 映画『去年マリエンバートで』 - 作中でニムが重要な役割を担う

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

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

• 表示
• 編集