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

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

小問2の解法

　以下、図3のようにオセロの石が1列に並んでいる状態をオセロ列と呼ぶことにします。また、すべての石が白のオセロ列を白オセロ列と呼びます。

　小問2を解くにあたって、まず、以下の命題を準備しておきます。

n個の白オセロが1列に並ぶとき、n+3個の白オセロ列を生成することができる

　長さが $n$ の白オセロ列があるとき、以下の図4の手順によって、長さ $n+3$ の白オセロ列を生成することが出来ます。

　ところが、初期状態は白石1個なので、命題1より、 $n= 3m+1(m=0,1,2,\cdots )$ のとき、長さ $n$ の白オセロ列を生成できることがわかります。

　また、以下のように長さ $n= 3$ の白オセロ列を生成できます。

\begin{aligned} & \text{○} \\ & \Downarrow \\ &\text{●} -\text{○} \\ & \Downarrow \\ \text{○} - & \text{○} - \text{○} \\ \end{aligned}

　よって命題1より、 $n= 3m(m=1,2,\cdots )$ のとき、長さ $n$ の白オセロ列を生成できることがわかります。

　すなわち、自然数 $\bm n$ を3で割ったあまりが0または1であるとき、長さ $n$ の白オセロ列が生成できます。

　のこりは、 $n = 3m+2 (m=1,2,\cdots )$ の場合です。 $n =2$ のとき、白オセロ列は出来ないことから、 $n$ を3で割ったあまりが2の時は白オセロ列は出来ないと予想できますが、これの証明が超絶難問です。

　以下、本稿では、この超難問の様々な解法を紹介していきます。その上で本稿は、着想の違いによって様々なアプローチがあるものの、殆どの解法が本質的には大きく分けて2種類の解法に収斂できることを示します。

　以下の解法を取り上げます。

　これらのうち、1番目は筆者が考えた解法です。以下、各解法を順次紹介していきますが、それに先立って、証明に使う記号や命題の準備をします。