キング オブ 難問 – 1998年東大 数学 後期 第3問

小問２の証明

　いよいよ大詰めです。これまで積み上げてきた準備の下に、小問２を証明します。

証明の流れ

　以下の方針で、証明します。

1. f(g) \ne 2 ならば、系2より g \notin EG である
2. 項番1を適用して、長さ 3m+2 の白オセロ列の両端にどのようにオセロを付加しても、 EG に含まれないことを示す
3. 項番2と系1より、長さ 3m+2 の白オセロ列が G に含まれないことが導出できる

記号の定義

　任意の非負整数 m に対し、オセロ列 wg(m) \in \mathfrak{G} を、 3m+2 個の白オセロが一列に並んだオセロ列であると定義します。

　また、２つのオセロ o_L,o_R \in \{ 〇、● \} に対し、オセロ列 ewg(m,o_L,o_R) \in \mathfrak{G} を、 wg(m) の左右にそれぞれ o_L と o_R を接続したオセロ列であると定義します。イメージは以下の通りです。

o_L-  \overbrace {\text{〇}- \text{〇}- \cdots - \text{〇}  }^{3m+2 \text{個} }-o_R

　以下、すべての非負整数 m に対し、 o_L,o_R \in \{ 〇、● } をどのように選んでも、 ewg(m,o_L,o_R) \notin EG であることを証明します。もしこれが成り立てば、系1より、 wg(m) \notin G が証明できたことになります。

o_{_L},o_{_R} ∈ { 〇、● } をどのように選んでも、 ewg(m,o_{_L},o_{_R}) ∉ EG であることの証明

　ところが以下の表１に示すように、o_{_L},o_{_R} ∈ { 〇、● } をどのように選んでも f(ewg(m,o_L,o_R)) \ne 2 です。

よって系２より、 ewg(m,o_L,o_R) \notin EG です。

結論

　以上、すべての非負整数 m に対し、 o_L,o_R \in \{ 〇、● } をどのように選んでも、 ewg(m,o_L,o_R) \notin EG であることが証明できました。

　ゆえに、すべての非負整数 m に対し、 wg(m) \notin G です。すなわち、長さ 3m+2 の白オセロ列は出来ません。