石の個数が同じになってはいけないニム (山が 2 つの場合), そのグランディ数

石の個数が同じになってはいけないニムはマヤゲームと呼ばれます。(参考: 『石取りゲームの数学～ゲームと代数の不思議な関係～』)

正確には、マヤゲームとは

通常のニムで指せる手のうち、ある $2$ 山の石が同じ個数になる手はダメ
- それ以外は OK
指せる手が無くなったプレイヤーの負け

というルールのゲームと考えていいです。*1

たとえば $(1, 2, 3, 6, 8) \to (1, 2, 3, 6, 6)$ は通常のニムでは許される手ですが、マヤゲームでは行えません。
なので、マヤゲームでは局面 $(0, 1, 2, \dots, n - 1)$ を渡された側が負けになります。

この記事では、マヤゲームで山が $2$ つの場合のグランディ数を求めます。
一般に、局面 $P$ のグランディ数 $g(P)$ とは「$P$ から一手で移れる局面のグランディ数に現れない最小の非負整数」のことです。
式で書くと次のようになります。非負整数全体の集合を $\mathbb{N}_0 = \{0, 1, 2, \dots\}$, 局面 $P$ から局面 $P'$ に移れることを $P \to P'$ と書いています。

$g: $ 局面全体の集合 $\to \mathbb{N}_0$
$g(P) = \min(\mathbb{N}_0 \setminus \{g(P') \mid P \to P'\})$
$P \to P'$ となる $P'$ が存在しないとき $g(P) = 0$

いまの場合 $g( (0, 1) ) = g( (1, 0) ) = 0$ です。さすがに括弧がうるさいので $g(0, 1)$ などと書きます。
他の局面のグランディ数も計算してみると

$g(0, 2) = \min(\mathbb{N}_0 \setminus \{g(0, 1)\}) = \min(\{1, 2, \dots\}) = 1$
$g(1, 2) = \min(\mathbb{N}_0 \setminus \{g(0, 2), g(1, 0)\}) = \min(\{2, 3, \dots\}) = 2$

となります。
$g(a, b) \ (0 \le a, b \le 5)$ の値を表にしました。

a ＼ b	0	1	2	3	4	5
0	x	0	1	2	3	4
1	0	x	2	1	4	3
2	1	2	x	0	5	6
3	2	1	0	x	6	5
4	3	4	5	6	x	0
5	4	3	6	5	0	x

この表を眺めると $g(a, b) = g_{\text{nim}}(a, b) - 1 = (a \ \mathrm{xor} \ b) - 1$ *2 が成り立っていることに気づきます。

一般の $a, b \in \mathbb{N}_0$ について $g(a, b) = (a \ \mathrm{xor} b) - 1$ が成り立つことを証明しましょう。
$a < b$ の場合も同様に示せるので、ここでは $a > b$ とします。

$a = 1, b = 0$ のとき $1 \ \mathrm{xor} \ 0 = 1$ より、確かに成立しています。
$g(a', b) \ (0 \le a' < a, a' \ne b)$ や $g(a, b') \ (0 \le b' < b)$ に対し成立していると仮定します (帰納法の仮定です) 。

$\quad S := \{g(a', b), g(a, b') \mid (a, b) \to (a', b), (a, b')\}$

とおきます。$g(a, b) = \min (\mathbb{N}_0 \setminus S)$ です。また、仮定より

$\quad S = \{(a' \ \mathrm{xor} \ b) - 1, (a \ \mathrm{xor} \ b') - 1 \mid (a, b) \to (a', b), (a, b')\}$

となります。次の 2 つを示せば $(a \ \mathrm{xor} \ b) - 1 = g(a, b)$ となるので証明が終わります。
1. $(a \ \mathrm{xor} \ b) - 1 \not\in S$
2. $0 \le y < (a \ \mathrm{xor} \ b) - 1$ ならば $y \in S$
(1) より $(a \ \mathrm{xor} \ b) - 1 \in \mathbb{N}_0 \setminus S$ となり、(2) より $y \not\in \mathbb{N}_0 \setminus S$ となるので $\mathrm{min}(\mathbb{N}_0 \setminus S) = (a \ \mathrm{xor} \ b) - 1$ が成り立ちます。
[(1) の証明] $(a \ \mathrm{xor} \ b) - 1 \in S$ と仮定して矛盾を導きます。このとき、次のうち少なくとも一方が成り立ちます。
- ある $a' \ (0 \le a' < a, a' \ne b)$ があって $(a \ \mathrm{xor} \ b) - 1 = (a' \ \mathrm{xor} \ b) - 1$ と表せる
- ある $b' \ (0 \le b' < b)$ があって $(a \ \mathrm{xor} \ b) - 1 = (a \ \mathrm{xor} \ b') - 1$ と表せる
ここでは $(a \ \mathrm{xor} \ b) - 1 = (a' \ \mathrm{xor} \ b) - 1$ だとします。両辺に $+1$ をして $\mathrm{xor} \ b$ をすると $a = a'$ となり $a' < a$ に反します。もう一方の場合も同様に矛盾が生じるため、$(a \ \mathrm{xor} \ b) - 1 \not\in S$ です。
[(2) の証明] $y + 1 < a \ \mathrm{xor} \ b = g_{\text{nim}}(a, b)$ よりグランディ数の定義から、次のうち少なくとも一方が成り立ちます。
- ある $a' \ (0 \le a' < a)$ があって $y + 1 = a' \ \mathrm{xor} \ b$
- ある $b' \ (0 \le b' < b)$ があって $y + 1 = a \ \mathrm{xor} \ b'$
ここで、$y + 1 \ge 1$ より $a' \ \mathrm{xor} \ b$ や $a \ \mathrm{xor} \ b'$ も $1$ 以上で、特に $0$ でないので $a' \ne b, a \ne b'$ です。したがって $y = (a' \ \mathrm{xor} \ b) - 1$ (または $= (a \ \mathrm{xor} \ b') - 1$) $\in S$ です。