ジェイラボワークショップ第40回『東大最難問解法展覧会』【数学部】[20220912-0925] #JLWS


この記事は、私が所属している「ジェイラボ」というコミュニティ内で行われたワークショップのログです。


以下、★マークを辿ればストーリーとして今回のワークショップを追体験することができるようになっています。今回はほぼほぼ本筋から逸れなかったため、ほぼ全てが★マークですが。

1日目

★Hiroto

こんばんは。数学部部長のHirotoです。よろしくお願いします。今回のテーマは、『東大最難問解法展覧会』です。東大受験数学史上最難問と呼ばれている問題の、解法を、展覧します。
○スケジュール
1週目:『準備』
・問題発表と目的説明
・前提の解きほぐし
・(1)の解答
以下(2)に取り組む。
・実験の大切さ
・すぐわかる十分条件
・やばい必要条件(某予備校の犯した誤答)
・2つの武器
・3人の試行錯誤
2週目:『解』
・Hiroto
・ブログ①
・所長
・たまき(環耀)
・ブログ②
・ブログ③

○それぞれの取り組み方
・数学そのものにある程度親しみがある方
思う存分楽しんで解いてみてください。1週目はヒントを段々と投下していくつくりになっているため、見て頂くもよし。あえて見て頂かないのもよし。とにかく楽しんでみてください。何か進捗があればいつでも投下を待っています。2週目以降の怒涛の解答ラッシュも、内容を理解してみてください。
・数学そのものにあまり親しみがない方
今回は、、、、小学生でも問題を理解することができます!!!!!実は最難問とはいえ、前提となる知識はなにもいらないのが今回のおもしろポイントです。今回のWSは数学的側面の真正面から取り組んでみるのも一興かと思います。
もちろん、その気がなくとも楽しめるストーリー構成にはしてありますゆえ、そちらの方をメタ的に楽しんでいただくのでも良いと思います。

★Hiroto

準備その1『問題を理解せよ』
https://examist.jp/legendexam/1998-tokyo/
上のリンクに問題も、逸話も、載っています。が、一応問題画像を投下いたします。(追記:noteには載せません。上ブログなどからご参照ください。)逸話も引用させていただくと、、

誰もが入試史上最難問と認める問題がある.東大が本気を出していた97~98年にその問題は現れた.数学オリンピックに出題されても解ける人はいないだろうと言われたその問題は1998年東京大学後期数学第3問.長いので問題文は省略するが,ネットでもそこらじゅうに転がっているので,一度見てみるといい.グラフ理論を題材にしたこの問題では答えはすぐに分かる.しかし論証は最強の難問で,完答者はゼロ.私は当時勤めていた予備校にいた.私がいた予備校は後期日程に関しては解答速報を出さないため,私は個人的にせっせと解いていた.しかし,第3問で鉛筆が止まる.1時間以上考えたが論証が思いつかない.横で解いていた同僚も同じ.相当な難問だと思っていたが,さすがに大手予備校はもう解けているだろうと思い,河合塾で働く友人に電話する.しかし,河合塾はまだ解けていなかった.大手予備校は東大の解答速報を当日にだす.しかし,どの予備校もなかなか解答速報が出ない.河合塾はその日の解答作成を断念,翌日にまわすことになったが,それでも解けなかったらどうしようと悩んだらしい.駿台も手も足も出ず,解答作成を急遽大数の安田先生に依頼した.事態を把握してようやく,これは入試史上過去に例がないほどの超難問であると理解し,国際数学オリンピックメダリストの友人に電話する.ちょうど彼も別の予備校から依頼を受けて問題を解いている最中だった.その後,かなりの時間を要して友人は解答を出してくれた.当時の東大は何がやりたかったのだろうかといまだに思う.97年・98年は前期後期ともDレベルの難問が続出(6題中Dレベルが3題,Cレベルが3題というセットもあった).たった2時間半では全完できた人は一人もいなかったであろう.良問もあったが,あれほど難しくしては差はほとんどつかない.東大後期で数学がなくなった現在ではあのような難問が出題されることはあるまい.東工大AO入試も難問が多いとはいえ,本問に比べればはるかに簡単であろう.無理のない難問にレベルが抑えられ,適度に差がつくようになったが,たまに難問が大量に出題されていた当時を振り返り懐かしむことがある.
https://maidskii.tumblr.com/post/3582802010/誰もが入試史上最難問と認める問題がある東大が本気を出していた97-98年にその問題は現れた
より引用


だそうです。
解くとかはひとまず置いておき、とりあえず問題を理解してみてください。文章は長いですが、意外と単純です。

2日目

★Hiroto

どうでしょうか?問題は理解できましたでしょうか。
長ったらしく書いてありますが、これは数学的に"しっかり"前提を書いてくれているからで、結局言いたいのはこの画像のようなことです。ぜひ目を通してみてください。

★Hiroto

準備その2『(1)にて手を動かそう』
それでは皆さん、(1)を解いてみましょう。この問題で最難問なのは(2)であって、(1)は本当に、マジの、ガチで、誇張なく、算数パズルです。10分あれば出来る人は出来ると思われるため、取り組んでみてください。
今日の深夜、解答を投下いたします。それまでに投下できそうな方、バンバンやっちゃってください(ネタバレ嫌な方は他の方の解答を見ないように自衛頼みます)。

3日目

★Hiroto

まだ解答出てないですが、僕のを出しちゃいます。こんな感じです。数学部の皆さんにも解いてもらいましたが、ここまでは皆さん順調でした。
この時点で一つの教訓
「難しそうだからといって、(1)から諦めるな」
を得ることができました。一点を争う受験では肝に銘じたい教訓ですね。

4日目

★Hiroto

準備その3『実験の大切さ』
(2)は、正直テンプレで解答が出せる類の問題ではなく、ある程度の試行錯誤が必要です。
数学における試行錯誤とは何か。今回は「実験と観察」が試行錯誤の大部分を担います。
「実験と観察は自然科学のもので、数学のものではない」? たしかに、自然科学の意味での実験とは意味が異なります。「具体的な計算」とでも言い換えれば良いでしょうか。
ひとまず、具体的な計算の具体例として、今回僕が行なった実験をご覧ください。

実験の過程で、「nを3でわった余りが0,1なら、n個の白頂点からなる棒状グラフは可能グラフ」(可能グラフとなるための十分条件)が示されています。そして、「そうでないなら可能グラフではないっぽい」ということも実験により示唆されています。
今回は棒状グラフが可能グラフになるためのnの必要十分条件(完璧に等価な条件)を求めたいため、上の「っぽい」を厳密に示す必要があります。そして、この(2)が難問たる所以はここにあります。((1)に関しては、数学部の部員の方々も到達している人が多かったです。)

★Hiroto

準備その4『教育的な誤答』
さあ!ついにこの東大最難問の解答一つ目です!!!、、、と言いたいところなのですが、これは誤答(というか明らかに議論が足りない)です。某予備校がこの方針で解答を出したようなのですが、皆さんはどこに誤り(というよりギャップ)があるのかわかるでしょうか??

5日目

■けろたん

n=1の黒丸と白丸に同じ回数だけ操作を適用してできるグラフは(2^n以下の数で)たくさんありますが、黒丸から派生したグラフと白丸から派生したグラフで頂点の数が同じもので、グラフに被りが一つもないというのは証明する対象のように思います。
(うまい言い方がわからずなんだか冗長な書き方になってしまいました。現在(2)をやっているのですがそこが難しくて苦労しています。→挫折して別の方針でやっています。)

↪︎Hiroto

取り組んでくださりありがとうございます!!
やっぱりそこにギャップ感じますよね、、。明日改めて投下しますので、お待ちください。

★Hiroto

何が誤りだったのか。赤文字で書いてあります。
そんなに自明でないことをあたかも「当然ですよね?」というように書いてありますが、これは説明不足です。示されなければなりません。

★Hiroto

準備その5『2つの武器』
ここまでの議論から、さすがにただ表面をいじくってるだけではしっかりと「示す」ことはできなさそうだという直感が働くと思います。
ということで、いくつかの数学的な武器をみなさんに提供させていただきたいと思います。その武器とは、
・(数学的)帰納法
・不変量
です。
一つ一つは難しい概念ではないため、具体例とともに納得していただければと思います。

6日目

★Hiroto

準備その6『3人の試行錯誤』
ここから、じわじわと(2)の核心に迫っていきます。
まずは、数学部で(2)に取り組んでくださった人の中から僕がバランスよく選んだ3人に、どのように(2)を解こうとしたかをお聞きしたいと思います。一人目は@chiffon cake さんです。面倒なところも含めて、思考の言語化をよろしくお願いいたします。

★chiffon cake

本文は夜に投下します。

★chiffon cake

前書き
 おそらく私が受験生のときに入試問題で遭遇したら、下にある「5」の時点でやばそうだと踏んで捨てていたでしょう。難問だと聞き知っているうえで、いかにも沼にハマりそうな発想でも続けていたと思います。
大まかな思考の流れ

  1. まず実験をする

  2. L=5を終えて雰囲気がわかる

  3. Lが3の倍数, 3の倍数+1のときが片付く

  4. Lが3の倍数+2は出来ないのかと予想する

  5. 「“出来ないということを示したい” -> “出来たと仮定して矛盾をいう”」なので無限降下法チック

  6. 矛盾をいうために、かつ簡潔にいうために、グラフの状態を図に頼らず表現したい気持ちがわく

  7. 「5」から「6」のやり方に挫折する

  8. L=8の実験

  9. ここまでの考えから離れ、別角度から攻める

  10. うまくいかず断念…

補足)「6」について
 添付ファイルの3ページ目を参照してくださった方が早いかと存じます(汚くて申し訳ありません….)。グラフを端、端以外で切り、さらに端以外を一定の短い長さで切ってしまいます。切った後は色の配置で場合分けすることでパーツができます。それにより任意の(棒状)グラフの状態を、用意したパーツの組み合わせで表現してみます。補足)「9」について
 操作(1)も操作(2)も点の数を増やします。ただし、施す位置によって”黒を1減らし、白を2増やす”あるいは”黒を1減らし、白を2増やす”などと意識します。ある意味とても素朴な考えに戻りました。「1」から「4」と違うのは、具体的な長さで実験するのではなく一般的な長さで考え始めたところです。  どの操作も”黒を○増やす/減らす、白を●増やす/減らす”ですが、黒を増やす操作には上限があります。簡単にわかりますが、(指定の長さ-1)回まで操作しないといけませんし、それ以上の操作は許されません。その制約内でピッタリ真っ白な状態まで持っていかなといけませんので、黒を増やしすぎると、増えた分の黒を消して白を入れる操作が不足します。ここから攻められないかと考えたわけです。
実況中継
 とりあえず手を動かし作ってみる。L=2はダメでL=3はOK….L=5はめんどくさいけどやるか(参照:2ページ目の右側)。やはり黒い頂点の動向に目がいき、L=5がOKとなるために1手前、2手前と遡る。この時にL=3の状態で実現できるものとできないものに問題が帰着される。(あとで部分問題へと帰着させる考えに飛びつく) とりあえずL=5ができないとわかる。
 (1)も解いたため、ある長さLの白い棒状グラフができれば操作①を3回繰り返してL+3の白い棒状グラフができるとわかっていたのでL=3m, 3m+1の時はOK。なんとなくL=3m+2ができないのかと察する。(ほんとうはL=8も確認すべきだったがめんどくさがった)
 「“出来ないということを示したい” -> “出来たと仮定して矛盾をいう”」という典型的な考えーーちなみに一向にこの考えから離れられなかったーーから、L=3m+2が作れたとしたら矛盾、つまり遡るとL=1の時が白頂点1つのみである事実に反することを示したくなる。数列と整数の問題で時折みる無限降下法を知っていたのも理由かもしれない。しかし、たどり返す操作をするということなので大変だ。どうするか。
 最初の段落で述べた部分問題への帰着を思いつく。L=5の可否についてL=3の状態を利用して判定したのでL=3m+2も同様にL=3mで考えられないかという考えもあり、1手あるいは2手で黒を消せてしまう棒グラフのパーツを挙げてみる。この考えが伸びて、できれば一般の長さLのグラフの状態をパーツとその数で表現してしまえないかなど、わりと好き勝手なことをやり始める。なんか代数っぽくなってきたぞ…….
 詳細は覚えていないけれども結局頓挫した。表現することはできても遡っていくことが必要なのには変わりなかった。どうしたものか。
 行き詰まったので、めんどくさがっていたL=8の実験をするほかないか。L=5までの実験では(勝手な印象で)何かと黒い頂点が少なかったが、L=8でたどると途中黒い頂点が結構あるものだなという感想を得る。とはいえ上限があるはず。
 操作①と操作②の意味付けによる両色の数の問題と捉えて攻める方向にシフト。というか他にやることがなかったから着地してきた感じが否めない。
 いや、やっぱりわからん……
余談
 総じてどこか情報系くさい考え方でした。とくに「6」です。あとから見たら完全に分割統治法を意識していました。これは計算機科学で使われるアルゴリズム設計におけるパラダイム(考え方)です。

↪︎Hiroto

ありがとうございます。情報系っぽい試行錯誤、というのが大変興味深かったです。
「一手ずつ遡る」「できたと仮定して矛盾(遡って1個の白にならない)が言いたい」などの方針を示してくれました。この時点で多くは語りませんが、chiffonさんの無念、、、、、、、、僕が晴らします(ドン!!!)

もう一つ補足しておくと、無限降下法は、背理法と帰納法(というか自然数の整列性)の合わせ技のようなものなので、基本的には帰納法と思って良いです。その意味でも僕の方針とchiffonさんの方針は大変近しいものでした。

7日目

★Hiroto

今日はていりふびにさんに語っていただこうと思います。夜9時ごろです。よろしくお願いいたします。

★ていりふびに

個人的には結局なんの糸口も掴めずに終わりましたが、問題を解いている最中に考えたことを書いていきます。
(1)は適当に手を動かしていれば解くことができました。(1)が(2)の布石になることが多いので、「(1)の操作がキーになるかも」と考えましたが、繋がりは分かりませんでした。
(2)はとりあえず、書き出していくしかないと思ったので n = 4までをいったん書き出してあります。この時点でn = 5ができないとは気付きました。
また、例を見ていく中で一度全てが白になると、三回操作を繰り返す(三個点が増える)ことでもう一度全てを白にできると分かりました。
つまり、n = 1、n = 3で一度全てが白になっているので、そこに三回の操作を繰り返した n = 3k 、3k - 2 はすべて白にできるということになります。
n = 2、5までしか確認していませんが、逆にn = 3k -1 の場合ができないのだろうとは予測がつきました。
このことを示す方針として
A:n = 3k、3k-1、3k-2ごとの特性量を見つける。
B:操作が複数あるとめんどくさそうなので一つにする。
を考えました。Aに関しては、特性量(特徴)を見出さないことにはn = 3k、3k-1、3k-2に関して区別することができないと思ったので考えました。この問題に対して固有に考えることというよりは数学の問題としてありがちなので、この視点は常に持っています。
特性量の具体例は書いていませんでしたが、例えば黒の個数などを見ていました。
しかし、今回は n = 5まで見ていてもなにも気づきはありませんでした。時間があれば、n を大きくして書き出していたと思います。Bに関しては、操作1と操作2の違いが「はじがあるかどうか」しかないような気がしたので考えました。はじをなくすために円環状にして考えましたが、同一視したらいけないパターンが同じ扱いになるので違うようなきがしています。。

↪︎Hiroto

ありがとうございます。
方針のA, Bがかなり本質的だったため、選ばせていただきました。
Aは僕が少し前に紹介した「不変量」の話で、のちにこの視点から解かれた解答がいくつか見られると思います。
Bは僕には実装できなかった視点ですが、これものちに紹介する解答ではかなり用いられています。僕もこれを用いたらもっと簡単にできたのかなと思っています。

8日目

★Hiroto

今日はあんまんさんに語っていただきます。よろしくお願いします。

■けろたん

ヒントの「不変量」で思いついたことをスレッドに投下します。

↪︎けろたん

操作に対する不変量がある→操作を3回やってもその量は不変。(3ステップの不変量を見つけたら1ステップでも普遍か後からチェックが必要(?))
不変量を見つけるために黒の位置関係を見てみる。
シンプルに隣合う黒丸までの距離を数えてみようとするが、白×2を白×5に伸ばす操作で白が伸びると隣の黒までの距離も伸びるので、単純に隣り合う黒丸までの距離をカウントすると不変量としてはダメっぽい。可能グラフに対して白枝(黒丸間の白×2以上の部分)を無視して黒同士の距離を数えたい。

(勘違い)どの黒丸同士の間にも白×2が含まれるのであれば、(右(カウントする方向を固定してみる))隣までの距離の和が不変量になる(具体例に作ったn=11の白黒混合グラフがそもそも可能グラフかどうかチェックするのが辛い。)
この和は違った白枝を伸ばしてもnが同じなら等しくなる量であって、nを増やす前後で不変な量ではないことに気づく。orz

(勘違いからの収穫)そもそも、隣り合う黒丸までの距離は一つの黒丸についての情報であってグラフ全体についての量ではない。距離の和をとってそれをグラフ全体についての情報とするのはよさそう。

和の数え方:(黒白混合グラフが可能グラフかどうか一旦無視)
1.黒から右隣の黒まで数えてそれらの和
2.左端の隣に0番目の頂点をおいて、そこからいくつか数えて和をとる
白白白黒白白黒白黒(これは白×6から割り込み2ステップ+両端に追加1ステップで可能)を考える。
白白白黒白白黒白白白

グェー!!

不変量が特定の値だとなぜ思った?
3のあまりで分類できる何かであれば、数値として確定しなくてもよい。
あるグラフの距離の総和は具体的な値。
白枝の無視が難しい→距離の和とそれ以外の要素をごちゃごちゃしたものが不変量かもしれない?
不変量の部品候補:黒の数、白の数、頂点の数、黒の相対距離(の和)、白の相対距離(の和)

何が不変量かは一旦保留。
注目している不変量=ある区間の白棒の伸縮に対する不変量
存在を示したい不変量=1回の操作に対する不変量?→あれ、3のあまりで分類ということは操作1回の不変量ではなくてもいいのか?1回の操作で固定的に変わり、3回周期で同じになる量?
よくわからなくなる。

・操作に共通しているのは、新しくくわわる頂点は必ず白である、ということ。
なーんか使えないかなー。
・端をキャンセルする操作を考えてみる
→毟る:両端をちぎって捨てたグラフの両端もまた気になる→n=5まで全部の可能グラフを列挙してパターンっぽいものが見つからなかったので望み薄。
→折り返す:右端に鏡を置いて、グラフの右端と鏡のグラフの左端を連結する。できたグラフはnが2倍になるので、3で割ったあまりが1と2で反転するのが何か使えないか
→無理やり付け足す:左端(xor右端)に黒丸を一個付け足してそこをカウントの起点にする(和の数え方1と2が同じようなものになる。&こいつ自体は1ステップで消えるのであとからnの帳尻を合わせるのが簡単そう。)
→→付け足したやつが可能グラフかどうか考える必要はありそう。

(例に戻って思いつきを試す)
黒白→白白黒(3k-2)、白白白(3k)、白白→黒白黒、白黒白(3k-1)
毟る:上記の例の範囲だと一方の端を毟ると白白開始組と白黒開始組が入れ替わるが、n=5→4毟りではそうならないやつがいる。
折り返す:折り返したやつは可能グラフなのか?→保留。
付け足す:
疑問1:黒白黒に対して黒を端に足していいのか?(足したやつは可能グラフではない)
黒白黒と、黒|白黒白で隣の黒までの総和は2。
疑問2:全白棒グラフは黒の相対距離が存在しない。→0ってことにする?

n=5の全ての可能グラフで、端に黒を足したり足さなかったりして、黒の相対距離和(+ごちゃごちゃ)で同じになる値がないか探してみる。(←現在)


・ここまでの感想
白白、白黒発展系のそれぞれのグラフに対する考察と、白黒発展系(可能グラフ)のnの増減に対する考察が混ざって混乱しています。

↪︎Hiroto

ありがとうございます。
「不変量が特定の値である必要はなく、それも3で割ったあまり(mod3)で考えればいいじゃん」というところまで至ったのは、やはり試行錯誤あってのものだと思います。こういった生の思考を見させていただくと、やはり試行錯誤がいかに大事かを感じさせられます。

9日目

★あんまん

(1) パズルを楽しみました。最難関のわりに問題設定は簡単やんけと思いました。
(2)まずは、問題を理解するためにとりあえず具体的な数字で実験してみました。そこでグラフの取りうる形をn=4まで書けるだけ書いてみました。n=5以降は取りうる形が多すぎて書けませんでした。しかし、n=4のどのグラフからも、n=5で白棒が可能グラフにならないことがわかりました。また、白棒から3回の手順で白棒が作れるという発見をしたので、この実験から、n=1,3の時に白棒が存在していたので、nが3の倍数の時とnが3で割って1余る時の数であれば、白棒が可能グラフであることがわかりました。実験で、n=2,5の時、白棒は可能グラフにならないので、nが3で割って2余る数の時は無理だろうと予測がつきました。具体的な実験によって、示すべきものを理解することができました。
次に計画です。白棒が可能グラフではないということは、グラフに少なくとも一つ黒が存在するということなので、黒色が存在する棒状グラフからは、手順を3回終えた後も黒色が存在するということを示せば良いと考えました。そこでまず初めに、形に着目しました。n=3k-1で白棒が可能グラフになるならば、ひとつ前のn=3k-2で特定のグラフが必要。そのグラフを作るためにはさらにひとつ前のn=3k-3で、こんな形のグラフが必要…というふうに。しかし、途方がないことに気づき断念。次に、数に着目しました。調べてみると黒の増減は+1 or -1 or +2 or -2 or +0の5種類であることがわかりました。3回の手順では、-2を3回することによって黒は最大6個までしか減らせないので、黒の数が1~6で場合分けして、どの場合でも、3回の手順後には黒が残ることを示そうと考えました。まずは黒が1つの時から。しかしここで、気付きたくないことに気づいてしまう。黒が1つあるグラフから、3回の手順で、白棒グラフが作成できてしまったのである。つまり、示したかったことの反例が見つかってしまいました。計画が白紙になり、(1)でなぜ十字の形のグラフを作らせたのかなどと考えたが、結局次に進まず、ggとなりました。

↪︎Hiroto

ありがとうございます。
「黒の個数に着目する」というのは、結果頓挫したとはいえいい着眼だと思います。「不変量」という視点から見て、このような着眼がのちに活きてきます。
十字グラフをどうにか誘導として利用したいというのは僕も考えました。結果使えなかったのですが、もしかしたらそれが使えるような何かがあったりする(棒状以外との関係性)のかな〜とまだ可能性を捨てきれずにいます。僕とそのあたりの思考が似ていたため、選ばせていただきました。

★Hiroto

本番その1『Hirotoの解』
さあ、今日からついに解答の展覧会に移りたいと思います。改めてよろしくお願いいたします。
さて、まずは僕の解答からです。先に言っておくと、試験答案としては到底収まらないグダグダ解答です。ただ、世界一泥臭い自信があります。僕の解答を最初に持ってきたのは、のちの解答のエレガントさを引き立たせるためです。
解答自体は割とくどいと思われるため、そこに至った「思考回路」の方を重点的に読んでみてください。そこらへんも全部このファイルに記してあります。よろしくお願いします。

↪︎Hiroto

大事なポイントは、
・GOALから抜いていく、と思考を転換したこと
・帰納法を回すために、示すべきことを強めたこと(普通結論を強めたら難しくなるが、帰納法の場合仮定も強くなるので、その限りではない)
極力、突飛な発想を用いなかったこと(凡人でも頑張れば辿り着ける想定)
・発想に頼らなかったせいで、解答が異常に長くなってしまった(これはデメリット)

★Hiroto

ちなみに、取り掛かった期間は確か1週間ほどです。試験時間内に解けない僕は、凡人だと思い知らされました。これからも地道に身の丈に合った数学をしていきたいとおもいます。
1週間のうち、
・6日間は頭の中
・最後の1日はノートに書いて明確にした
という感じだったと記憶しています。

10日目

★Hiroto

本番その2『ブログ①の解』
参考にさせていただいたのは
https://marriagetheorem.hatenablog.com/entry/20100324/1269362813
に掲載されている解法です。僕と同じ帰納法チックな解答ですが、目の付け所が僕よりもシャープで、その分僕よりも解答が小さくまとまっており素晴らしいです。
ただブログでは一つだけ場合わけが考慮されていなかった(ように思えました、僕の解釈ミスの可能性もあります)ので、それも完全にギャップなく補完して資料を作りました。ぜひご覧ください。

11日目

★Hiroto

本番その3『所長の解』
参考にさせていただいたのは、ジェイラボちょい解きレッスンでの当問題の解説動画です。
解法のエッセンスを汲みながら僕の方で整理し直しましたので、ぜひご覧ください。

↪︎Hiroto

帰納法でも不変量でもない、これぞ独自の解法、という感じです。
徹頭徹尾算数チックですし、発想以外何一つ難しいところがありません。本当に、エレガント以外の言葉が出ません。
明日からは不変量チックなものをご紹介します。所長の解や不変量を用いた解は、発想の部分で労力を費やしている分、記述量は少なく済みがちです。発想勝負か記述量勝負か。性格が分かれます。

12日目

★Hiroto

本番その4『環耀氏の解』
参考にさせていただいたのは、
https://youtu.be/mH_CQ5qFzss
で紹介されていた解法です。
発想の部分も含めて動画を参考にして資料を作りました。ぜひご覧ください。

★Hiroto

本番その5『ブログ②の解』
参考にさせていただいたのは
https://mine-kikaku.co.jp/index.php/2021/05/03/19983/
の解法です。

14日目

★Hiroto

本番その6『ブログ③の解』(番外編)
この解は番外編扱いとしようと思います。その理由は、「行列を用いているから」です。行列は今の高校数学課程には存在し得ないため、この解法は大学数学的ということになります。
(行列を平面の変換と思えば、変換の言葉や複素数の言葉で語れなくもないのですが、その場合も「写像チックな」語り方をせざるを得ないので、どちらにせよ大学数学的なエッセンスが含まれてしまいます。)理解できる人のみ内容はご理解いただければと思います。が、理解できない人もこの資料の「ページ数」だけはみてください。この解法、発想が天才なだけあって、超簡潔なんです。

■Naokimen

この問題はLie代数で出てくるDynkin図に似ていると思っていたのですが、グラフ理論は群の表現論と繋がりがあるのでしょうか?

↪︎Hiroto

表現論との関連はわからないのですが、こんな記事を見つけました。
https://www.mathsoc.jp/publication/tushin/2202/2202kobayashi.pdf
おそらく出題背景にはこのメビウスの輪のような問題があったのだと思われます。それなのに「入試史上最悪」という文脈でしか取り上げられないのはなかなか悲しくはありますね、、。

★Hiroto

本番まとめ『解の比較』
ここまで、準備としては、
・問題理解
・実験の大切さとすぐわかる十分条件
・やばそうな必要条件(某予備校もギャップのある解答を出すレベル)
・2つの武器:帰納法と不変量
・3人の試行錯誤
を行ない、その上で解法として、
その1:Hiroto
その2:ブログ①(https://marriagetheorem.hatenablog.com/entry/20100324/1269362813
その3:所長
その4:環耀氏(https://youtu.be/mH_CQ5qFzss
その5:ブログ②(https://mine-kikaku.co.jp/index.php/2021/05/03/19983/
その6:ブログ③(https://ameblo.jp/miraclemaster/entry-10876823332.html
と6つのものを紹介してきました。
ここで、今までの話を概観し、それぞれの解法を比較したいと思います。最初に断っておくと、この比較は優劣をつける類のものではありません。単に、その性質で分類しようという類のものです。その分類に何の他意も(もちろん悪意も)ございませんので、ご理解をよろしくお願いいたします。
(以下、1から5の五段階評価。5が高い。1が低い。これも例によって優劣という意味ではなく、評価軸の程度の話。その評価軸が高いことと価値が高いことは等価ではない。)

その1:Hiroto
・エレガントさ…1
・記述量の少なさ…1
・その他キーワード:帰納法、一手ずつ遡る、W付加ルール
一見するとゴミ解答のように見えるかもしれませんが、エレガントでないことは別に価値を下げるものではありません。泥臭さという意味で、発想が自然だ(突飛なひらめきを必要としない)と言い換えることもできます。とはいえ、他の解答を見ると、もっと工夫できたなあと思う部分もあり、個人的には反省をしています。ただ、自力で解けたこと自体は自分の中では一つの大きな糧となりました。日々反省日々成長。

その2:ブログ①
エレガントさ…4
記述量の少なさ…3(ブログのままの解答であれば4)
その他キーワード:帰納法、両端追加して操作2のみに、部分グラフ
僕とは異なる類の帰納法の回し方をしています。一手前という遡り方ではなく、部分グラフを見るという思考。これはエレガントポイントです。ブログのままの解答ではかなり記述量が少なくなっていますが、場合分けを補完して足すと少し長くはなります。これも厳密性と記述の簡便さのトレードオフで、実際の試験でどちらが良いかは判断しかねます。僕はたっぷり時間のあるこの場での紹介のため、記述量の長さは気にせず資料を作成しましたが、試験となればそうはいかないでしょう。

その3:所長
エレガントさ…5
記述量の少なさ…4
その他キーワード:辺にも変化を考える、算数、±1の積、操作を及ぼしたところだけの変化、両端追加して操作2のみに
エレガントさで言えば群を抜いていると思います。その上、数学の難しい概念を用いているわけでもない。発想一本勝負。見事です。この解法を試験で思いつけた人、冗談抜きですごいと思います。その意味では「観賞用」とも言えるかもしれません。その発想のエレガントさもあり、記述量も結果的に削減されています。算数って大事かもしれないですね。

その4:環耀氏
エレガントさ…2
記述量の少なさ…3
その他キーワード:不変量、Bから生成されるグラフとの共通部分がないことによる推論、W付加ルール
解答だけ見たらこの解法はエレガントかもしれません。不変量が空から降ってきているように思えるからです。が、環耀氏は動画内でしっかりとその発想に至った自然な実験経緯を語っており、その意味では自然な不変量と言えます。エレガントさが2と低いことは思いつきやすいということを示しています。両端追加で操作2のみにすれば、記述量はこれよりも減りそうです。が、それはそれで思いつきにくいので一長一短ではあります。

その5:ブログ②
エレガントさ…3〜4
記述量の少なさ…4
その他キーワード:不変量、両端追加して操作2のみに、初期状態と結果の不変量の値が異なることによる推論
環耀氏の解法とだいぶ似ています。両端追加して操作2のみにしていることにより、記述量の削減とそもそもの不変量の設定に差異が出ています。ブログではこの不変量に思い至った経緯が薄い(ひらめき頼り)ような気がしたため、3〜4としました。実験から思いついたとのことですが、なかなかそこにはギャップはあると思います。だからこそ思いついたこと自体が素晴らしいのですが。

その6:ブログ③
エレガントさ…5
記述量の少なさ…5
その他キーワード:不変量、行列、両端追加して操作2のみに、積の非可換性
エレガントすぎます。これは所長のものとは訳が違い、高等な具体物(行列)の知識があって達成されたエレガントさです。このエレガントさに関しては正直驚きが隠せませんでした。(棒状グラフを積と思うなど考えもしなかった、、。)そのエレガントさの分だけ、記述量は異次元に少ないです。数学は論理的思考力が大事であって知識ではない、とはよく言われますが、その反例のようなものがこの解法で見られたような気がします。色々な具体例を知っていることは本当に大事です。研究(または自力で勉強)するときはなおさら。

★Hiroto

よければ皆さんの興味を惹かれた解法をお教えください。
アンケート形式にはしません。一番得票したものが偉いかのように見えてしまいかねないからです。
僕は驚いたという意味で、所長のものとブログ③が興味を惹かれました。自分がこの発想に至るために何が必要なのか皆目見当がつかず、「ひらめき」について日々考えなくてはならなくなりました、、。
(こちらからの投稿はこれで以上なので、適宜読み返していただいたり、質問していただいたり、上の質問にお答えしていただいたり、お願いします。)

■チクシュルーブ隕石


僕はhirotoさんの解答と所長の解答、ブログ③が印象に残りました。
hirotoさんの解答は事前の実験や思考のプロセスが分かりやすく、丁寧に一歩一歩踏みしめながら進めている感じがして、自分が今後数学をやっていく時も地道な試行錯誤を蔑ろにしないという指針にさせて頂きたいと思います。
所長の解答は基本的に必要な知識が算数の範囲で全て完結していると言う点で凄いと思いました。大学入試の最難問が理論上中学生の知識でも解けるのを実感して末恐ろしさを感じました。
③は正直高等すぎてまだよく理解しきれていないですが、解答の簡潔さと行列を導入するというアイディアは僕が一生かかっても多分思いつかなかったと思いますw。
今回展覧会という形で様々な解答例を載せていただき、僕自身も楽しく解かせていただく事ができました。ありがとうございます!

↪︎Hiroto

地道な試行錯誤、大事ですね、、。
所長のものとブログ③は、本当に対比すればするほど面白い2つだと思います。楽しんでいただき光栄です。こちらこそありがとうございます。

★Hiroto

一応形式的にWSを締めさせていただきますが、上の問いかけへの答えなど、なんでもお待ちしてます。
所長のWSが始まるまでは多分ここで良いですし、始まったとしても事後スレッドで僕はいつでもあなたを待っています。
この度は、東大入試数学最難問の解法展覧会にお越しいただき、誠にありがとうございました。またのお越しをお待ちしております。
以上、数学部のWSでした。お疲れ様でございました。

この記事が気に入ったらサポートをしてみませんか?