Ark's Blog

参加記や備忘録などを書いていきます

ようこそ

ARC087 E - Prefix-free Game のGrundy数の証明

この問題の解説

実験結果から分かるように,{g_i = }{i}を割り切る最大の2の冪)であることが示せます.

とあります。たしかに計算してみるとそうなるのですが、実際に成り立つのか気になるので証明しました。

前提

問題内容や解法については書かないのであしからず。

命題

今回のGrundy数の定義と結論は次のように表せます。

  •  {\mathbb{N} := \{0, 1, 2, \cdots\} \colon \text{非負整数全体} }
  •  {\mathrm{mex}\colon S \mapsto \min\{i\in\mathbb{N} \mid i\notin S\} \colon 2^\mathbb{N}\to \mathbb{N}\cup\{\infty\} }
  •  {^\forall n\in\{1, 2, \cdots\}, S_n := \{0\}\cup\left\{g_{n-1}\oplus g_{n-2}\oplus \cdots \oplus g_i \mid i\in\{1, \cdots, n-1\}\right\} }
  •  {^\forall n\in\{1, 2, \cdots\}, g_n := \mathrm{mex}(S_n) }

このとき

 {^\forall n, k\in\mathbb{N}, g_{2^n (2k+1)} = 2^n }

が成り立つ。

これを示したいです。

ここで、 {\mathrm{mex}}minimum excluded valueのことで \mathrm{mex}(S)は「集合Sに含まれない最小の非負整数」です。

証明

  •  g_1 = 1 ... (i)
  •  ^\forall k\in \mathbb{N} - \{0\}, g_{2k+1} = 1 ... (ii)
  •  ^\forall n, k\in\mathbb{N}, g_{2^{n+1}(2k+1)} = 2g_{2^n(2k+1)} ... (iii)

が成り立つことを示せば十分。

これを数学的帰納法で示す。(普通の帰納法ではなく、完全帰納法とか累積帰納法とか呼ばれてるやつを使います)

(i)

 g_1 = 1は明らか

(ii)

\begin{aligned}
g_{2k + 1} &= \mathrm{mex}(S_{2k+1})\\
&= \mathrm{mex}\left( \{0\} \cup \left\{g_{2k}\oplus g_{2k-1}\oplus g_{2k-2} \oplus g_{2k-3} \oplus \cdots \oplus g_i \mid i\in\{1, \cdots, 2k\}\right\}\right)\\
&= \mathrm{mex}\left( \{0\} \cup \left\{2g_{k}\oplus 1\oplus 2g_{k-1} \oplus 1\oplus \cdots \oplus g'_i
 \mid i\in\{1, \cdots, 2k\}\right\}\right)\text{ where } g'_i := \begin{cases}  1 & i \colon \mathbb{odd}  \\ 2g_{\frac{i}{2}} & i\colon\mathrm{even} \end{cases}\\
&= \mathrm{mex}\left( \{0\} \cup \left\{0\oplus 2(g_k \oplus\cdots\oplus g_i) \mid i\in\{1, \cdots, k\} \right\} \cup \left\{1\oplus 2(g_k \oplus\cdots\oplus g_i) \mid i\in\{1, \cdots, k\}  \right\}\right)\\
&= \mathrm{mex}\left( \{0\} \cup \left\{2(g_k \oplus\cdots\oplus g_i) \mid i\in\{1, \cdots, k\} \right\} \cup \left\{2(g_k \oplus\cdots\oplus g_i) + 1 \mid i\in\{1, \cdots, k\}  \right\}\right)\\
&= \mathrm{mex}\left( \{0\} \cup \{2i\mid i\in S_k - \{0\}\} \cup \{2i+1\mid i\in S_k - \{0\}\}\right)\\
&= 1
\end{aligned}

(iii)

 \begin{aligned}
g_{2^{n+1}(2k+1)} &= \mathrm{mex}(S_{2^{n+1}(2k+1)}) \\
&= \mathrm{mex}\left( \{0\} \cup \left\{g_{2^{n+1}(2k+1) - 1}\oplus g_{2^{n+1}(2k+1)-2}\oplus g_{2^{n+1}(2k+1)-3} \oplus g_{2^{n+1}(2k+1)-4} \oplus \cdots \oplus g_i \mid i\in\{1, \cdots, 2^{n+1}(2k+1)-1\}\right\}\right)\\
&= \mathrm{mex}\left( \{0\} \cup \left\{1 \oplus 2g_{2^n(2k+1)-1}\oplus 1 \oplus 2g_{2^n(2k+1)-2} \oplus \cdots \oplus g'_i \mid i\in\{1, \cdots, 2^{n+1}(2k+1)-1\}\right\}\right)\text{ where } g'_i := \begin{cases}  1 & i \colon \mathbb{odd}  \\ 2g_{\frac{i}{2}} & i\colon\mathrm{even} \end{cases}\\
&= \mathrm{mex}\left( \{0, 1\} \cup \left\{0\oplus 2(g_{2^n(2k+1)-1} \oplus\cdots\oplus g_i) \mid i\in\{1, \cdots, 2^n(2k+1)-1\} \right\} \cup \left\{1\oplus 2(g_{2^n(2k+1)-1} \oplus\cdots\oplus g_i) \mid i\in\{1, \cdots, 2^n(2k+1)-1\}  \right\}\right)\\
&= \mathrm{mex}\left( \{0, 1\} \cup \left\{2(g_{2^n(2k+1)-1} \oplus\cdots\oplus g_i) \mid i\in\{1, \cdots, 2^n(2k+1)-1\} \right\} \cup \left\{2(g_{2^n(2k+1)-1} \oplus\cdots\oplus g_i) + 1 \mid i\in\{1, \cdots, 2^n(2k+1)-1\}  \right\}\right)\\
&= \mathrm{mex}\left( \{0, 1\} \cup \{2i\mid i\in S_{2^n(2k+1)} - \{0\}\} \cup \{2i+1\mid i\in S_{2^n(2k+1)} - \{0\}\}\right)\\
&= \mathrm{mex}\left( \{2i\mid i\in S_{2^n(2k+1)}\} \cup \{2i+1\mid i\in S_{2^n(2k+1)}\}\right)\\
&= \min\{j\in\mathbb{N} \mid j\notin \{2i\mid i\in S_{2^n(2k+1)}\} \cup \{2i+1\mid i\in S_{2^n(2k+1)}\} \}\\
&= \min\{2i \mid i\in \mathbb{N} - S_{2^n(2k+1)} \}\\
&= 2\min\{i \in \mathbb{N}\mid i\notin S_{2^n(2k+1)} \}\\
&= 2\,\mathrm{mex}(S_{2^n(2k+1)})\\
&= 2g_{2^n(2k+1)}\\
\end{aligned}

以上より数学的帰納法から

^\forall n, k\in\mathbb{N}, g_{2^n (2k+1)} = 2^n

が成り立つ。