ゲーム理論の問題

石が $n$ 個の山 1 つだけの局面のグランディ数を $g(n)$ とする。$n$ 個の山から $k$ 個（$1\le k\le \lfloor n/2\rfloor$）取ると $n-k$ 個になるので、移れる石の個数は
$$n-\lfloor \frac{n}{2}\rfloor ,\dots ,n-1$$
であり、$g(n)$ はこれらの $g$ の値に含まれない最小の $0$ 以上の整数（mex）である。

$n=0,1$ のときは石を取れないので $g(0)=g(1)=0$。以下、順に計算する。

• $g(2)$：移り先 $1$ → $\mathrm{mex}\{0\}=1$
• $g(3)$：移り先 $2$ → $\mathrm{mex}\{1\}=0$
• $g(4)$：移り先 $2,3$ → $\mathrm{mex}\{1,0\}=2$
• $g(5)$：移り先 $3,4$ → $\mathrm{mex}\{0,2\}=1$
• $g(6)$：移り先 $3,4,5$ → $\mathrm{mex}\{0,2,1\}=3$
• $g(7)$：移り先 $4,5,6$ → $\mathrm{mex}\{2,1,3\}=0$
• $g(8)$：移り先 $4,\dots ,7$ → $\mathrm{mex}\{2,1,3,0\}=4$
• $g(9)$：移り先 $5,\dots ,8$ → $\mathrm{mex}\{1,3,0,4\}=2$
• $g(10)$：移り先 $5,\dots ,9$ → $\mathrm{mex}\{1,3,0,4,2\}=5$
• $g(11)$：移り先 $6,\dots ,10$ → $\mathrm{mex}\{3,0,4,2,5\}=1$
• $g(12)$：移り先 $6,\dots ,11$ → $\mathrm{mex}\{3,0,4,2,5,1\}=6$
• $g(13)$：移り先 $7,\dots ,12$ → $\mathrm{mex}\{0,4,2,5,1,6\}=3$

3 つの山の局面は、それぞれの山のゲームの和なので、スプレイグ・グランディの定理により、そのグランディ数は各山のグランディ数のニム和（2 進法での排他的論理和）である。
$$g(9)\oplus g(12)\oplus g(13)=2\oplus 6\oplus 3$$
2 進法で $2=010_{(2)}$、$6=110_{(2)}$、$3=011_{(2)}$ なので、
$$010_{(2)}\oplus 110_{(2)}=100_{(2)},100_{(2)}\oplus 011_{(2)}=111_{(2)}=7$$
よって求めるグランディ数は $7$ である。

1 つの山のグランディ数を $g(n)$ とする。$n$ 個の山から $k$ 個取ると $n-k$ 個になり、$1\le k\le \lfloor n/2\rfloor$ なので移動先は $\lceil n/2\rceil \le m\le n-1$ の山である。よって $g(n)=\mathrm{mex}\{g(m):\lceil n/2\rceil \le m\le n-1\}$。

• $g(0)=0$、$g(1)=0$（移動先なし）
• $g(2)$: $m\in \{1\}$ → $\mathrm{mex}\{0\}=1$
• $g(3)$: $m\in \{2\}$ → $\mathrm{mex}\{1\}=0$
• $g(4)$: $m\in \{2,3\}$ → $\mathrm{mex}\{1,0\}=2$
• $g(5)$: $m\in \{3,4\}$ → $\mathrm{mex}\{0,2\}=1$
• $g(6)$: $m\in \{3,4,5\}$ → $\mathrm{mex}\{0,2,1\}=3$
• $g(7)$: $m\in \{4,5,6\}$ → $\mathrm{mex}\{2,1,3\}=0$
• $g(8)$: $m\in \{4,\dots ,7\}$ → $\mathrm{mex}\{2,1,3,0\}=4$
• $g(9)$: $m\in \{5,\dots ,8\}$ → $\mathrm{mex}\{1,3,0,4\}=2$
• $g(10)$: $m\in \{5,\dots ,9\}$ → $\mathrm{mex}\{1,3,0,4,2\}=5$
• $g(11)$: $m\in \{6,\dots ,10\}$ → $\mathrm{mex}\{3,0,4,2,5\}=1$
• $g(12)$: $m\in \{6,\dots ,11\}$ → $\mathrm{mex}\{3,0,4,2,5,1\}=6$
• $g(13)$: $m\in \{7,\dots ,12\}$ → $\mathrm{mex}\{0,4,2,5,1,6\}=3$

複数の山の和のグランディ数は各山の排他的論理和（XOR）なので、$g(9)\oplus g(12)\oplus g(13)=2\oplus 6\oplus 3$。$2\oplus 6=4$（$010\oplus 110=100$）、$4\oplus 3=7$（$100\oplus 011=111$）。よって 7。

検算: 各 $g(n)$ の表を再度たどり、$g(2)=1,g(4)=2,g(6)=3,g(8)=4,g(10)=5,g(12)=6$ と偶数で 1 ずつ増えるパターンが整合していることを確認した。