ゲーム理論の問題

石が $n$ 個の山 1 つだけの局面のグランディ数を $g(n)$ とする。$n$ 個の山からは $n-1,n-3,n-4$ 個（0 以上のもの）の山に移れるので
$$g(n)=\mathrm{mex}\{g(n-k)\mid k\in \{1,3,4\},k\le n\}$$
である（$\mathrm{mex}$ は集合に含まれない最小の 0 以上の整数）。

順に計算する。
- $g(0)=\mathrm{mex}\varnothing =0$
- $g(1)=\mathrm{mex}\{g(0)\}=\mathrm{mex}\{0\}=1$
- $g(2)=\mathrm{mex}\{g(1)\}=\mathrm{mex}\{1\}=0$
- $g(3)=\mathrm{mex}\{g(2),g(0)\}=\mathrm{mex}\{0\}=1$
- $g(4)=\mathrm{mex}\{g(3),g(1),g(0)\}=\mathrm{mex}\{1,0\}=2$
- $g(5)=\mathrm{mex}\{g(4),g(2),g(1)\}=\mathrm{mex}\{2,0,1\}=3$
- $g(6)=\mathrm{mex}\{g(5),g(3),g(2)\}=\mathrm{mex}\{3,1,0\}=2$
- $g(7)=\mathrm{mex}\{g(6),g(4),g(3)\}=\mathrm{mex}\{2,1\}=0$
- $g(8)=\mathrm{mex}\{g(7),g(5),g(4)\}=\mathrm{mex}\{0,3,2\}=1$
- $g(9)=\mathrm{mex}\{g(8),g(6),g(5)\}=\mathrm{mex}\{1,2,3\}=0$
- $g(10)=\mathrm{mex}\{g(9),g(7),g(6)\}=\mathrm{mex}\{0,2\}=1$
- $g(11)=\mathrm{mex}\{g(10),g(8),g(7)\}=\mathrm{mex}\{1,0\}=2$

各手番では 1 つの山だけを動かすので、全体の局面は 3 つの山のゲームの直和である。スプレイグ・グランディの定理より、直和のグランディ数は各成分のグランディ数の排他的論理和（ニム和）$\oplus$ になる。
$$g(5)\oplus g(6)\oplus g(11)=3\oplus 2\oplus 2.$$
2 進法で $3=11_{(2)}$, $2=10_{(2)}$ であり、$2\oplus 2=0$ なので
$$3\oplus 2\oplus 2=3.$$
よって求めるグランディ数は $3$ である。

1 つの山のグランディ数 $g(n)$ を $g(n)=\mathrm{mex}\{g(n-1),g(n-3),g(n-4)\}$（存在する項のみ）で順に求める。$g(0)=0$。$g(1)=\mathrm{mex}\{0\}=1$。$g(2)=\mathrm{mex}\{g(1)\}=\mathrm{mex}\{1\}=0$。$g(3)=\mathrm{mex}\{g(2),g(0)\}=\mathrm{mex}\{0,0\}=1$。$g(4)=\mathrm{mex}\{g(3),g(1),g(0)\}=\mathrm{mex}\{1,1,0\}=2$。$g(5)=\mathrm{mex}\{g(4),g(2),g(1)\}=\mathrm{mex}\{2,0,1\}=3$。$g(6)=\mathrm{mex}\{g(5),g(3),g(2)\}=\mathrm{mex}\{3,1,0\}=2$。$g(7)=\mathrm{mex}\{g(6),g(4),g(3)\}=\mathrm{mex}\{2,2,1\}=0$。$g(8)=\mathrm{mex}\{g(7),g(5),g(4)\}=\mathrm{mex}\{0,3,2\}=1$。$g(9)=\mathrm{mex}\{g(8),g(6),g(5)\}=\mathrm{mex}\{1,2,3\}=0$。$g(10)=\mathrm{mex}\{g(9),g(7),g(6)\}=\mathrm{mex}\{0,0,2\}=1$。$g(11)=\mathrm{mex}\{g(10),g(8),g(7)\}=\mathrm{mex}\{1,1,0\}=2$。よって $g(5)=3,g(6)=2,g(11)=2$。複数の山の和のグランディ数は各山のグランディ数の XOR なので $3\oplus 2\oplus 2=3$（$2\oplus 2=0$ より）。検算: 数列は $0,1,0,1,2,3,2,0,1,0,1,2$ で、$g(7)=0$ から $g(11)=2$ まで周期 7 の様子（$g(\mathrm{7..11})=0,1,0,1,2$ が $g(\mathrm{0..4})$ と一致）とも整合する。