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

2021年5月3日2023年12月11日

補足１：拡張オセロ列の付加オセロが何であっても同じように証明できます

　本稿では拡張オセロ列集合 EG を定義するにあたって、最初の白オセロの両端に黒オセロを接続しましたが、両端につなげるオセロの色は何であっても、同じように証明できます。

　初期オセロ〇の両端に付加するオセロ O_L,O_R の値によって、 EG の初期要素 g_0 = O_L - 〇 -O_R 、 EG の黒オセロ数の偶奇、および f(g_0) の値は、以下の値を取ります。

　EGの黒オセロの数が偶数の時、その不変量 f(g_0) は上表のとおり、0か2のいずれかです。一方、 ewg(m,o_L,o_R) \in EG が成り立つためには、 ewg(m,o_L,o_R) の黒オセロ数が偶数でなければならないため、 o_L,o_R が両方〇か両方●である必要がありますが、このとき、

ewg( m, ○,○ ) = \overbrace {\text{〇}- \text{〇}- \cdots - \text{〇} }^{3m+4 \text{個} }

または

ewg( m, ●,● ) = ● - \overbrace {\text{〇}- \text{〇}- \cdots - \text{〇} }^{3m+2 \text{個} }- ●

であり、いずれの場合も f(ewg(m,o_L,o_R)) = 1 なので、 ewg(m,o_L,o_R) \notin EG です。

　また、EGの黒オセロの数が奇数の時、その不変量 f(g_0) は上表のとおり、1か2のいずれかです。一方、 f(ewg(m,o_L,o_R)) \in EG が成り立つためには、 ewg(m,o_L,o_R) の黒オセロ数が奇数でなければならないため、 o_L,o_R の一方は○、もう一方は●である必要がありますが、このとき、

ewg( m, ○,● ) = \overbrace {\text{〇}- \text{〇}- \cdots - \text{〇} }^{3m+3 \text{個} } - ●

または

ewg( m, ●,○ ) = ● - \overbrace {\text{〇}- \text{〇}- \cdots - \text{〇} }^{3m+3 \text{個} }

であり、いずれの場合も f(ewg(m,o_L,o_R)) = 0 なので、 ewg(m,o_L,o_R) \notin EG です。

補足２：黒オセロから生成されるオセロ列集合との排他性を利用する証明

　1つの黒オセロを起点に、操作1と操作2を施して生成したオセロ列集合を G' とするとき、明らかに 〇-〇 \in G' なので、命題1より、すべての非負整数 m に対し、個数 3m+2 の白オセロ列 wg(m) は G' の要素です。

　ここで G \cap G' = \empty が成り立てば、 wg(m) \notin G が証明できたことになります。ネット上にはこれを無証明で使用している例もありますが、筆者は証明が必要と考えています。

　 G \cap G' = \empty の証明は、不変量関数を以下のように黒オセロ数を考慮した形にすると、少し手間はかかりますが本稿と同様の手法でできます。

f(g)  =  \sum_{k \text{が偶数} } w_k - \sum_{k \text{が奇数} } w_k  + b   \mod  3 

　ここで b は、 g に含まれる黒オセロの総数を2で割った余りです。

その他の証明方法

　ネットをググると、本問に対するいろいろな証明を見出すことが出来ます。以下の記事でそれらを紹介していますので、是非ご覧ください。

伝説の超難問のいろいろな解法 – 1998年東大後期理系第3問

本問における、整数３の意味

　本問において、整数3は重要な意味を持っています。小問2の解答がそもそもmodulo 3だし、証明においてもmodulo 3が重要な役割を担っています。

　これらは偶然の一致かというとそうではなく、操作2で、挿入したオセロとその両隣の計3つが動くことに起因しています。これが仮に、挿入したオセロの左右2つずつを反転させる、という問題で有ったら、おそらく違う結果になっていたでしょう。

　ただ、3という数字が固有に持つ、何か整数論的な背景が影響している、というわけではなさそうです。

解法のポイントと今後の学習方針

　本問を解くにあたってのポイントは、以下の2点に集約されます。

1. 題意の拡張による一般化（「拡張オセロ列」）
2. 発想の転換による、統一的法則性の発見（不変量関数導出における、奇数項の符号反転）

　これらの両方を試験中に思いつけるかどうかが、死活的に重要です。どちらか一方でも証明できないことはありませんが、ものすごい手間が必要になります。以下、思いつき方のヒントと、どのようにすれば思いつけるようになるのかを、考察してみます。

　項番1は本問では非常に有用でしたが、一般化するのはいささか難しいところがあります。しかし、問題を解いていて、「この条件が無ければすんなり解けるのに」などというようなケースに遭遇した時に、今回のような考え方が役立つことがあります。まずは、過去において回答に苦労した問題の中に、このようなアプローチが有用なものがないかどうか、探してみるのが良いと思います。

　項番2については、本問のような逐次処理タイプの問題では、modulo計算によって答えを得るケースがままあります。もし本問のように、modulo計算にうまくあてはめられないなどというケースに遭遇した場合、符号反転のようなちょっとした工夫が打開の糸口になるかもしれない、と念頭に置いておくことは、有用であると考えます。普段の勉強方針としては、modulo系の問題（10005番目の数字が13で割り切れることを証明せよ、みたいなやつ）を多く解くようにしておくと、良いでしょう。