札幌の予備校・塾|大学受験(英語・数学)は札幌のマンツーマン個別指導塾、高上へお電話ください!大学受験において偏差値を上げる塾ですので、生徒の地力を底上げします。札幌駅、大通り駅にある予備校・塾のマンツーマン個別指導塾高上は、大学受験の英語、数学、物理、化学を静かな環境の個室で指導します。周りの声が邪魔になることはありません。英作文の添削、スカイプでの指導も全国どこからでも随時受け付けております。
お気軽にお問い合わせください。
TEL:080-1885-3972
受付時間:10:00~21:00
年中無休(相談などについては要予約)
※指導中はお電話に出られません。
お問い合わせページよりご連絡ください。
公開日:2021年4月3日
最終更新日:2021年5月17日

はじめに

この記事では,1998年の東京大学後期理科数学の第3問 (2) の解答例を紹介します.この問題は大学入試数学の難問として有名です.高校までの数学では習わない「グラフ理論」という分野を題材とした問題です.
この解答は高上の講師のアイデアを清書したものです.今のところ,(2) の解答のみを載せますが,後日完全な解答を載せる予定です.

問題

掲載予定.

解答例

(1)

掲載予定.(1) は簡単です.

(2)

(2) の難しいところは,「\(n\) 個の頂点の色がすべて白である棒状のグラフが可能グラフならば,\(n \equiv 0, 1 \bmod 3\)」の証明です.\(n \equiv 0, 1 \bmod 3\) ならば,所望のグラフが可能グラフであることは簡単に示せますが,逆はそうはいきません.
ネット上にある解答では,\(1\) 個の白頂点から出発して各操作によって得られるグラフ(可能グラフ)の集合と \(1\) 個の黒頂点から出発して各操作によって得られるグラフの集合を考え,それら二つの集合が交わらないことを不変量を用いて示しています.特に,後者に属する頂点がすべて白の可能グラフの頂点数 \(n\) は必ず \(n \equiv 2 \bmod 3\) となります.
この記事の解答では,黒頂点に挟まれた白頂点の和を考えています.

(2) の解答

棒状のグラフのみを考える.すべて頂点の色が白のグラフを白グラフとよぶ.頂点数が \(n\) のグラフを \(G_n\) と書く.出発点のグラフ \(G_1\) の唯一の頂点を \(P_1\) とおき,\(G_n\) に対する操作によって加えられた頂点を \(P_{n + 1}\) とおく.
まず,\(n \equiv 0, 1 \bmod 3\) ならば,白グラフ \(G_n\) は可能グラフであることを示す.
白グラフ \(G_n\) が可能グラフならば,白グラフ \(G_{n + 3}\) は可能グラフである.グラフの右端の頂点に対して,操作 \(1\) を \(2\) 回適用し,得られたグラフの右から \(2\) 番目の辺に対して操作 \(2\) を \(1\) 回適用すればよい.白グラフ \(G_1\) が可能グラフであることは明らかである.また,(1) より,白グラフ \(G_3\) も可能グラフである.したがって,\(n \equiv 0, 1 \bmod 3\) ならば,白グラフ \(G_n\) は可能グラフである.
次に,白グラフ \(G_n\) が可能グラフならば,\(n \equiv 0, 1 \bmod 3\) であることを示す.グラフ \(G_k\) の黒頂点の個数を \(b_k\) とおき,\(G_k\) の両端に黒頂点が加えられたと仮定し(それらは黒頂点の個数には加えない),黒頂点間の白頂点の個数を考える.また,各操作によって \(G_1\) から \(G_k\) を得るまでに,頂点 \(P_1\) またはそれより左の頂点に対して操作 \(1\) が左から適用された回数を \(l_k\) とおく.黒頂点間の白頂点の個数それぞれに \(1\) を加えた数をグラフの左から順に \(a_{k,l_k,1},\) \(a_{k,l_k,2}, \dotsc\), \(a_{k,l_k,b_k+1}\) とし,$$\begin{align}X_k &= \sum_{i + l_k\text{が奇数}} a_{k,l_k,i},\\ Y_k &= \sum_{i + l_k\text{が偶数}} a_{k,l_k,i}\end{align}$$とおく.グラフ \(G_k\) から \(G_{k+1}\) を得る1回の任意の操作において,$$\begin{align} X_{k+1} &= X_k – 1,\\Y_{k+1} &= Y_k + 2\end{align}$$または$$\begin{align}X_{k+1} &= X_k + 2,\\Y_{k+1} &= Y_k – 1\end{align}$$となる.ここで,\(-1 \equiv 2 \bmod 3\) より,いずれの場合も$$\begin{align} X_{k+1} &\equiv X_k + 2 \bmod 3,\\Y_{k+1} &\equiv Y_k + 2 \bmod 3\end{align}$$となる.出発点のグラフ \(G_1\) から \(n – 1\) 回の操作によって \(G_n\) を得たとき,\(X_1 = 2,\) \(Y_1 = 0\) より,$$\begin{align}X_n &\equiv 2 + 2(n-1) \\&\equiv 2n \bmod 3,\\Y_n &\equiv 2(n-1) \\&\equiv 2n + 1\bmod 3\end{align}$$となる.さらに,\(G_n\) が白グラフかつ可能グラフならば,$$\begin{align}X_n &= n + 1,\\ Y_n &= 0\end{align}$$または$$\begin{align}X_n &= 0,\\ Y_n &= n+1\end{align}$$である.前者ならば,\(n \equiv 1 \bmod 3\), 後者ならば, \(n \equiv 0 \bmod 3\) となる.したがって,白グラフ \(G_n\) が可能グラフならば,\(n \equiv 0, 1 \bmod 3\) である.
よって,白グラフ \(G_n\) が可能グラフになるために \(n\) のみたすべき必要十分条件は$$n \equiv 0, 1 \bmod 3$$である.

細かい場合分けチェックが大変ですが,グラフと操作の対称性から,操作 \(1\) は右からの操作のみを考えればよいです.左からの操作の回数を考えているのは,単に \(X_k,\) \(Y_k\) を計算するための位置合わせです.

この記事の著者

ャに
記事一覧

高上は医学部合格率80%!
結果が出る指導を受けてみませんか?

 医学部合格実績を見る 

著者一覧