ゲーム理論の問題

方針. スプレイグ・グランディの定理を使う。空きマスが $n$ 個連続した列（両端は盤の端か置かれたドミノ）を 1 つのゲームとみなし、そのグランディ数を $G(n)$ とする。$n$ 個の列にドミノを置くと、左に $a$ 個、右に $b$ 個（$a+b=n-2,a,b\ge 0$）の独立な 2 列に分かれる。分かれた 2 列の和のグランディ数は $G(a)\oplus G(b)$（$\oplus$ はビットごとの排他的論理和）なので
$$G(n)=\mathrm{mex}\{G(a)\oplus G(b)\mid a+b=n-2,a,b\ge 0\}$$
となる（$\mathrm{mex}$ は集合に含まれない最小の $0$ 以上の整数）。ドミノを置けない $n=0,1$ では $G(0)=G(1)=0$ である。

グランディ数の計算. 以下、組 $(a,b)$ の値 $G(a)\oplus G(b)$ を並べる。
- $G(2)$: $(0,0)\to 0$ より $1$。
- $G(3)$: $(0,1)\to 0$ より $1$。
- $G(4)$: $(0,2)\to 1,(1,1)\to 0$ より $2$。
- $G(5)$: $(0,3)\to 1,(1,2)\to 1$ より $0$。
- $G(6)$: $(0,4)\to 2,(1,3)\to 1,(2,2)\to 0$ より $3$。
- $G(7)$: $(0,5)\to 0,(1,4)\to 2,(2,3)\to 0$ より $1$。
- $G(8)$: $(0,6)\to 3,(1,5)\to 0,(2,4)\to 3,(3,3)\to 0$ より $1$。
- $G(9)$: $(0,7)\to 1,(1,6)\to 3,(2,5)\to 1,(3,4)\to 3$ より $0$。
- $G(10)$: $(0,8)\to 1,(1,7)\to 1,(2,6)\to 2,(3,5)\to 1,(4,4)\to 0$ より $3$。
- $G(11)$: $(0,9)\to 0,(1,8)\to 1,(2,7)\to 0,(3,6)\to 2,(4,5)\to 2$ より $3$。
- $G(12)$: $(0,10)\to 3,(1,9)\to 0,(2,8)\to 0,(3,7)\to 0,(4,6)\to 1,(5,5)\to 0$ より $2$。
- $G(13)$: $(0,11)\to 3,(1,10)\to 3,(2,9)\to 1,(3,8)\to 0,(4,7)\to 3,(5,6)\to 3$ より $2$。

初期局面. 3 枚の盤の和なので、局面のグランディ数は
$$G(6)\oplus G(10)\oplus G(13)=3\oplus 3\oplus 2=2\ne 0$$
であり、先手必勝である。必勝手とは、手を打った後の全体のグランディ数を $0$ にする手である。長さ $n$ の盤（値 $g=G(n)$）で打つとき、他の 2 枚の値の排他的論理和は $g\oplus 2$ なので、その盤を値 $g\oplus 2$ の局面に変える必要がある。

• 6 マスの盤（$g=3$）: 目標値 $3\oplus 2=1$。$G(a)\oplus G(b)=1$ となるのは $(a,b)=(1,3),(3,1)$ のみ。左端から数えて何マス目に置くかで手が決まり、$a=1,3$ の $2$ 通り。
• 10 マスの盤（$g=3$）: 目標値 $1$。上の計算より $(0,8),(1,7),(3,5)$ が値 $1$ で、左右を入れ替えたものも含めて $a\in \{0,8,1,7,3,5\}$ の $6$ 通り。
• 13 マスの盤（$g=2$）: 目標値 $2\oplus 2=0$。値 $0$ となるのは $(3,8)$ のみで、$a\in \{3,8\}$ の $2$ 通り。

したがって必勝手は $2+6+2=10$ 通りである。

各盤は、隣り合う2マスを取り除くと左右に分かれる Dawson's Kayles（八進ゲーム 0.07）と同じ構造をもつ。長さ $n$ の盤のグランディ数を $g(n)$ とする。

$g(0)=g(1)=0$ で、$g(n)=\mathrm{mex}\{g(a)\oplus g(b):a+b=n-2,a,b\ge 0\}$ により順に求める。
$g(2)=1,g(3)=1,g(4)=2,g(5)=0,g(6)=3,g(7)=1,g(8)=1,g(9)=0,g(10)=3,g(11)=3,g(12)=2,g(13)=2$。

初期局面のグランディ数は $g(6)\oplus g(10)\oplus g(13)=3\oplus 3\oplus 2=2\ne 0$ なので先手必勝である。

必勝手は、手の後の全体のグランディ数が $0$ になる手である。左右に残るマスの数を $(a,b)$（$a+b=n-2$）とする。

• 盤6：他の盤の xor は $3\oplus 2=1$ なので、新しい値が $1$ になればよい。
• $(0,4)$：$0\oplus 2=2$
• $(1,3)$：$0\oplus 1=1$ ○
• $(2,2)$：$0$
• $(1,3)$ は左右反転した $(3,1)$ も含めて 2 通りが該当する。
• 盤10：他の盤の xor は $3\oplus 2=1$ なので、新しい値が $1$ になればよい。$a+b=8$ の各分割は次のとおり。
• $(0,8)$：$0\oplus 1=1$ ○
• $(1,7)$：$0\oplus 1=1$ ○
• $(2,6)$：$1\oplus 3=2$
• $(3,5)$：$1\oplus 0=1$ ○
• $(4,4)$：$0$
• 該当する分割 3 種はそれぞれ左右反転も別の手なので、$3\times 2=6$ 通り。
• 盤13：他の盤の xor は $3\oplus 3=0$ なので、新しい値が $0$ になればよい。$a+b=11$ の各分割は次のとおり。
• $(0,11)$：$0\oplus 3=3$
• $(1,10)$：$0\oplus 3=3$
• $(2,9)$：$1\oplus 0=1$
• $(3,8)$：$1\oplus 1=0$ ○
• $(4,7)$：$2\oplus 1=3$
• $(5,6)$：$0\oplus 3=3$
• 該当するのは $(3,8)$ とその左右反転の 2 通り。

合計は $2+6+2=10$ 通りである。