1998年東大入試後期日程、数学問3（2）の件

備忘録 研究・教育 数学

1998年の東大入試後期日程の数学で出題された問題（問３の小問（２））がとんでもない難度だと某所で話題になっていたので、ちょっと眺めてみました。


件の問題に関するまとめサイト： http://2r.ldblog.jp/archives/2927641.html
問題はこちら（河合塾のサイト）：

で、某氏に名指しでこの問題を解くように言われたので解いてみました。
今回は50分弱で以下の答えに辿り着いた（ただし解答を書く時間は含めず）のですが、実を言うと数ヶ月前にもこの問題を40分ぐらい考えて音を上げていたので、合計すると１時間半くらい時間がかかったことになります。確か当時の東大後期数学は全３問で試験時間が２時間半だったと思うので、１問にこんなに時間を掛けていてはいけません。
それはさておき、以下が私の解答です。どうも論文風の書き方が染み付いてしまっていて、大学入試の答案としてはややくどい書き方かもしれませんがご容赦下さい。

問３（２）の解答

　求める必要充分条件は、「ｎを３で割った余りが０か１」・・・（＊）である。以下このことを証明する。

　まず、棒状のグラフを作る過程で両端以外の頂点を選んで操作１を行ってしまうと、グラフに枝分かれ（３本以上の辺が出る頂点）ができてしまい、以降の操作でその枝分かれがなくなることはないので棒状のグラフにならなくなる。従って、操作１は常に両端のいずれかの頂点を選んで行うものと仮定しても一般性を失わないことを注意しておく。また、以下では「可能グラフ」は全て棒状の可能グラフを指すものとする。

　さて、元々の問題を考えるために、以下のような「拡張された問題設定」を考える。そこでは二つの頂点（色は好きに選んでよい）を１本の辺で結んだグラフG1'を出発点のグラフとして、操作２のみを繰り返して新たなグラフを作っていく。このとき、以下の性質が成り立つ：

  • 性質１：ある棒状グラフが元々の問題設定における可能グラフであるための必要充分条件は、その棒状グラフが、拡張された問題設定におけるある可能グラフの両端点を削除して得られることである。

実際、元々の問題設定で端点Pを選んで操作１を行う際に、もしPのさらに外側に別の頂点P'があったとすると、この操作はP'の存在を除けば操作２と同じ操作になる。従って元々の問題設定の下である可能グラフを得る一連の操作は、拡張された問題設定の下で対応する一連の操作を行い、最後に余分な両端点を削除することと同値である。（拡張された問題設定で最初の操作を行った後のグラフは、３頂点の棒状グラフで中央の頂点が白であり、それが元々の問題設定での出発点のグラフG1に対応する。）

　この拡張された問題設定について、以下の性質を証明する：

  • 性質２：拡張された問題設定における可能グラフで、両端点以外の頂点が全て白であるグラフは以下の２種類であり、またそれらに限られる。
    • 両端点以外の頂点が全て白であり、頂点数が３の倍数で、両端点の色がそれぞれ出発点のグラフG1'におけるその頂点の色と異なっている。
    • 両端点以外の頂点が全て白であり、頂点数を３で割ると２余り、両端点の色がそれぞれ出発点のグラフG1'におけるその頂点の色と同じである。

性質１と性質２を合わせると求める条件（＊）が示されるので、性質２を証明すれば充分である。

その２種類のグラフが実際に可能グラフであること

頂点数に関する数学的帰納法で証明する。頂点数が６以下の場合は下の図より可能グラフである。（両端点の色について特定の組み合わせしか図示していないが、他の色の組み合わせでも同じ理由で成り立つ。また各操作で追加した頂点に印を付けた。以下も同様。）

頂点数が７以上のとき、両端点の色を変えずに真ん中の頂点を３個減らしたグラフは帰納法の仮定より可能グラフであり、そこから下図の操作で所望のグラフが作れるのでやはりそれも可能グラフである。

よってこの性質は確かに成り立つ。

可能グラフがその２種類に限られること

頂点数に関する数学的帰納法で証明する。頂点数が５以下の場合は、可能グラフは対称性を除いて下図のものに限られるので確かにこの性質が成り立つ。

次に、頂点数が６以上で、両端点以外の頂点が全て白である可能グラフGを考える。便宜的に、Gの頂点を端から順にP1、P2、・・・、Pnと名付ける。このときP1とPn以外の頂点は全て途中で操作２によって追加されたものである。P2が追加されたときに選ばれた辺の２頂点のうち、P1以外のものはPkであったと仮定する（kは3からnのいずれか）。

その後P3からPk-1までがある順序で追加されることになるが、その際P2とPkに挟まれた部分は、それ自体が「拡張された問題設定」の状況である。（P2とPk、およびそれらを結ぶ辺だけからなる部分的なグラフを出発点のグラフとみなす。）ただしPkの色の推移はPk+1からPn-1までの箇所の操作に影響されるので、Pkの色の推移だけは無視して考えることにする。

さて、P2が追加された直後のP2は白であり、最終的なグラフGにおけるP3からPk-1とP2はまた全て白である。帰納法の仮定より、この部分的な可能グラフは上に挙げた２種類の場合のいずれかにあてはまることになるが、この部分的なグラフの端点P2の色が変化していないことから、２種類のうち前者の種類ではあり得ず、後者の種類に確定する。つまり、この部分的なグラフの頂点数k-1は３で割ると２余り、またP3からPk-1までの頂点を追加した操作によるPkの色への影響は（全て互いに打ち消されて）無いことになる。従って、kは３の倍数であり、最終的なグラフGから頂点P3、・・・、Pk-1を削除してP2とPkを直結させたグラフG'もまた、拡張された問題設定の下での可能グラフとなる。実際、グラフGを作る一連の操作から、P3、・・・、Pk-1を追加する操作のみ省くことで、グラフG'を作る一連の操作が得られる。（P3からPk-1までを追加した操作による、P1およびPk+1、・・・、Pnの色への影響は無いことに注意。）
帰納法の仮定より、G'は上に挙げた２種類の場合のいずれかにあてはまることになる。従って、G'に両端点以外の３の倍数個の白頂点を付け加えたグラフGも、また上に挙げた２種類の場合のいずれかにあてはまる。よって確かに、可能グラフは上に挙げた２種類に限られる。


以上により性質２が示され、従って上に述べた注意より、所望の性質（＊）も証明された。
（証明終わり）

感想

確かに、知識レベルだけ見ると決して高校数学の範囲を逸脱してはいないと思います。分野としては「グラフ理論」という（下手すると大学理系でも習わないかもしれない）進んだ分野の問題ですが、問題の理解に必要な予備知識は全て出題中で与えられていますし、グラフ理論に関する予備知識が必要なわけでもありません。

ただし、要求される数学的能力や数学センスは、客観的に見て通常の高校生のレベルを大きく超越していると思います。一例として、（少なくとも私の解答の方針では）性質１と性質２を統一的に扱うために補助的な両端点を追加するとか、またより強力な「数学的帰納法の仮定」に基づいて証明を進めるために所望の性質（＊）より強い性質（性質２）を証明のターゲットとする、といったテクニックは、私が大学受験生だった頃に発想して使いこなすことができたとは思えません。（一応私もその前年、1997年の後期日程試験を数学受験で突破した人間なので、普通の高校生よりはかなり高い数学力を当時備えていたはずです。）
個人的にはこの問題は数学系大学院修士課程の入試で出題されていても違和感の無い（むしろ難しい？）レベルの問題だと思いますが、冒頭に紹介したまとめサイトによると２名も完答者がいたとのことです。それらの方々に、数学のプロの一人として、またかつての受験生として心から敬意を表します。

おまけ：河合塾の解答速報における同問題の解答について

上述のまとめサイトのコメント欄でURLが紹介されていましたが、河合塾が当時発表した解答速報における同問題の解答例は http://kaisoku.kawai-juku.ac.jp/nyushi/honshi/98/answer/t2/math/6.gif のようです。

こんな鬼問題にいち早く解答を出さなければならなかった当時の速報の中の人には心底同情しますが、それはそれとして私の見解としてはこの解答は不十分だと思います。
具体的には、「白色の頂点から作られる棒状グラフの集合と黒色の頂点から作られる棒状グラフの集合には共通部分が無い」という性質を自明なものとして扱っています（証明のアウトラインすら記載されていない）が、これは決して自明な性質ではないと思います。（そもそも本当に正しいのでしょうか？）
この発想自体は、見たときに面白い発想だなぁと感心しましたし、速報なので紙面の制限があったのかもしれませんが、せめて正しい証明を再構築できる程度のアウトラインは載せておいていただきたかったと思います。
（もし簡単な証明があるようでしたら、ご教示下さいますととても嬉しいです。）