キング オブ 難問 – 1998年東大 数学 後期 第3問
- 1. 1998年東大 数学 後期 第3問 とは
- 2. 本問とグラフ理論の関係
- 3. 小問1はしっかり押さえておこう！
- 4. 1998年東大 数学 後期 大問3 小問２の攻略
- 5. n = 3m +2 （ m は非負整数）の時の証明
- 6. 証明の方針
- 7. 記号の定義
- 8. 拡張オセロ列
- 9. 不変量
- 10. 不変量関数 f(g) の導出
- 11. EG の不変量を求める
- 12. 小問２の証明
- 13. 補足１：拡張オセロ列の付加オセロが何であっても同じように証明できます
- 14. 補足２：黒オセロから生成されるオセロ列集合との排他性を利用する証明
- 15. その他の証明方法
- 16. 本問における、整数３の意味
- 17. 解法のポイントと今後の学習方針
小問２の証明
いよいよ大詰めです。これまで積み上げてきた準備の下に、小問２を証明します。
証明の流れ
以下の方針で、証明します。
- f(g) \ne 2 ならば、系2より g \notin EG である
- 操作2によってオセロ列に含まれる黒オセロ数の偶奇が変らないので、 g \in EG ならば、 g に含まれる黒オセロの数は偶数である
- 項番1および2を適用して、長さ 3m+2 の白オセロ列の両端にどのようにオセロを付加しても、 EG に含まれないことを示す
- 項番3と系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 = ●
または
o_L=● かつ o_R = ○
のケースです。
このとき、 ewg(m,o_L,o_R) の黒オセロの数は１個すなわち奇数です。
ところが、 EG の初期オセロ列 ●-○-● の黒オセロの個数は偶数であり、かつ、操作2によって黒オセロの数は2個増えるか、2個減るか、変化しないかのいずれかで、偶奇が変わりません。
すなわち、 g \in EG ならば g に含まれる黒オセロの数は偶数でなければならないので、 ewg(m,o_L,o_R) \notin EG です。
次に、
o_L=○ かつ o_R = ○
または
o_L=● かつ o_R = ●
のケースです。
このとき、以下の表１に示すように、 f(ewg(m,o_L,o_R)) \ne 2 です。
| o_L | o_R | w_0 | w_1 | w_2 | f(ewg) |
|---|---|---|---|---|---|
| 〇 | 〇 | 3m+4 | – | – | 1 |
| ● | ● | 0 | 3m+2 | 0 | 1 |
よって系２より、 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 の白オセロ列は出来ません。