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

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

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

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

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

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

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

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

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

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

コインの山の数を n とし、各山のコインの枚数を A1, …, An とする。

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

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

先手が S の Ak からコインを取り除いて Bk になったとする。 T = A 1 ⊕ ⋯ ⊕ B k ⊕ ⋯ ⊕ A n {\displaystyle T=A_{1}\oplus \cdots \oplus B_{k}\oplus \cdots \oplus A_{n}}

とおく。排他的論理和は交換法則、結合法則および X ⊕ X = 0 {\displaystyle X\oplus X=0} を満たすため、次の等式が成り立つ。 T = ⨁ i ; i ≠ k A i ⊕ B k = ⨁ i ; i ≠ k A i ⊕ ( A k ⊕ A k ) ⊕ B k = S ⊕ A k ⊕ B k {\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： S = 0 {\displaystyle S=0} のとき、任意の操作について T ≠ 0 {\displaystyle T\neq 0} である。

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

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

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

故に、必勝形 (A1, …, An) は

(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) [いかたこのたこつぼ]

関連項目

不偏ゲーム

ニム和

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

外部リンク

『ニム（複数山の石取りゲーム）の必勝法』 - 高校数学の美しい物語
.mw-parser-output .asbox{position:relative;overflow:hidden}.mw-parser-output .asbox table{background:transparent}.mw-parser-output .asbox p{margin:0}.mw-parser-output .asbox p+p{margin-top:0.25em}.mw-parser-output .asbox{font-size:90%}.mw-parser-output .asbox-note{font-size:90%}.mw-parser-output .asbox .navbar{position:absolute;top:-0.90em;right:1em;display:none}

この項目は、ゲームに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。
.mw-parser-output .hlist ul,.mw-parser-output .hlist ol{padding-left:0}.mw-parser-output .hlist li,.mw-parser-output .hlist dd,.mw-parser-output .hlist dt{margin-right:0;display:inline-block;white-space:nowrap}.mw-parser-output .hlist dt:after,.mw-parser-output .hlist dd:after,.mw-parser-output .hlist li:after{white-space:normal}.mw-parser-output .hlist li:after,.mw-parser-output .hlist dd:after{content:" ・\a0 ";font-weight:bold}.mw-parser-output .hlist dt:after{content:": "}.mw-parser-output .hlist-pipe dd:after,.mw-parser-output .hlist-pipe li:after{content:" |\a0 ";font-weight:normal}.mw-parser-output .hlist-hyphen dd:after,.mw-parser-output .hlist-hyphen li:after{content:" -\a0 ";font-weight:normal}.mw-parser-output .hlist-comma dd:after,.mw-parser-output .hlist-comma li:after{content:"、";font-weight:normal}.mw-parser-output .hlist-slash dd:after,.mw-parser-output .hlist-slash li:after{content:" /\a0 ";font-weight:normal}.mw-parser-output .hlist dd:last-child:after,.mw-parser-output .hlist dt:last-child:after,.mw-parser-output .hlist li:last-child:after{content:none}.mw-parser-output .hlist dd dd:first-child:before,.mw-parser-output .hlist dd dt:first-child:before,.mw-parser-output .hlist dd li:first-child:before,.mw-parser-output .hlist dt dd:first-child:before,.mw-parser-output .hlist dt dt:first-child:before,.mw-parser-output .hlist dt li:first-child:before,.mw-parser-output .hlist li dd:first-child:before,.mw-parser-output .hlist li dt:first-child:before,.mw-parser-output .hlist li li:first-child:before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child:after,.mw-parser-output .hlist dd dt:last-child:after,.mw-parser-output .hlist dd li:last-child:after,.mw-parser-output .hlist dt dd:last-child:after,.mw-parser-output .hlist dt dt:last-child:after,.mw-parser-output .hlist dt li:last-child:after,.mw-parser-output .hlist li dd:last-child:after,.mw-parser-output .hlist li dt:last-child:after,.mw-parser-output .hlist li li:last-child:after{content:")\a0 ";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li:before{content:" "counter(listitem)" ";white-space:nowrap}.mw-parser-output .hlist dd ol>li:first-child:before,.mw-parser-output .hlist dt ol>li:first-child:before,.mw-parser-output .hlist li ol>li:first-child:before{content:" ("counter(listitem)" "}.mw-parser-output .navbar{display:inline;font-size:75%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}.mw-parser-output .infobox .navbar{font-size:88%}.mw-parser-output .navbox .navbar{display:block;font-size:88%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}