ゲーム理論の問題

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

石が $n$ 個の山のグランディ数を $g(n)$ とする。$n$ 個の山からは $n-1,n-2,n-4$ 個の山（$0$ 以上のもの）へ移れるので、$g(n)$ はそれらのグランディ数の集合の mex である。

• $g(0)=0$（動かせない）
• $g(1)=\mathrm{mex}\{g(0)\}=\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$

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

局面全体のグランディ数は各山のグランディ数のニム和である。
$$g(5)\oplus g(7)\oplus g(9)=2\oplus 1\oplus 0=3$$
$0$ でないので先手必勝である。

手順 3：ニム和を $0$ にする手を数える。

全体のニム和が $3$ なので、グランディ数 $g$ の山を、グランディ数 $g\oplus 3$ の山に変える手が勝ちにつながる手である。

• $5$ 個の山（$g=2$）：$2\oplus 3=1$ にしたい。移り先は $4,3,1$ 個で、グランディ数は $1,0,1$。よって $1$ 個取る（$4$ 個にする）手と $4$ 個取る（$1$ 個にする）手の $2$ 通り。
• $7$ 個の山（$g=1$）：$1\oplus 3=2$ にしたい。移り先は $6,5,3$ 個で、グランディ数は $0,2,0$。よって $2$ 個取る（$5$ 個にする）手の $1$ 通り。
• $9$ 個の山（$g=0$）：$0\oplus 3=3$ にしたいが、グランディ数は $0,1,2$ しか現れないので不可能。$0$ 通り。

確認：たとえば $7$ 個の山から $2$ 個取ると、$g(5)\oplus g(5)\oplus g(9)=2\oplus 2\oplus 0=0$ となる。

したがって勝ちにつながる手は $2+1+0=3$ 通りである。

1 つの山のグランディ数 $g(n)$ を、取れる個数の集合 $\{1,2,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$（4 個は取れない）
• $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$ である。

山 $5,7,9$ のグランディ数は $2,1,0$ で、全体は $2\oplus 1\oplus 0=3\ne 0$ となり、先手の勝ちの局面である。

全体を $0$ にする手を山ごとに調べる。

• 5 の山（$g=2$）: 残りの山の XOR は $1\oplus 0=1$ なので、$g=1$ の局面へ移る必要がある。$5\to 4$（1 個取る）は $g=1$ で適する。$5\to 3$（2 個取る）は $g=0$ で不適。$5\to 1$（4 個取る）は $g=1$ で適する。よって 2 通り。
• 7 の山（$g=1$）: 残りの XOR は $2\oplus 0=2$ なので、$g=2$ の局面へ移る必要がある。$7\to 6$ は $g=0$、$7\to 5$（2 個取る）は $g=2$、$7\to 3$ は $g=0$。適するのは $7\to 5$ の 1 通り。
• 9 の山（$g=0$）: 残りの XOR は $2\oplus 1=3$ だが、$g(n)\le 2$ なので $g=3$ の局面には移れない。0 通り。

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

検算: 5→4 の後は $(4,7,9)$ で $1\oplus 1\oplus 0=0$。5→1 の後は $(1,7,9)$ で $1\oplus 1\oplus 0=0$。7→5 の後は $(5,5,9)$ で $2\oplus 2\oplus 0=0$。いずれも 0 になる。