ゲーム理論の問題

方針　山を分けると局面は 2 つの山になります。2 つの山からなる局面のグランディ数は、それぞれの山のグランディ数のニム和です。そこで、各 $n$ について「分け方ごとに $g(a)\oplus g(b)$ を計算し、その集合の mex をとる」ことで、小さい $n$ から順に $g(n)$ を求めます。

$n=1,2,3$　どちらも $2$ 個以上の 2 山には分けられない（$2+2=4$ が最小）ので、1 手も打てません。終了局面のグランディ数は $0$ なので
$$g(1)=g(2)=g(3)=0.$$

$n=4$　分け方は $(2,2)$ のみ。$g(2)\oplus g(2)=0\oplus 0=0$。集合 $\{0\}$ の mex は $1$ なので $g(4)=1$。

$n=5$　分け方は $(2,3)$ のみ。$g(2)\oplus g(3)=0\oplus 0=0$。よって $g(5)=\mathrm{mex}\{0\}=1$。

$n=6$　分け方は $(2,4),(3,3)$。
- $(2,4)$: $0\oplus 1=1$
- $(3,3)$: $0\oplus 0=0$

よって $g(6)=\mathrm{mex}\{0,1\}=2$。

$n=7$　分け方は $(2,5),(3,4)$。
- $(2,5)$: $0\oplus 1=1$
- $(3,4)$: $0\oplus 1=1$

よって $g(7)=\mathrm{mex}\{1\}=0$。

$n=8$　分け方は $(2,6),(3,5),(4,4)$。
- $(2,6)$: $g(2)\oplus g(6)=0\oplus 2=2$
- $(3,5)$: $g(3)\oplus g(5)=0\oplus 1=1$
- $(4,4)$: $g(4)\oplus g(4)=1\oplus 1=0$（2 進法で $1\oplus 1=0$）

移れる局面のグランディ数の集合は $\{0,1,2\}$ なので、その mex は $3$ です。

表にまとめると
$$\begin{array}{ccccccccc}n& 1& 2& 3& 4& 5& 6& 7& 8\\ g(n)& 0& 0& 0& 1& 1& 2& 0& 3\end{array}$$

したがって $g(8)=3$。

各山の大きさごとにグランディ数を小さい順に求める。複数の山からなる局面のグランディ数は、各山のグランディ数の排他的論理和（xor）になる。

• $g(1)=g(2)=g(3)=0$：分けられない（分けると 1 個の山ができる）ので、移れる局面がなく mex$\varnothing =0$。
• $g(4)$：移れるのは $2+2$ のみ。$0\oplus 0=0$ なので mex$\{0\}=1$。
• $g(5)$：移れるのは $2+3$ のみ。$0\oplus 0=0$ なので mex$\{0\}=1$。
• $g(6)$：$2+4$ は $0\oplus 1=1$、$3+3$ は $0\oplus 0=0$ なので mex$\{1,0\}=2$。
• $g(7)$：$2+5$ は $0\oplus 1=1$、$3+4$ は $0\oplus 1=1$ なので mex$\{1\}=0$。
• $g(8)$：$2+6$ は $0\oplus 2=2$、$3+5$ は $0\oplus 1=1$、$4+4$ は $1\oplus 1=0$ なので mex$\{2,1,0\}=3$。

よって $g(8)=3$。