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

解法３：【史上最悪の伝説】1998年東大後期グラフ理論を丁寧に解説【理系大問3】(2020)

　本解法の基本的アイディアは、どんなオセロ列でも操作１及び操作２を繰り返すことで、白オセロ列にすることができる、というものです。

　にわかに信じがたい主張ですが、驚くべきことに、確かにそうなります。詳細は元記事（動画です）をご覧ください。

　 g \in G が図6の構造を持ち、黒オセロの数が n であるとします。このとき、本解法に従って g から生成される白オセロ列の長さは、元記事によると

\sum_{k=0}^{n-1} 2^kw_k + 3 \left [\frac{n}2 \right ]+2mod_2(n)

となります（表記法は本稿に合わせてアレンジしてあります）。ここに[]はガウスの記号です。

　 g の関数 f(g) を、この白オセロ列の長さを3で割った余りとします。すなわち、

\begin{aligned}

f(g) = & mod_3(\sum_{k=0}^{n-1} 2^kw_k + 3[\frac{n}2]+2mod_2(n))  \\
= & mod_3(\sum_{k=0}^{n-1} (-1)^kw_k +2mod_2(n))  \\
= & mod_3(\sum_{k \text{が偶数} } w_k - \sum_{k \text{が奇数} } w_k  \\
&  \text{　　　}+2mod_2(n))  \\
\end {aligned}

と定義します。この関数を使って、元記事は以下の段取りで証明を行っています。

1. f(g) は G の不変量関数であり、 g \in G ならば f(g) =0 か f(g) =1 のいずれか
2. G' = \{ 1個の黒オセロを起点に、操作1および操作2を施して生成されるオセロ列 \}
   と定義するとき、 f(g) は G ‘の不変量関数でもあって、 g \in G' ならば f(g) = 2 。すなわち、
   G \cap G' = \emptyset
3. 長さ 3m+2,m=0,1,2,\cdots の白オセロ列を wg と置くとき、は○-○ \in G' であることと命題1より、 wg \in G' である
4. ②および③より、 wg \notin G である。すなわち、長さ 3m+2 の白オセロ列は生成できない

　例によって、表記方法はアレンジされています。また、各項目の具体的な証明方法は、元記事をご参照ください。

　白オセロから生成される集合 G と、黒オセロから生成される集合 G’ が実は排他ではないかというのは、本問が登場した直後から言われていたようですが、決して自明ではありません。本解法はこれを実際に証明することで、長さ3m+2の白オセロ列が出来ないことを示しています。

　本解法の不変量関数も、本質的には解法1および解法2と同じものと言えます。本解法の不変量関数に黒オセロ数に関わる項があるのは、操作1による黒オセロ数の偶奇変動を考慮する必要があるからだと考えられます。