皆さん、こんにちは。
ここ最近は、東大の後期入試の過去問を解いてきましたが、その中で1問「別記事で取り上げます」としてた問題がありました。
それが、1998年の第3問です。
この問題、「大学入試史上最も難しい数学の問題」として伝説になった超難問です。そういう曰く付きの問題だったので、シリーズ物から独立して記事にした次第です。
問題文は以下のようになっています。
まずは、とりあえず目を通してしてみてください。
1. どんな問題か？
まず問題文を見てどういう印象を持ちましたでしょうか？
「とにかく長い」
「意味不明」
「威圧案ぱない」
「見ただけでヤバい予感しかしない」
色々感想が頭に浮かんだと思います。正直問題文を見ただけで裸足で逃げ出したくなりますね。
しかし、この問題の言わんとしていることは、実はそんなに難しくありません。簡単にまとめると、ルールは以下の2つに集約されます。
1. [操作1] ○をつなぐと、繋がれた○の色が反転する(○→●, ●→○)
2. [操作2]○を途中に割り込ませると、両隣りにある○の色が反転する
これら2つのルールに従って○と●を線で繋いだ図形を作っていく、というのがこの問題の趣旨になります。
そして、問題文の「可能グラフ」というのは、「○１つからスタートして、操作1と操作2を繰り返すことで作ることができる図形」の事だというわけです。
2. (1)について
(1)については、図5にある３つの図形が○1つからスタートすれば全て作ることができると言えてしまえばOKなので、実際に実験して作れることが確かめられれば終了です。いわばルール確認のための小問と言え、この段階では全く「超難問」ではありません。
実際に確かめてみると、下のような感じに全部作ることができます。
3. (2)について
では、この問題が「大学入試史上最も難しい問題」と伝説化する所以になった(2)についてみていきましょう。
3-1. どんな問題か？
問題文の趣旨は、
「1個の○からスタートして操作1と操作2の繰り返しで○をn個横一列に並べられる、nの必要十分条件は何か？」というものです。
要求されているものは必要十分条件なので、
「この条件さえクリアできていれば横一列に並べられる（十分条件）」
「逆にその条件がクリアされていなければ横一列に並べることができない（必要条件）」
の両方を証明しないといけないわけです。
3-2. 十分条件について
まずn=1がOKなのは明らかであり、(1)でn=3もOKだと調べています。
ここで一般に
「n個の横一列が可能グラフ→n+3個の横一列も可能グラフ」が成り立ち、これは以下のように簡単に証明できます。
この事実から、帰納法の考え方を使えば
「n=3mあるいはn=3m+1のときは、n個の○を横一列に並べることができる（但しmは整数)」
が証明できます。これがnの十分条件です。ここまでなら、何とかなるでしょう。
3-3. 必要条件について（この部分が超難問）
逆に、(1)の途中を見れば分かる通り、n=2の場合は白と黒が混在してNG, 実験してみるとn=5の場合も無理そうだと分かります。つまり、
「n=3m+2のときは、n個の○を横一列に並べることができない」と言えそうですが、これはあくまで「予想」なのでちゃんと証明しないといけません。
ところが、「できないことの証明」というのは非常に難しいのです。しかも今回は操作の仕方が2種類あり、「操作1と操作2をどんな場所にどんな順番で何回行ってもn=3m+2の場合は作れない」ことを証明しないといけないわけです。通常高校数学で使うような数学的帰納法では全く歯が立ちません。まさに「悪魔の証明」です。
そうです、この必要条件の部分の証明こそが、「大学入試史上最も難しい数学の問題」なのです。
3-3-1. 方針決め
＜その１：操作1と操作2の統合 →両端にダミーの●を置く＞
まずこの問題における考えにくさの要因の一つが、やってもいい操作が、端っこに○を継ぎ足す「操作1」と、辺に○を割り込ませる「操作2」の2種類あることですね。これを何とか一緒に考えられるようにしないと訳が分からなくなります。
ここで、一つ目のひらめきポイントが発生するのですが、種を明かしてしまうとこういうことです。
「最初に両端にダミーの●をくっつけてしまえば、『両端の辺への操作2=もともとの状態での操作1』にできる」
というトリックです。どういうことかを図で説明すると、下のようになります。
このトリックを使うと、「最初に両端にダミーの●をくっつける→操作2だけをひたすら行う→最後に両端のダミーを外す」＝「元の状態に操作1と操作2を繰り返し行う」
とできて、操作2だけ考えればよいことにできます。これで操作を統合できたので多少は考えやすくなりました。
ということで、(2)の必要条件の証明の概略は以下のようになります。
＜その２：操作2で変わらない量＝不変量 を探す＞
さて、上記の作戦で操作2だけ考えればよくなったのですが、それでもどうやって必要条件を証明すればいいのか、よく分かりません。
ここでは、高校数学まででは中々お目にかからない発想が必要になります。
「操作2を何回行っても変わらない量＝不変量を見つける」ということです。いわば、その図形のDNAを調べてあげようという事です。
このDNAさえ見つかってしまえば、
「○1個からできるグラフのDNA」≠「○が3m+2個並んだグラフのDNA」
が言えれば、「どんなに操作1,2を繰り返しても、○を3m+2個並べることができない。なぜなら、DNAが異なる別人だから」という感じで必要条件が示せることになるわけです。
なので、このDNA, 不変量を何とかして見つけてあげればゴールに大きく近づきます。
3-3-2. 解答
＜不変量を見つける＞
以上２つの方針を使って「n=3m+2の場合は○を横一列に並べられない」ことを証明していきますが、2つ目の方針の核である「不変量」を見つけるのが、かなりの難関です。
まず、パッと思いつくのが「操作2をしたら、○と●の個数がどう変わるんだろう？」だと思うので、そこからチェックしていきます。
具体的に実験すると、個数の増減は
(i)○2個の間に操作2をするとき ○: -1個、●: +2個
(ii)○と●の間に操作2をするとき ○: +1個、●: ±0個
(iii)●2個の間に操作2をするとき ○: +3個、●: -2個
となります。特にこれと言った規則性は見えてきません。
上では2個の丸しか見れていなかったので、直接反転が起こらない少し外側まで見てみることにします。
今、両側をa個の○とb個の○(a≧0, b≧0)に挟まれた2個の丸を結ぶ辺に操作2を行うことを考えます。
実際に操作2を行うと下のようになります。
この時の○の個数の合計を、クラスターごとに調べると
(i)2つとも○のとき
1番目のクラスター: a+2+b個
(合計T0=a+b+2個)
⇒1番目のクラスター: a個、
2番目のクラスター: 1個、
3番目のクラスター: b個、
(合計T1=a+b+1 =T0-1)
(ii)左が○、右が●のとき
1番目のクラスター: a+1個
2番目のクラスター: b個
(合計T0=a+b+1個)
⇒1番目のクラスター: a個、
2番目のクラスター: b+2個、
(合計T1=a+b+2 =T0+1)
(iii)左が●、右が○のとき
1番目のクラスター: a個
2番目のクラスター: b+1個
(合計T0=a+b+1個)
⇒1番目のクラスター: a+2個、
2番目のクラスター: b個、
(合計T1=a+b+2 =T0+1)
(iv)2つとも●のとき
1番目のクラスター: a個
2番目のクラスター: 0個（※）
3番目のクラスター: b個
(合計T0=a+b個)
⇒1番目のクラスター: a+3+b個、
(合計T1=a+b+3 =T0+3)
となります。
（※ ●が2つ以上連続する場所は、その隙間に「0個」の○クラスターがあると考えることにします。こうすると好都合なので）
前述のように、ただ単に○の個数を合計した値の変化(T0→T1)を見ても-1,+1,+1,+3とバラバラです。
しかし、ここで、「偶数番目のクラスターの個数を-1倍してから合計する」という細工をしてあげると、
(i)2つとも○のとき
1番目のクラスター: a+2+b個
(合計S0=a+b+2個)
⇒1番目のクラスター: a個、
2番目のクラスター: -1個、
3番目のクラスター: b個、
(合計S1=a+b-1 =S0-3)
(ii)左が○、右が●のとき
1番目のクラスター: a+1個
2番目のクラスター: -b個
(合計S0=a-b+1個)
⇒1番目のクラスター: a個、
2番目のクラスター: -(b+2)個、
(合計S1=a-b-2 =S0-3)
(iii)左が●、右が○のとき
1番目のクラスター: a個
2番目のクラスター: -(b+1)個
(合計S0=a-b-1個)
⇒1番目のクラスター: a+2個、
2番目のクラスター: -b個、
(合計S1=a-b+2 =S0+3)
(iv)2つとも●のとき
1番目のクラスター: a個
2番目のクラスター: 0個（※）
3番目のクラスター: b個
(合計S0=a+b個)
⇒1番目のクラスター: a+3+b個、
(合計S1=a+b+3 =S0+3)
となって、操作2の前後での変化(S0→S1)をみると、-3,-3,+3,+3と全て差の絶対値が3になりました！
3を足したり引いたりしても変わらない量と言えば、「3で割った余り」ですね。
要するに、
「○の個数を（左から）奇数番目のクラスターの個数はそのまま、（左から）偶数番目のクラスターの個数はマイナス1倍して、全て足した合計Sを3で割った余り」
は、操作2の前後で変わらない、ということです。
※初めて黒に挟まれる白クラスターが発生した場所を「1番目のクラスター」とみなし、左端に白クラスターがある場合は「0番目のクラスター」と見なします。
これを図形の不変量、DNAにしてしまえばよいでしょう。
＜最終的な証明＞
無事「不変量=DNA」が見つかったので、実際にスタート状態のDNAと、n=3m+2が実現した状態のDNAを比較すると、見事両者のDNAが違うことが確かめられます。
これで、「○1個の状態からどんな場所にどんな順番で操作1と操作2を繰り返しても○を3m+2個横一列に並べられない」ことが厳密に証明できたことになり、先に調べた十分条件「n=3m, 3m+1」が○を横一列に並べられる必要条件でもあることが分かりました。
以上から、○1個からスタートして○をn個横一列に並べられる必要十分条件は
n=3m, 3m+1 (m:自然数)
だと求まりました。
これにて終了です。
4. この問題に関する逸話
どうでしたでしょうか？微分も積分も連立方程式も確率も一切使わないパズルチックな題材でしたが、
「ダミーの●を両端に足せば操作1を考えなくてよくなる を思いつく」
「操作2に対して変わらない量（不変量）を考えれば証明できる を思いつく」
「不変量を見つける＝構築する」
といった常人離れした発想をいくつもしなければならない、超ど級の難問でしたね。
私自身、自力で解けたわけもなく、この記事を作成するにあたり、いくつかのブログを参考にさせて頂きました。
【入試伝説】1998年 東京大学 大学入試史上No.1の超難問～20年目の真実～ | 受験の月
キング オブ 難問 – 1998年東大 数学 後期 第3問 | 有限会社峰企画
(今回紹介した解法は、主にこの2つの記事を参考にしたものです）
【伝説の東大入試】なんと中学レベルの数学で解けるぞ！【徹底解説】
(東大王の伊沢さんでお馴染みQuizKnockさんの記事で、さらに噛み砕いて解説した記事です）
史上最大の難問 東大後期1998-問3 | 東大カリスマ塾長 浜田一志公式ブログ -9割が伸びる”文武両道”勉強法-
（こちらでは、行列を使った別ルートでの解法が紹介されています）
ある人曰く「国際数学オリンピックで出題されたとしても難問のレベル」
ある人曰く「これは数学科の夏休みの課題レベル」
ある人曰く「数学科の大学院入試で出題されてても違和感がない」
要するに専門家の間でも、とてもじゃないが一介の高校3年生の受験生には到底手に負えるレベルではない超難問、という評価で落ち着いています。
実際に、当時の受験数学のプロ集団である予備校講師ですら、その日のうちに解くことができずどの予備校も即日の解答速報を出せなかったそうで、最終的にはプロの数学者に解答を依頼して2日がかりで解いてもらった、なんて逸話もあったりします。
5. おまけ（グラフ理論）
この問題、大学入試というジャンルではほとんど例のない題材が背景になっています。それが「グラフ理論」というものです。
「グラフ理論」と言うのは、「点と線でつながった図形に関して研究する学問」のことで、いわゆる受験生になじみのある「x軸y軸のグラフ」とは全く別の概念です。身近な例では、鉄道の路線図なんかが「グラフ」に当たります。
この分野の問題で、比較的有名なものとして「ケーニヒスベルクの橋の問題＝一筆書きができるか否か？」、「巡回セールスマン問題＝最も短い時間で全ての都市を回る方法をどうやって構築するか？」、「四色問題＝あらゆる地図を4色以内で塗り分けることができるか？」といったものが挙げられます。
以上おまけでした。
