ニムゲームと排他的論理和

ニムと呼ばれる二人で行うゲームの必勝法と、それにまつわる演算を紹介します。

ニム

ニムは二人のプレイヤーがいくつかの石の山から石を交互に取り合うゲームです。ニムのルールはいろいろバリエーションがありますが、次のルールを考えます。

ニムのルール

石の山をいくつか用意する。
二人のプレーヤーは交互に $1$ 個以上石を取る。このとき、複数の山にまたがっては取れないが、一つの山からは何個でも取れる。
取れる石が無くなったら負け。

後でルール２を変えたゲームも考えます。

以下では、ニムの局面を非負整数の順序対で表します。

例： $(4,2,1)$ は、 $1$ 番目の山に $4$ 個、 $2$ 番目の山に $2$ 個、 $3$ 番目の山に $1$ 個石がある局面。

Grundy値

ニムの局面には、Grundy値という非負整数値が定まります。

Grundy値の定義と性質については

fibonacci-freak.hatenablog.com

にあります。そこに書かれているように、Grundy値が $0$ の局面は後手必勝、nonzeroの局面は先手必勝です。

ニムの局面 $(n_1,\ldots,n_k)$ のGrundy値を $G(n_1,\ldots,n_k)$ と表すことにすると、局面 $(n_1,\ldots,n_k)$ は局面 $(n_1),\ldots,(n_k)$ の直和*1だから、上の記事の第一定理より、

\begin{split} G(n_1,\ldots,n_k)&= G(n_1) \oplus \cdots \oplus G(n_k) \\&= n_1 \oplus \cdots \oplus n_k \end{split}

ここで $\oplus$ は二進記数法の各桁ごとの排他的論理和です。この「二進記数法の各桁ごとの排他的論理和」のことも単に排他的論理和と呼びます。

例： $11 \oplus 5 = {1011}_2 \oplus {101}_2 = {1110}_2=14$

よって次の結果を得ます：

定理１ ニムの局面 $(n_1,\ldots,n_k)$ が後手必勝 $\Leftrightarrow$ $n_1 \oplus \cdots \oplus n_k = 0$

これをもとにしたニムの必勝法の手順は

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

の「ニムの必勝法の概略」にあります。その記事では「後手必勝」のことを単に「必勝形」と呼んでいます。

$N$ -ニム

$N$ を自然数とします。上のニムのルールにおいて、一つの山から取れる石の個数を $1$ 以上 $N$ 以下に変更したゲームを考えます。区別のため、このゲームを $N$ -ニムと呼ぶことにします*2。

$N$ -ニムの局面も同じく順序対で表し、 $N$ -ニムの局面 $(n_1,\ldots,n_k)$ のGrundy値を $G_N(n_1,\ldots,n_k)$ と表すことにすると、

\begin{split} G_N(n_1,\ldots,n_k)&= G_N(n_1) \oplus \cdots \oplus G_N(n_k) \\&= (n_1 \ \mathrm{mod} \ N+1) \oplus \cdots \oplus (n_k \ \mathrm{mod} \ N+1) \end{split}

ここで自然数 $k$ に対して $n \ \mathrm{mod} \ k$ は、整数 $n$ を $k$ で割った余り( $0$ 以上 $k-1$ 以下)を返す関数です。

まとめると次の結果となります：

定理２ $N$ -ニムの局面 $(n_1,\ldots,n_k)$ が後手必勝 $\Leftrightarrow$ $(n_1 \ \mathrm{mod} \ N+1) \oplus \cdots \oplus (n_k \ \mathrm{mod} \ N+1) = 0$

$3$ -ニムの必勝法

$N=3$ の場合について必勝法を考えます。

系 $3$ -ニムの局面 $(n_1,\ldots,n_k)$ が後手必勝 $\Leftrightarrow$ $n_1, \ldots , n_k$ のうち、 $4$ で割って $1$ 余るものの個数、 $2$ 余るものの個数、 $3$ 余るものの個数の偶奇が一致する。

証明．定理２から明らか。証明終わり

この系をもとに具体的な必勝法の手順を考えます。 $(n_1,\ldots,n_k)$ を $3$ -ニムの先手必勝の局面とします。 $n_1, \ldots , n_k$ のうち、 $4$ で割って $i(i=0,1,2,3)$ 余るものの個数を $a_i$ とおいて、 $a_1,a_2,a_3$ の偶奇で場合分けします。系により次の二つの場合に分かれます。