ゲーム理論の問題

このゲームは、各山が独立なゲームの和になっている。石が $n$ 個の山 1 つだけのゲームのグランディ数を $g(n)$ とすると、スプレイグ・グランディの定理により、局面全体のグランディ数は各山のグランディ数の排他的論理和（ニム和、$\oplus$ で表す）であり、グランディ数が $0$ の局面は手番のプレイヤーの負け（後手必勝）、$0$ でない局面は手番のプレイヤーの勝ちである。

山を $a$ 個と $b$ 個に分けた後の局面のグランディ数は $g(a)\oplus g(b)$ なので
$$g(n)=\mathrm{mex}\{g(a)\oplus g(b)\mid a+b=n,1\le a<b\}$$
（$\mathrm{mex}$ は集合に含まれない最小の $0$ 以上の整数）。

$g(n)$ の計算
- $g(1)=g(2)=0$（分けられない）
- $g(3)$: $1+2\to 0$。$\mathrm{mex}\{0\}=1$
- $g(4)$: $1+3\to 1$。$\mathrm{mex}\{1\}=0$
- $g(5)$: $1+4\to 0$, $2+3\to 1$。$\mathrm{mex}\{0,1\}=2$
- $g(6)$: $1+5\to 2$, $2+4\to 0$。$\mathrm{mex}\{0,2\}=1$
- $g(7)$: $1+6\to 1$, $2+5\to 2$, $3+4\to 1\oplus 0=1$。$\mathrm{mex}\{1,2\}=0$
- $g(8)$: $1+7\to 0$, $2+6\to 1$, $3+5\to 1\oplus 2=3$。$\mathrm{mex}\{0,1,3\}=2$
- $g(9)$: $1+8\to 2$, $2+7\to 0$, $3+6\to 1\oplus 1=0$, $4+5\to 0\oplus 2=2$。$\mathrm{mex}\{0,2\}=1$
- $g(10)$: $1+9\to 1$, $2+8\to 2$, $3+7\to 1$, $4+6\to 1$。$\mathrm{mex}\{1,2\}=0$
- $g(11)$: $1+10\to 0$, $2+9\to 1$, $3+8\to 1\oplus 2=3$, $4+7\to 0$, $5+6\to 2\oplus 1=3$。$\mathrm{mex}\{0,1,3\}=2$
- $g(12)$: $1+11\to 2$, $2+10\to 0$, $3+9\to 0$, $4+8\to 2$, $5+7\to 2$。$\mathrm{mex}\{0,2\}=1$
- $g(13)$: $1+12\to 1$, $2+11\to 2$, $3+10\to 1$, $4+9\to 1$, $5+8\to 2\oplus 2=0$, $6+7\to 1\oplus 0=1$。$\mathrm{mex}\{0,1,2\}=3$

最初の局面
$$g(8)\oplus g(11)\oplus g(13)=2\oplus 2\oplus 3=3\ne 0$$
なので先手必勝である。勝ちにつながる手は、操作後の局面のグランディ数を $0$ にする手である。

• $13$ 個の山を分ける: 残りの山のニム和は $g(8)\oplus g(11)=0$ なので、分けた結果のグランディ数が $0$ になればよい。上の計算から $13$ の分け方でそうなるのは $5+8$ だけ（$1$ 通り）。
• $8$ 個の山を分ける: 残りは $g(11)\oplus g(13)=2\oplus 3=1$ なので、分けた結果が $1$ になればよい。$8$ の分け方では $2+6$ だけ（$1$ 通り）。
• $11$ 個の山を分ける: 残りは $g(8)\oplus g(13)=2\oplus 3=1$ なので、分けた結果が $1$ になればよい。$11$ の分け方では $2+9$ だけ（$1$ 通り）。

よって勝ちにつながる手は
$$1+1+1=3\text{通り}.$$

公平ゲームなのでスプレイグ・グランディ理論を使う。$g(n)$ を $n$ 個の山のグランディ数とし、$g(n)=\mathrm{mex}\{g(a)\oplus g(b)\mid a+b=n,a\ne b,a,b\ge 1\}$ で求める（$\oplus$ は XOR）。\n\n$g(1)=g(2)=0$。\n$g(3)$: $1+2\to 0$ なので mex$\{0\}=1$。\n$g(4)$: $1+3\to 1$ なので mex$\{1\}=0$。\n$g(5)$: $1+4\to 0$、$2+3\to 1$ なので $2$。\n$g(6)$: $1+5\to 2$、$2+4\to 0$ なので $1$。\n$g(7)$: $1+6\to 1$、$2+5\to 2$、$3+4\to 1$ なので $0$。\n$g(8)$: $1+7\to 0$、$2+6\to 1$、$3+5\to 1\oplus 2=3$ なので $2$。\n$g(9)$: $1+8\to 2$、$2+7\to 0$、$3+6\to 0$、$4+5\to 2$ なので $1$。\n$g(10)$: $1+9\to 1$、$2+8\to 2$、$3+7\to 1$、$4+6\to 1$ なので $0$。\n$g(11)$: $1+10\to 0$、$2+9\to 1$、$3+8\to 3$、$4+7\to 0$、$5+6\to 3$ なので $2$。\n$g(12)$: $1+11\to 2$、$2+10\to 0$、$3+9\to 0$、$4+8\to 2$、$5+7\to 2$ なので $1$。\n$g(13)$: $1+12\to 1$、$2+11\to 2$、$3+10\to 1$、$4+9\to 1$、$5+8\to 0$、$6+7\to 1$ なので $3$。\n\n初期局面の XOR は $g(8)\oplus g(11)\oplus g(13)=2\oplus 2\oplus 3=3\ne 0$ で先手必勝。勝ちにつながる手は、操作後の全体の XOR が $0$ になるもの。\n\n- 8 の山を分ける: 分けた 2 山の XOR が $g(11)\oplus g(13)=1$ になる分け方。$1+7\to 0$、$2+6\to 1$ ✓、$3+5\to 3$。→ 1 通り\n- 11 の山を分ける: 目標は $g(8)\oplus g(13)=1$。$1+10\to 0$、$2+9\to 1$ ✓、$3+8\to 3$、$4+7\to 0$、$5+6\to 3$。→ 1 通り\n- 13 の山を分ける: 目標は $g(8)\oplus g(11)=0$。$5+8\to 0$ ✓、他は $1,2,1,1,1$ で不適。→ 1 通り\n\n合計 3 通り（$8\to 2+6$、$11\to 2+9$、$13\to 5+8$）。検算: 例えば $8\to 2+6$ のあと山は $2,6,11,13$ でグランディ数 $0,1,2,3$ の XOR は $0$。