ニム

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

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

ゲームのルール

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

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

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

必勝法

山が2つの場合

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

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

テンプレート:Math2 ならば、後手が上記を実行すると必ず勝つ。

一般の場合

コインの山の数をテンプレート:Mvar とし、各山のコインの枚数をテンプレート:Math2 とする。

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

テンプレート:Math2 のときは必ずテンプレート:Math2 にでき、すると次に相手はテンプレート:Math2 にせざるを得なくなる。これを繰り返すと必ず勝てる。テンプレート:Math2 ならば先手必勝、テンプレート:Math2 ならば後手必勝にできる。

証明

先手がテンプレート:Mvar のテンプレート:Mvar からコインを取り除いてテンプレート:Mvar になったとする。

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

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

\begin{matrix} T & = ⨁_{i; i \neq k} A_{i} \oplus B_{k} \\ = ⨁_{i; i \neq k} A_{i} \oplus (A_{k} \oplus A_{k}) \oplus B_{k} \\ = S \oplus A_{k} \oplus B_{k} \end{matrix}

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

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

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

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

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

逆形

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

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

テンプレート:Mvar個の山の内、コインが2個以上であるものの個数をテンプレート:Mvar とする。

テンプレート:Math2 である後手必勝形は

1個だけの山が奇数個のみ。… (テンプレート:EquationRef)

である。

テンプレート:Math2 のときは、

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

故にテンプレート:Math2 のときは必敗形である。

テンプレート:Math2 のときは、プレイヤーがニム和を 0 にし続ければ、相手はテンプレート:Math2 にせざるを得なくなる。

（なぜなら、テンプレート:Math2 のときのニム和は 0 でないから。）

故に、必勝形テンプレート:Math2 は

テンプレート:EquationNote または
2個以上の山が2個以上かつ、ニム和が 0 であるもの。

に限られる。//

脚注

テンプレート:Reflist

外部リンク

テンプレート:高校数学の美しい物語

テンプレート:Game-stub

↑ Richard J. Nowakowski (Dalhousie University) テンプレート:Wayback 2009年1月24日。p.4
↑ テンプレート:Nowiki（クラスメソッド株式会社）2018.03.23
↑ テンプレート:Nowiki

[1] Richard J. Nowakowski (Dalhousie University) テンプレート:Wayback 2009年1月24日。p.4

[2] テンプレート:Nowiki（クラスメソッド株式会社）2018.03.23

[3] テンプレート:Nowiki

[1]

[2]

[3]

ニム

目次

ゲームのルール

必勝法

山が2つの場合

一般の場合

証明

逆形

脚注

関連項目

外部リンク

ナビゲーションメニュー

ニム

ゲームのルール

必勝法

山が2つの場合

一般の場合

証明

逆形

脚注

関連項目

外部リンク

ナビゲーション メニュー

検索

ナビゲーションメニュー