ニム

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

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

ゲームのルール

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

●一度に取るコインは1つの山からとする。

●回ごとに最低1個は取らなければいけないとする。

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

必勝法

山が2つの場合

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

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

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

一般の場合

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

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

S ≠ 0 のときは 必ず S= 0 にでき、すると次に相手は S≠ 0 にせざるを得なくなる。これを繰り返すと必ず勝てる。S ≠ 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$  となる。

逆形

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

実際に逆形ニムにおいては、必勝形、必勝法は次の通りである‥

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 であるもの。

に限られる。//

関連項目

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

外部リンク

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