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

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

解法８：1998年東大後期理系数学第3問には超簡単な解法があるのです！(2022)

　本解法は他の解法とは異なり、証明に不変量関数を必要としません。驚くべき画期的な証明法ですが、どのようなものなのでしょうか。

　例によって、表記方法は本稿固有の表記にアレンジされています。

　使用する記号を、改めて定義します。

G = \{ 1個の白オセロを起点に、操作1および操作2を施して生成されるオセロ列 \}

G' = \{ 1個の黒オセロを起点に、操作1および操作2を施して生成されるオセロ列 \}

　また、オセロ列 g \in \mathfrak G に操作1または操作2を施すことを、「 \text{操作} (g) 」と表記します。

　このとき、 元記事は以下の段取りで証明を行っています。

1. 操作１及び操作２には、それぞれ逆操作が定義できる
2. G の各要素に操作と逆操作を有限回施して得られる集合を CG と表記するとき、定義から明らかに、 G \subset CG が成り立つが、 操作と逆操作は CG 上で閉じている
3. したがって、 g \notin CG なら \text{操作} (g) \notin CG である
4. CG は1個の白オセロから生成されるが、1個の黒オセロは CG の要素ではない。よって③により、1個の黒オセロにどのような操作を施しても CG の要素になることはない
5. したがって CG \cap G' = \emptyset なので G \cap G' = \emptyset が成り立つ
6. 長さ 3m+2,m=0,1,2,\cdots の白オセロ列 wg はすべて G’ の要素なので、 wg \notin G である。すなわち、長さ 3m+2 の白オセロ列は生成できない

　元記事では④の主張「1個の黒オセロは CG の要素ではない」を自明のこととして無証明で記述してありますが、これはあまり自明でない気がします。

　G’ の各要素に操作と逆操作を有限回施して得られる集合を CG' と表記するとき、1個の黒オセロ●が CG の要素ではないことと、 CG \cap CG' = \empty が成り立つことは同値です。まず、 CG \cap CG' = \empty なら1個の黒オセロが CG の要素ではないことは明らかです。

　逆に CG \cap CG' \ne \empty であるとき、 g_0 \in CG \cap CG' に対して一連の \text{操作}_{b\_1},\text{操作}_{b\_2}, \cdots , \text{操作}_{b\_k} が存在して、

g_0 = \text{操作}_{b\_k}(\text{操作}_{b\_k-1}( \cdots(\text{操作}_{b\_1}(\text{●}) \cdots))

が成り立ちます。

　したがって、

 \text{●} = \text{操作}_{b\_1}^{-1}(\text{操作}_{b\_2}^{-1}( \cdots(\text{操作}_{b\_k}^{-1}(g_0) \cdots))

が成り立ちます。 g_0 \in CG なので、1個の黒オセロ●は CG の要素です。以上、1個の黒オセロ●が CG の要素ではないことと、 CG \cap CG' = \empty が成り立つことが同値であることが証明できました。

　ここで再び項番④に戻ります。1個の黒オセロ●が CG の要素でないということは、●に有限回の操作、逆操作をどのように施しても○になることはない、ということで、一見自明に見えますが、実際は CG \backslash G は空集合ではないのでそれほど自明ではありません。

　たとえば ●-● は G の要素ではありませんが、操作2によって ○-○-○ ∈ G ⊂ CG になるので CG \backslash G の要素です。このような「G の要素でないが操作した結果 G の要素になる」 オセロ列が存在するので、そのようなオセロ列のすべてが CG' の要素でないことが証明できないと CG \cap CG' = \empty が成り立たず、これと同値である「1個の黒オセロ●が CG の要素ではない」ことは証明できません。

　以上のように、「1個の黒オセロ●は CG の要素でない」ための必要条件が「G の要素でないが操作した結果 G の要素になるすべてのオセロ列に対し、どのように操作、逆操作を施しても●にならないこと」という、あまり自明ではないかなり厳し目なものなので、やはり何らかの証明が必要であると考えています。

解法9：1998年の東大後期数学のグラフ問題の解答例(2023)

　本解法は解法4などのような、不変量関数が

   \sum_{k \text{が奇数} } (w_k  +1) 

タイプの解法です。

　本解法は拡張オセロ列方式を採用していません。また、図または説明が一部欠落していてちょっとわかりにくいのですが、おそらく以下の段取りで証明していると思われます。

　オセロ列 g \in \mathfrak{G} に対し、不変量関数 f(g) を、解法4などと同様に

  f(g) =mod_3 ( \sum_{k \text{が奇数} } (w_k  +1) )

と定義します。ここに w_k は g を構成する白オセロ群の個数です（図6参照）。このとき、

1. オセロ列 g \in G の長さが n のとき、 f(g) = mod_3(2n) が成り立つ
2. 白オセロ列 wg \in G の長さが n のとき、 f(wg) =0 または f(wg) = mod_3(n+1) のいずれかが成り立つ
3. ①および②により、 mod_3(2n) = 0 または mod_3(2n) = mod_3(n+1) が成り立つ。これはすなわち
   　 2n \equiv 0( \mod 3) または
   　 2n \equiv n+1 ( \mod 3)
   が成り立つことと同義であり、n は3で割り切れるか、3で割った余りが1のいずれかである

となります。項番①および項番②の詳細は、元記事を参照願います。

　本稿では白オセロ群の項番を0から振っているのに対し、本解法の元記事では1から振っています。このため、本稿と元記事とで白オセロ群項番の偶奇が反転していますのでご注意ください。

　また、本解法は拡張オセロ列方式を採用していないので、オセロ列の左端に操作1を施すと白オセロ群項番の偶奇が入れ替わってしまいます。これを防ぐため、元記事に説明はありませんが、左端に施す操作1の個数に応じて項番の振り方を調整していると思われます。

　白オセロ列 wg はすべての石が白なので、白オセロ群は１つしかありません。にもかかわらず解法の項番②で f(wg) の値が2通りあるのは、白オセロ群項番調整の影響で、 wg の白オセロ群の項番が偶数である場合と奇数である場合が存在するからであると考えられます。

解法10：1998年東大入試後期日程、数学問3（2）の件(2010)

　本解法は、ネット上で見つけられた中では最も古いものです。しかも、数学的帰納法によって解くという、これまでにない斬新な解法です。どのような解法なのでしょうか。

　基本的な証明方針は、拡張オセロ列方式です。したがってオセロ列への操作は、操作2のみを考慮します。

　例によって、表記方法は本稿固有の表記にアレンジされています。

　まず記号の準備です。オセロ石 o_L,o_R に対し、

EG(o_L,o_R ) = \{ o_L －〇－ o_R から操作2のみを施して生成された拡張オセロ列 \}

と定義します。また、

\begin{aligned}
EEG = EG( \text{○,○})\cup EG( \text{●,○}) \\ \cup EG( \text{○,●})\cup EG( \text{●,●}) 
\end{aligned}

と定義します。

　以上の準備のもとに、本解法では以下の命題を、オセロ列の長さ n に関する数学的帰納法によって証明します。

命題3

　元記事では以下の段取りで証明しています。

　拡張オセロ列 g \in EEG の各石に左から1,2,3,・・・と番号を振り、 k 番目の石を o_k と表記するとき、

1. n \leqq 4 のときは成り立つ
2. n \geqq 5 のとき、長さ n の白オセロ列 wg に対する拡張オセロ列 g = o_L-wg-o_R が EEG の要素であるとする。 g の左から2つ目のオセロ石 o₂ が操作2によって g に挿入された時の、 o₂ の右隣の石をo_k ( 3 ≦ k ≦ n+2 ) と置くとき、 o_k の右側に対する操作2と左側に対する操作2は各々、反対側に影響を及ぼさないので可換である。したがって o₂ が挿入されるタイミングで o_k の右側に対する操作2は終了しているとして一般性を失わない。このとき、 g は以下のように表記できる：
   o_L - o_2 -o_k- \overbrace {\text{○} -\text{○} - \cdots - \text{○}-o_R }^{(n-k+2) \text{個}}
3. o₂ と o_k の間に最初の操作2が施された後のオセロ列は
   o_L - \overline{o_2} - \text{○} - \overline{o_k}- \overbrace {\text{○} -\text{○} - \cdots - \text{○}-o_R }^{(n-k+2) \text{個}}
   挿入直後のo₂ は白、反転後の \overline{o_2} は黒である
4. すべての操作が終了した後のオセロ列は
   o_L - \overbrace {\text{○} -\text{○} - \cdots - \text{○} }^{(k-1) \text{個}} - \overbrace {\text{○} -\text{○} - \cdots - \text{○}-o_R }^{(n-k+2) \text{個}}
   であるが、
   \overbrace {\text{○} -\text{○} - \cdots - \text{○} }^{(k-1) \text{個}} \in EG( \text{●},\overline{o_k})
   なので、帰納法の仮定により、 k -3 は3の倍数でかつ、 \overline{o_k} は黒である
5. よって、 o₂ 挿入直後のオセロ列は
   o_L - \text{○} -\text{○} - \overbrace {\text{○} -\text{○} - \cdots - \text{○}-o_R }^{(n-k+2) \text{個}}
   であるが、 o_L,o_R に挟まれた白オセロ石の数は n – k +3 個である。 k は3の倍数であったので、帰納法の仮定により n は3の倍数であるか、3で割った余りが1である。また、同じく帰納法の仮定により、n を3で割った余りが１なら
   o_L - wg -o_R \in EG(o_L,o_R)
   n が3の倍数なら
   o_L - wg -o_R \in EG(\overline{o_L}, \overline{o_R})
   が成り立つ

なんかいい感じですが、1つ気になるのは、項番⑤で操作を遡って縮退させたオセロ列に帰納法の仮定を適用していることです。これができるのは、縮退オセロ列

o_L - \text{○} -\text{○} - \overbrace {\text{○} -\text{○} - \cdots - \text{○}-o_R  }^{(n-k+2) \text{個}}

が EEG の要素であるという前提があるからですが、これは自明ではありません。これは EEG の要素でないオセロ列 g に操作2を施して、 \text{操作2}(g) \in EEG となる場合があるからで、たとえば

○-●-●-○

は EEG の要素ではありませんが、これの中央に白オセロを挿入すると

\text{○} - \text{○} - \text{○} - \text{○} - \text{○} \in EG(\text{○,○} ) \subset EEG

が成り立ちます。

　したがって、項番⑤で縮退オセロ列が EEG の要素であることを明示的に証明する必要があると思います。

本問の解法パターンは本質的に2種類

　以上のように、解法８、解法10以外の本問の証明の中核である不変量関数は、本質的に

  \sum_{k \text{が偶数} } w_k - \sum_{k \text{が奇数} } w_k   

タイプか、

   \sum_{k \text{が奇数} } (w_k  +1) 

タイプのいずれかです。操作１及び操作2による白オセロ数の増減のパターンから見て、不変量関数を用いる証明として、上記２パターン以外の画期的な解法が今後現れるというのは、多分無いだろうと考えています。

　解法８及び解法10は不変量関数を用いていませんが、どちらも「G の要素でないが操作した結果 G の要素になるオセロ列」に関するある種の性質を無証明で使用しています。筆者は何らかの証明が要るのではないかと考えています。

　史上最強と言われる本問も、不変量関数がわかってしまえばどうということはありません。結局のところ本問の難しさは、特段のヒントもない中、どうやって不変量関数を着想できるかという点に有ります。

　後期試験なので、数学的才能に特に秀でた学生を採りたい、という意図が出題者にはあったのかも知れませんが、この難易度はどう見てもやり過ぎです。もしかして出題者は、現に今そうなっているように、後世に残る不滅の金字塔的ネタ化を狙っていたのかも知れません（そんな訳ない）。