伝説の超難問の解法まとめ – 1998年東大 数学 後期 第3問

2022年4月1日2024年3月11日

解法４：【伝説の東大入試】なんと中学レベルの数学で解けるぞ！【徹底解説】(2021)

　本解法では拡張オセロ列 EG を使用します。拡張オセロ列の初期要素を

○－〇－○

とします。

　本解法の不変量関数導出方法は、ちょっと意表をついています。オセロ列において、左側に黒オセロが自分も含めて奇数個ある石の数を3で割った余りを、不変量関数と定義します。詳細は元記事をご確認ください。

　これを本稿の流儀に従って記述すると、 g \in \mathfrak{G} が図6の構造を持つとき、

  f(g) =mod_3 ( \sum_{k \text{が奇数} } (w_k  +1) )

と表記できます。

　このとき、 元記事は以下の段取りで証明を行っています。

　このとき、 元記事は以下の段取りで証明を行っています。

1. g \in EG かつ g の長さが 3m+2+2 =3m+4(m=0,1,2,\cdots) のとき、 f(g) =2 である
2. wg \in \mathfrak{G} を長さ 3m+2 の白オセロ列とする。 wg の両端にオセロ石 o_L,o_R を付加するとき、 o_L,o_R をどのように選んでも、 f(o_L-wg-o_R) は0か1のいずれかであり、したがって o_L-wg-o_R \notin EG である
3. ゆえに命題2により、 wg \notin G である。すなわち長さ3m+2の白オセロ列は生成できない

　ずいぶんすっきりとした証明です。なお、毎度のことながら、表記方法はアレンジされています。また、項番①および②の証明は元記事をご参照ください。

　本解法の不変量関数は奇数番の白オセロ群のみ考慮しているのが、意表をついています。偶数番を考慮しなくて良いのか気になるところですが、 g \in EG のとき

mod_3 (\sum_{k \text{が偶数} } w_k - \sum_{k \text{が奇数} } w_k   )

が常に一定の値であること（解法４と解法１は EG の初期オセロが異なりますが、解法４のEGの場合でも同様に証明できます）と、nを黒オセロの数とするとき、

  \begin{aligned}
\sum_{k \text{が奇数} } (w_k  +1)  & = \sum_{k \text{が奇数} } w_k  + \frac{n}2 \\
\sum_{k \text{が偶数} } (w_k  +1)  & = \sum_{k \text{が偶数} } w_k  + \frac{n}2 + 1
\end{aligned}

である（初期オセロ列の黒オセロ数が0なので、EGのすべての要素の黒オセロ数 n は常に偶数であることに注意）ことから、

\begin{aligned}
& \sum_{k \text{が偶数} } w_k - \sum_{k \text{が奇数} } w_k    \\
= & \sum_{k \text{が偶数} } w_k + \frac{n}2 + 1-1- \sum_{k \text{が奇数} } w_k -  \frac{n}2   \\
= & \sum_{k \text{が偶数} }( w_k + 1)-1 - \sum_{k \text{が奇数} } (w_k +1)
\end{aligned}

が成り立つので、奇数番だけ考慮しても問題ないことがわかります。