ゲーム理論の問題

手順 1：1 つの山のグランディ数を求める。

石が $n$ 個の山のグランディ数を $g(n)$ とする。$n$ 個の山からは $n-1,n-2,n-4$ 個の山（$0$ 以上のもの）へ移れるので、
$$g(n)=\mathrm{mex}\{g(n-1),g(n-2),g(n-4)\}$$
である（負になるものは除く）。小さい順に計算すると、

• $g(0)=0$（動かせない）
• $g(1)=\mathrm{mex}\{0\}=1$
• $g(2)=\mathrm{mex}\{g(1),g(0)\}=\mathrm{mex}\{1,0\}=2$
• $g(3)=\mathrm{mex}\{g(2),g(1)\}=\mathrm{mex}\{2,1\}=0$
• $g(4)=\mathrm{mex}\{g(3),g(2),g(0)\}=\mathrm{mex}\{0,2,0\}=1$
• $g(5)=\mathrm{mex}\{g(4),g(3),g(1)\}=\mathrm{mex}\{1,0,1\}=2$
• $g(6)=\mathrm{mex}\{g(5),g(4),g(2)\}=\mathrm{mex}\{2,1,2\}=0$
• $g(7)=\mathrm{mex}\{g(6),g(5),g(3)\}=\mathrm{mex}\{0,2,0\}=1$
• $g(8)=\mathrm{mex}\{g(7),g(6),g(4)\}=\mathrm{mex}\{1,0,1\}=2$
• $g(9)=\mathrm{mex}\{g(8),g(7),g(5)\}=\mathrm{mex}\{2,1,2\}=0$

よって $g(4)=1,g(8)=2,g(9)=0$ である。

手順 2：スプレイグ・グランディの定理で局面全体のグランディ数を求める。

局面全体のグランディ数は各山のグランディ数のニム和である。2 進法で $1=01_{(2)},2=10_{(2)},0=00_{(2)}$ だから
$$1\oplus 2\oplus 0=11_{(2)}=3$$
となり、$0$ でないので先手必勝である。

手順 3：全体のグランディ数を $0$ にする手を数える。

ある山のグランディ数 $g_i$ を $g_i\oplus 3$ に変えれば、全体のニム和は $0$ になる。

• $4$ 個の山（$g=1$）：目標は $1\oplus 3=2$。移り先は $3$ 個（$g=0$）、$2$ 個（$g=2$）、$0$ 個（$g=0$）なので、$2$ 個取って $2$ 個にする $1$ 通り。
• $8$ 個の山（$g=2$）：目標は $2\oplus 3=1$。移り先は $7$ 個（$g=1$）、$6$ 個（$g=0$）、$4$ 個（$g=1$）なので、$1$ 個取る手と $4$ 個取る手の $2$ 通り。
• $9$ 個の山（$g=0$）：目標は $0\oplus 3=3$。移り先のグランディ数は $g(8)=2,g(7)=1,g(5)=2$ で、$3$ になるものはないので $0$ 通り。

以上より、勝ちにつながる手は $1+2+0=3$ 通りである。

1 つの山のグランディ数 $g(n)$ を、取れる個数が $1,2,4$ として順に求める。

$g(0)=0$、$g(1)=\mathrm{mex}\{0\}=1$、$g(2)=\mathrm{mex}\{1,0\}=2$、$g(3)=\mathrm{mex}\{g(2),g(1)\}=\mathrm{mex}\{2,1\}=0$。

$g(4)=\mathrm{mex}\{g(3),g(2),g(0)\}=\mathrm{mex}\{0,2,0\}=1$、$g(5)=\mathrm{mex}\{g(4),g(3),g(1)\}=\mathrm{mex}\{1,0,1\}=2$、$g(6)=\mathrm{mex}\{g(5),g(4),g(2)\}=\mathrm{mex}\{2,1,2\}=0$。

$g(7)=\mathrm{mex}\{g(6),g(5),g(3)\}=\mathrm{mex}\{0,2,0\}=1$、$g(8)=\mathrm{mex}\{g(7),g(6),g(4)\}=\mathrm{mex}\{1,0,1\}=2$、$g(9)=\mathrm{mex}\{g(8),g(7),g(5)\}=\mathrm{mex}\{2,1,2\}=0$。

よって $g(n)=n\mathrm{mod}3$ である。

山 $4,8,9$ のグランディ数は $1,2,0$ で、全体は $1\oplus 2\oplus 0=3$。手のあとの全体を $0$ にするには、その山のグランディ数を (現在の値) $\oplus 3$ にすればよい。

• 山 4（$g=1$）: 目標は $1\oplus 3=2$。移動先は 3, 2, 0 で $g$ は $0,2,0$。個数 2 を取る手（4→2）だけが適する。1 通り。
• 山 8（$g=2$）: 目標は $2\oplus 3=1$。移動先は 7, 6, 4 で $g$ は $1,0,1$。8→7（1 個取る）と 8→4（4 個取る）が適する。2 通り。
• 山 9（$g=0$）: 目標は $3$。移動先は 8, 7, 5 で $g$ は $2,1,2$。$3$ になるものはない。0 通り。

合計は $1+2+0=3$ 通り。

検算: 4→2 のあとは $g=2,2,0$ で XOR は 0。8→7 のあとは $1,1,0$ で XOR は 0。8→4 のあとは $1,1,0$ で XOR は 0。