ゲーム理論の問題

石が $n$ 個の山 1 つの局面のグランディ数を $g(n)$ とする。$n$ 個の山を $a$ 個と $b$ 個（$a+b=n$, $a,b\ge 2$）に分けると 2 つの山の和の局面になるので、そのグランディ数は $g(a)\oplus g(b)$ である。よって $g(n)$ は、すべての分け方についての $g(a)\oplus g(b)$ の集合の mex である。小さい $n$ から順に求める。

$n=1,2,3$：どちらも $2$ 個以上の 2 山には分けられない（$1+1$ や $1+2$ は不可）ので、1 手で移れる局面がない。よって $g(1)=g(2)=g(3)=0$。

$n=4$：分け方は $2+2$ のみ。$g(2)\oplus g(2)=0\oplus 0=0$。集合 $\{0\}$ の mex より $g(4)=1$。

$n=5$：分け方は $2+3$ のみ。$g(2)\oplus g(3)=0\oplus 0=0$。よって $g(5)=1$。

$n=6$：分け方は $2+4$, $3+3$。
$g(2)\oplus g(4)=0\oplus 1=1$, $g(3)\oplus g(3)=0\oplus 0=0$。集合 $\{0,1\}$ の mex より $g(6)=2$。

$n=7$：分け方は $2+5$, $3+4$。
$g(2)\oplus g(5)=0\oplus 1=1$, $g(3)\oplus g(4)=0\oplus 1=1$。集合 $\{1\}$ の mex より $g(7)=0$。

$n=8$：分け方は $2+6$, $3+5$, $4+4$。
$g(2)\oplus g(6)=0\oplus 2=2$,
$g(3)\oplus g(5)=0\oplus 1=1$,
$g(4)\oplus g(4)=1\oplus 1=0$（2 進法で $1\oplus 1=0$）。
集合 $\{0,1,2\}$ の mex より $g(8)=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}$$
となり、求めるグランディ数は $3$ である。

1つの山の石の個数が $n$ のときのグランディ数を $g(n)$ とする。複数の山からなる局面のグランディ数は、各山のグランディ数の排他的論理和（XOR）になる。

分けた後の2つの山はどちらも2個以上でなければならないので、$n=2,3$ では操作できない。$n=0,1$ も操作できない。よって $g(0)=g(1)=g(2)=g(3)=0$。

• $g(4)$: 分け方は $2+2$ のみ。$0\oplus 0=0$ なので、$g(4)=\mathrm{mex}\{0\}=1$。
• $g(5)$: 分け方は $2+3$ のみ。$0\oplus 0=0$ なので、$g(5)=\mathrm{mex}\{0\}=1$。
• $g(6)$: $2+4$ で $0\oplus 1=1$、$3+3$ で $0\oplus 0=0$。よって $g(6)=\mathrm{mex}\{0,1\}=2$。
• $g(7)$: $2+5$ で $0\oplus 1=1$、$3+4$ で $0\oplus 1=1$。よって $g(7)=\mathrm{mex}\{1\}=0$。
• $g(8)$: $2+6$ で $0\oplus 2=2$、$3+5$ で $0\oplus 1=1$、$4+4$ で $1\oplus 1=0$。よって $g(8)=\mathrm{mex}\{0,1,2\}=3$。

検算として、各 $n$ について分け方を漏れなく数えたことを確認した（$8$ の分け方は $2+6,3+5,4+4$ の3通り）。

答えは $3$。