Ark's Blog

引っ越しました→ https://blog.arkark.dev/

ようこそ

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

競プロ

ARC087 E - Prefix-free Game

この問題の解説で

実験結果から分かるように， ${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)

は明らか

(ii)

(iii)

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

が成り立つ。