Nim
概要
Nim（nim）とは、いくつかの山から 2 人が交互に 1 つの山を選んで 1 本以上の棒を取り、最後の 1 本を取った者が勝つゲームである。Bouton の定理により、手番の者が負ける局面（必敗局面）は、山の本数を二進法で書いて桁ごとに排他的論理和をとった Nim 和が 0 になる局面にちょうど一致し、Nim 和が 0 でない局面からは Nim 和を 0 にする手が必ずある。たとえば山が 1,3,5,7 本の局面は Nim 和が 0 なので後手が勝つ。最後の 1 本を取った者が負ける規則では、すべての山が 1 本以下の局面だけ判定が変わる。Sprague–Grundy の定理により、Nim は不偏ゲームの一般論の基本となる。
動機
机の上にマッチ棒の山がいくつかある。2 人が交互に、どれか 1 つの山を選んで、その山から 1 本以上好きなだけ棒を取る。最後の 1 本を取った人が勝ちである。これが Nim（ニム）と呼ばれるゲームである。
山が 2 つで本数が等しい局面、たとえば $(4,4)$ から始めると、後から打つ人が必ず勝てる。先手がどちらかの山から何本取っても、後手はもう一方の山から同じ本数を取って 2 つの山を再び等しくすればよく、最後の 1 本は必ず後手が取るからである。では山が $1,3,5,7$ 本の 4 つのときはどうか。この局面でも後手が必ず勝てる。理由は本数を二進法で書くと見えてくる。
$$
1=001_{(2)},\quad 3=011_{(2)},\quad 5=101_{(2)},\quad 7=111_{(2)}
$$
と縦に並べると、どの桁にも $1$ がちょうど偶数個（$4$ 個、$2$ 個、$2$ 個）ある。一方、山が $3,4,5$ 本なら $011,100,101$ の $2$ の位に $1$ が 1 個しかなく、この局面では先手が勝てる。$3$ 本の山から $2$ 本取って $(1,4,5)$、すなわち $001,100,101$ にすれば、どの桁の $1$ も偶数個になるからである。「すべての桁で $1$ の個数が偶数である局面は、手番の人の負け」というのが、Bouton が 1901–02 年に証明した Nim の完全な解である Bou02。本記事ではこの定理と、最後の 1 本を取った人が負けになる規則での解、さらに一般の組合せゲームへの拡張である Sprague–Grundy の定理を述べる。
規則と定義
$k\ge1$ とする。$k$ 個の非負整数の組 $(n_1,\dots,n_k)$ を Nim の局面という（$n_i$ は $i$ 番目の山の本数）。局面 $(n_1,\dots,n_k)$ からの手とは、ある $i$ と $0\le m< n_i$ を満たす整数 $m$ を選んで $n_i$ を $m$ に置き換えることである。すべての $n_i$ が $0$ である局面 $(0,\dots,0)$ を終局という。2 人の対局者は交互に手を打ち、終局で手番になった者（打つ手がない者）の負け、すなわち最後の 1 本を取った者の勝ちとする。これを Nim（nim）という。
1 回の手で棒の総数 $n_1+\dots+n_k$ は少なくとも $1$ 減るので、どのように打っても $n_1+\dots+n_k$ 手以内に終局に達し、引き分けは無い。
局面の必敗・必勝を、棒の総数についての帰納法で次のように定める。
- 終局は必敗局面である。
- 終局でない局面は、そこからどの手を打っても必勝局面になるとき必敗局面であり、必敗局面になる手が 1 つでもあるとき必勝局面である。
総数が少ない局面の必敗・必勝がすべて決まっていれば、1 手先の局面は総数が少ないので、この定義で矛盾なく決まる。必勝局面では、手番の者は必敗局面へ移る手を打ち続ければ必ず勝つ。必敗局面では、手番の者がどう打っても相手が同じ方針で勝つ。
非負整数 $a,b$ を二進法で $a=\sum_j a_j2^j$、$b=\sum_j b_j2^j$（$a_j,b_j\in\{0,1\}$）と書くとき、
$$
a\oplus b:=\sum_j c_j2^j,\qquad c_j:=\begin{cases}0&(a_j=b_j),\\1&(a_j\ne b_j)\end{cases}
$$
を $a$ と $b$ の Nim 和（nim-sum）という。すなわち各桁ごとの排他的論理和であり、二進法で繰り上がりを無視した足し算である。
たとえば $3\oplus5=011_{(2)}\oplus101_{(2)}=110_{(2)}=6$、$7\oplus5=111_{(2)}\oplus101_{(2)}=010_{(2)}=2$ である。各桁で $0,1$ を $2$ を法として足していることから、次の性質がすぐに分かる：$a\oplus b=b\oplus a$、$(a\oplus b)\oplus c=a\oplus(b\oplus c)$、$a\oplus0=a$、$a\oplus a=0$。したがって非負整数全体は $\oplus$ について、すべての元が自分自身の逆元になるアーベル群をなし、$a\oplus b=c$ と $a=b\oplus c$ は同値である。結合法則により $n_1\oplus\dots\oplus n_k$ は括弧のつけ方によらず、その $j$ 桁目は、$n_1,\dots,n_k$ のうち $j$ 桁目が $1$ であるものの個数の偶奇（偶数なら $0$、奇数なら $1$）に等しい。
Boutonの定理
必敗局面の集合は、次の 3 条件で特徴づけられる。
局面の集合 $\mathcal{P}$ が次の 3 条件を満たすとする。
- 終局は $\mathcal{P}$ に属する。
- $\mathcal{P}$ に属する局面からのどの手も、$\mathcal{P}$ に属さない局面へ移る。
- $\mathcal{P}$ に属さない局面からは、$\mathcal{P}$ に属する局面へ移る手がある。
このとき $\mathcal{P}$ は必敗局面全体の集合に一致する。
局面 $x$ について「$x\in\mathcal{P}$ と $x$ が必敗局面であることは同値」を、$x$ の棒の総数 $s$ についての強い数学的帰納法で示す。$s=0$ のとき $x$ は終局であり、条件 1 により $x\in\mathcal{P}$、定義により $x$ は必敗局面である。$s>0$ とし、総数が $s$ 未満の局面について主張が成り立つとする。$x$ から 1 手で移る局面はどれも総数が $s$ 未満である。$x\in\mathcal{P}$ なら、条件 2 により 1 手先の局面はすべて $\mathcal{P}$ に属さず、帰納法の仮定によりすべて必勝局面なので、$x$ は必敗局面である。$x\notin\mathcal{P}$ なら、条件 3 により $\mathcal{P}$ に属する局面、すなわち帰納法の仮定により必敗局面へ移る手があるので、$x$ は必勝局面である。$\square$
Nim の局面 $(n_1,\dots,n_k)$ が必敗局面であるための必要十分条件は
$$
n_1\oplus n_2\oplus\dots\oplus n_k=0
$$
である。すなわち、二進法で書いた本数のどの桁にも $1$ が偶数個あることである。
$\mathcal{P}:=\{(n_1,\dots,n_k)\mid n_1\oplus\dots\oplus n_k=0\}$ が lem-nim-p-set の 3 条件を満たすことを示す。以下 $s:=n_1\oplus\dots\oplus n_k$ とおく。
条件 1：終局では $s=0\oplus\dots\oplus0=0$ である。
条件 2：$s=0$ の局面で $n_i$ を $m\ne n_i$ に置き換えると、新しい Nim 和は、Nim 和の性質により
$$
s\oplus n_i\oplus m=n_i\oplus m
$$
であり、$n_i\ne m$ なので二進法のある桁が異なって $n_i\oplus m\ne0$ である。よって移った先は $\mathcal{P}$ に属さない。
条件 3：$s\ne0$ とし、$s$ を二進法で書いたときの最上位の $1$ の桁を $d$ 桁目とする（$2^d\le s<2^{d+1}$）。$s$ の $d$ 桁目が $1$ なので、$n_1,\dots,n_k$ のうち $d$ 桁目が $1$ のものは奇数個あり、特に 1 つはある。それを $n_i$ とし、$m:=n_i\oplus s$ とおく。$s$ の $d$ 桁目より上の桁はすべて $0$ なので、$m$ と $n_i$ は $d$ 桁目より上の桁が一致し、$d$ 桁目は $n_i$ で $1$、$m$ で $0$ である。二進法で最初に異なる桁が大きい方が大きい数なので $m< n_i$ であり、$n_i$ を $m$ に置き換えるのは正しい手である。移った先の Nim 和は
$$
s\oplus n_i\oplus m=s\oplus n_i\oplus n_i\oplus s=0
$$
なので、移った先は $\mathcal{P}$ に属する。
以上と lem-nim-p-set により、$\mathcal{P}$ は必敗局面全体に一致する。$\square$
証明の条件 3 の部分は、勝つ手の求め方をそのまま与えている：全体の Nim 和 $s$ を求め、$s$ の最上位の $1$ の桁（$d$ 桁目）に $1$ をもつ山 $n_i$ を 1 つ選び、その山を $n_i\oplus s$ 本に減らせばよい。勝つ手の個数は、$d$ 桁目に $1$ をもつ山の個数に等しい。実際、山 $n_j$ を $m'$ に減らす手で Nim 和が $0$ になるなら $m'=n_j\oplus s$ でなければならず、それが $n_j$ より小さいのは $n_j$ の $d$ 桁目が $1$ のときに限る（$0$ なら $n_j\oplus s$ の $d$ 桁目が $1$ になり、上の桁は一致するので $n_j$ より大きい）。
例と反例
古典的な開始局面 $(1,3,5,7)$ では、
$$
1\oplus3\oplus5\oplus7=001_{(2)}\oplus011_{(2)}\oplus101_{(2)}\oplus111_{(2)}=000_{(2)}=0
$$
なので必敗局面であり、後手が勝つ。たとえば先手が $7$ の山から $3$ 本取って $(1,3,5,4)$ にすると Nim 和は $1\oplus3\oplus5\oplus4=3=011_{(2)}$ で、最上位の $1$ は $2$ の位にある。$2$ の位に $1$ をもつ山は $3$（$011$）だけなので、後手は $3$ の山を $3\oplus3=0$ 本にすればよく、$(1,0,5,4)$ で Nim 和は $1\oplus5\oplus4=0$ に戻る。
$(3,4,5)$ では $3\oplus4\oplus5=2=010_{(2)}$ で、$2$ の位に $1$ をもつ山は $3=011_{(2)}$ だけである。勝つ手は $3$ の山を $3\oplus2=1$ 本にする（$2$ 本取る）ただ 1 つで、$(1,4,5)$ の Nim 和は $0$ である。
$(9,11,13)$ では $9\oplus11\oplus13=15=1111_{(2)}$ で、$8$ の位に $1$ をもつ山は $9,11,13$ の 3 つともである。勝つ手は $9\to9\oplus15=6$、$11\to11\oplus15=4$、$13\to13\oplus15=2$ の 3 つあり、$(6,11,13)$、$(9,4,13)$、$(9,11,2)$ はどれも Nim 和が $0$ である。
5 つの山 $(1,2,5,7,11)$ では Nim 和は $10=1010_{(2)}$ で、$8$ の位に $1$ をもつのは $11$ だけなので、勝つ手は $11$ の山から $10$ 本取って $(1,2,5,7,1)$ にするただ 1 つである（Bruckner–Thomson–Bruckner の §3.5.3、Example 3.5.7、p. 158 BTB11）。
$(3,10,12)$ では $s=3\oplus10\oplus12=5=0101_{(2)}$ である。「どれかの山 $n$ を $n\oplus s$ 本にすれば Nim 和が $0$ になる」のは計算上は正しいが、$3\oplus5=6$、$10\oplus5=15$ はもとの本数より大きく、棒を増やすことは手として許されない。正しい手になるのは、$s$ の最上位の $4$ の位に $1$ をもつ $12=1100_{(2)}$ の山を $12\oplus5=9$ 本にする手だけである。「Nim 和 $s\ne0$ ならどの山を $n\oplus s$ 本にしてもよい」という主張は、山が $s$ の最上位の桁に $1$ をもつという条件を落としており、この例で破れる。
棒の総数の偶奇や、各山の本数の偶奇だけでは必敗・必勝は決まらない。$(2,2)$ と $(2,4)$ はどちらも総数が偶数で、どの山も偶数本であるが、$2\oplus2=0$ なので $(2,2)$ は必敗局面、$2\oplus4=6\ne0$ なので $(2,4)$ は必勝局面である（$4$ の山を $2$ 本にすればよい）。また $(1,2,3)$ は総数 $6$ だが $1\oplus2\oplus3=0$ で必敗局面、$(1,2,4)$ は総数 $7$ で $1\oplus2\oplus4=7\ne0$ の必勝局面である。Nim 和は、二進法の各桁の $1$ の個数の偶奇を桁ごとに別々に見ている点が、普通の足し算と異なる。
最後の1本を取ると負けの規則
最後の 1 本を取った者が負けになる規則（misère 規則）では、ほとんどの局面で通常の規則と同じ戦略が使え、すべての山が $1$ 本以下になる局面だけ判定が変わる。以下この節では、終局で手番になった者（直前に最後の 1 本を取られた者）を勝ちとし、必敗・必勝を def-nim-p-position と同じ帰納法で、ただし「終局は必勝局面」として定める。lem-nim-p-set は、条件 1 を「終局は $\mathcal{P}$ に属さない」に、条件 3 を「$\mathcal{P}$ に属さない終局でない局面からは $\mathcal{P}$ へ移る手がある」に替えて、同じ証明で成り立つ。
最後の 1 本を取った者が負けになる規則で、局面 $(n_1,\dots,n_k)$ が必敗局面であるための必要十分条件は、次のいずれかが成り立つことである。
- すべての山が $1$ 本以下で、$1$ 本の山の個数が奇数である。
- $2$ 本以上の山があり、$n_1\oplus\dots\oplus n_k=0$ である。
条件 1 または 2 を満たす局面の集合を $\mathcal{P}$ とする。まず、$2$ 本以上の山がちょうど 1 つの局面では Nim 和が $0$ にならないことに注意する：その山を $n_i\ge2$ とすると、$n_i$ の最上位の $1$ の桁は $2$ の位以上であり、ほかの山は $0$ か $1$ なのでその桁に $1$ をもたず、Nim 和のその桁は $1$ である。したがって条件 2 を満たす局面には $2$ 本以上の山が 2 つ以上ある。
終局は $1$ 本の山が $0$ 個（偶数）なので $\mathcal{P}$ に属さない。
$\mathcal{P}$ からの手は $\mathcal{P}$ の外へ移る：条件 1 の局面からの手は $1$ 本の山を $0$ 本にするしかなく、$1$ 本の山の個数が偶数になる。条件 2 の局面では $2$ 本以上の山が 2 つ以上あり、1 回の手で変わる山は 1 つなので、移った先にも $2$ 本以上の山が残る。移った先の Nim 和は prf-nim-bouton の条件 2 と同じ理由で $0$ でないので、条件 2 を満たさない。
$\mathcal{P}$ の外の終局でない局面からは $\mathcal{P}$ へ移れる：すべての山が $1$ 本以下で $1$ 本の山が偶数個（$2$ 個以上）あるなら、そのうち 1 つを取れば奇数個になる。$2$ 本以上の山がちょうど 1 つなら、その山を $0$ 本か $1$ 本に減らして、$1$ 本の山の個数を奇数にできる。$2$ 本以上の山が 2 つ以上あって Nim 和が $0$ でないなら、prf-nim-bouton の条件 3 の手で Nim 和を $0$ にでき、変わる山は 1 つなので $2$ 本以上の山は少なくとも 1 つ残り、移った先は条件 2 を満たす。
以上により、上で述べた形の lem-nim-p-set から $\mathcal{P}$ は必敗局面全体に一致する。$\square$
たとえば $(1,1,1)$ は通常の規則では $1\oplus1\oplus1=1\ne0$ の必勝局面だが、この規則では条件 1 を満たす必敗局面である。$(1,3,5,7)$ はどちらの規則でも必敗局面である。戦略としては、$2$ 本以上の山が 2 つ以上あるうちは通常の Nim と同じく Nim 和を $0$ にし、$2$ 本以上の山が 1 つだけになった時点でその山を $0$ 本か $1$ 本にして、$1$ 本の山を奇数個残せばよい（Bruckner–Thomson–Bruckner の §3.7 Problem 148 の解答、pp. 214–215 BTB11）。
Grundy数とSprague–Grundyの定理
Nim の解は、Nim だけでなく、2 人が同じ手の選択肢をもち、各局面から打てる手は有限個で、有限手で必ず終わり、最後に手を打った者が勝つゲーム（不偏ゲーム、組合せゲーム理論）全般に広がる。以下の Grundy 数の議論はこの 2 つの有限性を前提にする。この前提のもとでは、各局面から始まる対局の手数に最大値がある（ある局面から始まる対局の手数に上限が無ければ、1 手先の局面は有限個なので、そのうちの 1 つから始まる対局の手数にも上限が無い。これを繰り返すと終わらない対局が作れてしまい、有限手で終わることに反する）。この最大値を、局面の残り手数と呼ぶ。
不偏ゲームの局面 $x$ の Grundy 数 $g(x)$ を、残り手数についての帰納法で（終局から逆にたどって）次のように定める：$x$ から 1 手で移れる（有限個の）局面を $x_1,\dots,x_r$ とするとき、$g(x)$ は $g(x_1),\dots,g(x_r)$ のどれとも等しくない最小の非負整数である（終局では $r=0$ なので $g(x)=0$）。
不偏ゲームの局面 $x$ が必敗局面であることと $g(x)=0$ であることは同値である。また 1 つの山の Nim では、$n$ 本の山の Grundy 数は $n$ である。
$\mathcal{P}:=\{x\mid g(x)=0\}$ が lem-nim-p-set の 3 条件を満たすことを示す（棒の総数の代わりに、残り手数についての帰納法を使えば、同じ証明で lem-nim-p-set は不偏ゲームにも成り立つ）。終局では $g=0$ である。$g(x)=0$ なら、定義により 1 手先の局面の Grundy 数はどれも $0$ でない。$g(x)\ne0$ なら、$0$ は $g(x)$ より小さいので、定義により 1 手先のある局面の Grundy 数が $0$ である。
1 つの山の Nim で $n$ 本の山から移れるのは $0,1,\dots,n-1$ 本の山である。$n$ についての強い帰納法でそれらの Grundy 数が $0,1,\dots,n-1$ なら、どれとも等しくない最小の非負整数は $n$ である。$\square$
2 つの不偏ゲーム $G_1,G_2$ の和 $G_1+G_2$ とは、局面が $G_1,G_2$ の局面の組 $(x_1,x_2)$ で、手番の者がどちらか一方を選んでそこで 1 手打つゲームのことである。$k$ 個の山の Nim は、1 つの山の Nim を $k$ 個足したものである。
不偏ゲームの和の局面 $(x_1,x_2)$ の Grundy 数は $g(x_1)\oplus g(x_2)$ である。
証明は、残り手数についての帰納法で、$(x_1,x_2)$ から $g(x_1)\oplus g(x_2)$ 未満のどの値の局面へも移れ、その値そのものの局面へは移れないことを示すもので、prf-nim-bouton の条件 2・条件 3 と同じ二進法の議論を使う（Bruckner–Thomson–Bruckner の §3.10.2–3.10.4、pp. 173–178 BTB11）。この定理と prop-nim-grundy-zero を合わせると、$k$ 個の山の Nim の局面 $(n_1,\dots,n_k)$ の Grundy 数は $n_1\oplus\dots\oplus n_k$ であり、必敗局面であることと Nim 和が $0$ であることが同値になって、thm-nim-bouton がもう一度得られる（同書 §3.10.6、pp. 179–180）。
Nim の完全な解（thm-nim-bouton）は C. L. Bouton が 1901–02 年の Annals of Mathematics の論文で与えた Bou02。1930 年代に R. P. Sprague と P. M. Grundy がそれぞれ独立にこのゲームを見直し、Grundy 数による見方を与えた（Bruckner–Thomson–Bruckner の §3.10.1、p. 172 BTB11）。最後の 1 本を取ると負けの規則の Nim は、1961 年の映画「去年マリエンバートで」の中で、カードの列を山として遊ばれる（同書 §3.7、p. 167）。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
