ゲーム理論の問題

方針 $n=0$ から順に、$g(n)=\mathrm{mex}\{g(n-2),g(n-3)\}$ を計算して表にします。ただし $n-2$ や $n-3$ が負になる手は打てないので、集合から除きます。

小さい局面から順に計算する

• $g(0)$：動かせないので $g(0)=0$。
• $g(1)$：2 個も 3 個も取れないので $g(1)=0$。
• $g(2)=\mathrm{mex}\{g(0)\}=\mathrm{mex}\{0\}=1$。
• $g(3)=\mathrm{mex}\{g(1),g(0)\}=\mathrm{mex}\{0\}=1$。
• $g(4)=\mathrm{mex}\{g(2),g(1)\}=\mathrm{mex}\{1,0\}=2$。
• $g(5)=\mathrm{mex}\{g(3),g(2)\}=\mathrm{mex}\{1\}=0$。
• $g(6)=\mathrm{mex}\{g(4),g(3)\}=\mathrm{mex}\{2,1\}=0$。
• $g(7)=\mathrm{mex}\{g(5),g(4)\}=\mathrm{mex}\{0,2\}=1$。
• $g(8)=\mathrm{mex}\{g(6),g(5)\}=\mathrm{mex}\{0\}=1$。
• $g(9)=\mathrm{mex}\{g(7),g(6)\}=\mathrm{mex}\{1,0\}=2$。

表にすると次のようになります。

$$\begin{array}{ccccccccccc}n& 0& 1& 2& 3& 4& 5& 6& 7& 8& 9\\ g(n)& 0& 0& 1& 1& 2& 0& 0& 1& 1& 2\end{array}$$

周期を見つける

$g(n)$ は $g(n-2)$ と $g(n-3)$ だけで決まります。$g(5),g(6),g(7)=0,0,1$ が $g(0),g(1),g(2)=0,0,1$ と一致したので、$g(8)$ 以降も $g(3),g(4),\dots$ と同じ値が繰り返されます。したがって、$n\ge 0$ のすべてで $g(n+5)=g(n)$ が成り立ちます。つまり $g(n)$ は周期 $5$ で
$$0,0,1,1,2$$
を繰り返します。

$g(24)$ を求める

$24=5\times 4+4$ なので、$g(24)=g(4)=2$ です。

答え：$2$

$g(n)=\mathrm{mex}\{g(n-2),g(n-3)\}$ とする。ただし、山に残る石の個数が足りず取れない手は除く。

順に計算する。
- $g(0)=0$、$g(1)=0$（動けない局面）
- $g(2)=\mathrm{mex}\{g(0)\}=\mathrm{mex}\{0\}=1$
- $g(3)=\mathrm{mex}\{g(1),g(0)\}=\mathrm{mex}\{0\}=1$
- $g(4)=\mathrm{mex}\{g(2),g(1)\}=\mathrm{mex}\{1,0\}=2$
- $g(5)=\mathrm{mex}\{g(3),g(2)\}=\mathrm{mex}\{1\}=0$
- $g(6)=\mathrm{mex}\{g(4),g(3)\}=\mathrm{mex}\{2,1\}=0$
- $g(7)=\mathrm{mex}\{g(5),g(4)\}=\mathrm{mex}\{0,2\}=1$
- $g(8)=\mathrm{mex}\{g(6),g(5)\}=\mathrm{mex}\{0\}=1$
- $g(9)=\mathrm{mex}\{g(7),g(6)\}=\mathrm{mex}\{1,0\}=2$
- $g(10)=\mathrm{mex}\{g(8),g(7)\}=\mathrm{mex}\{1\}=0$
- $g(11)=\mathrm{mex}\{g(9),g(8)\}=\mathrm{mex}\{2,1\}=0$

$g(5),\dots ,g(9)$ は $g(0),\dots ,g(4)$ と同じ値 $0,0,1,1,2$ である。$g(n)$ は直前の 3 項までで決まるので、$g(n+5)=g(n)$ となる周期 5 の数列になる。実際に $g(10)=g(0)$、$g(11)=g(1)$ も成り立っている。

周期は $n\mathrm{mod}5=0,1,2,3,4$ に対して $0,0,1,1,2$ である。$24\equiv 4(\mathrm{mod}5)$ なので $g(24)=2$。