ゴールデンな数学に挑戦（その１）
2020年12月24日
先日、twitterを眺めていたら面白いマンガに出会いました。
『数学ゴールデン』です！！：
第一話が試し読みできたのですが、面白すぎて、読み終わった後、即楽天ブックスで第１巻を購入しました^^
数学オリンピックに青春をかける高校生たちの物語ですっ！
『数学ゴールデン』です！！：
数学オリンピックに青春をかける高校生たちの物語ですっ！
胸が熱くなるストーリー展開に加え、数学の問題やその解法が登場するのも数学愛好家の心をくすぐります（笑）
普段はマンガは電子書籍で買っていますが、『数学ゴールデン』は紙版を買って自習室に置いてあります。
是非、当塾の生徒さんも自習の合間の休憩に手に取ってみてください。
もし数学オリンピックに興味がわいたら挑戦してみるのも良いと思います！
私に相談していただければアドバイスもいたします^^！
ちなみに…私は数学オリンピックを受験したことはありません^^;
数学のオリンピックの存在を知ったのが高校２年生くらいのときで（雑誌『大学への数学』の記事で読んだのが最初です。そういえば『ゴールデン』に登場する『数拳』という雑誌は『大数』のオマージュですね^^！）、受験勉強などもあったので、時間的にも実力的にも挑戦する余裕がありませんでした。
さて、前置きが長くなりましたが…今回の記事では、『数学ゴールデン第１巻』に登場した問題を一緒に考えてみようと思います。
問題
17人それぞれが他の全員と互いに手紙のやりとりをしている．その手紙では 3つの話題のみが やりとりされている．
そして、同じ2人組の間でなされる話題は常に同じ一つのやりとりである．このとき、互いに同じ話題の手紙のやりとりをした3人組が存在することを証明せよ。
(IMO 1964)
数学オリンピックでは、ベクトルや微分積分のような（高校で習う）高度な概念を知らなくても、この問題のように小学生でも内容は理解できるような問題も出題されます。
でも、この問題が易しいというワケでは決してありません！！
それでは問題の解説に移りましょう。
最初に問題の「言い換え」を行って、「証明すべきこと」をハッキリさせましょう！！
17人の人をそれぞれ A、B、C、…、P、Q として、さらに正17角形の各頂点にそれぞれを配置します。
手紙でやりとりされる3つの話題をそれぞれ「赤」「青」「緑」の3色に対応させます。例えば、AとBの間でやりとりされる話題に対応する色が「赤」なら、頂点AとBを赤い線分で結びます。同様に、2人の間でやりとりされる話題にあわせて、頂点どうしをその色の線分で結んでいきます。
例えば、下の図のようなものが出来上がります：
問題の主張は、「同じ話題の手紙のやりとりをした3人組」が存在することですが、これはこの図で「3辺が同じ色の三角形」が存在することと言い換えられます。
これは下の図のように確かに存在します：
以下の証明でも、できるだけ同色三角形ができないような配置を考えていくケドどうあがいても同色三角形ができてしまう、という方針で進めていきます！
まず、頂点Aを考えます。頂点Aは他の16個の頂点と16本の線分で結ばれています。16本の線分は3色のいずれかの色ですが、その色は一般的には分かりません。でも、次のことは分かります：
「3色のうちどれかの色は少なくとも6本の線分に使われている」
3色とも5本以下だと、3×5＝15で高々15本の線分しか引けないので、どれかの色は6本以上の線分に使われているはずです。
ここでは、その6本以上の線分に使われている色を「赤」とします。
ここで、「赤」と決めつけていいの？と疑問に思うかもしれませんが大丈夫です！
仮に与えられた配色では「青」が6本以上であっても、以下の議論で「赤」と「青」を入れ替えれば証明はそのまま適応できます。
数学ではこのような「適当な決めつけ」を行って同じ議論の繰り返しを避けたりすることがよくあります。
もちろん一般性を欠いてしまう「悪い決めつけ」もあるので注意が必要ですが、この「適当な決めつけ」を行う能力も数学の学力として重要だと思います。
…話が少しそれましたが、Aと赤い線分で結ばれた頂点が6個以上あるとして、そのうちの6個を B、C、D、E、F、G とします。
これももし頂点が違ったとしても、頂点の名前を付けなおせばすむので、このように「決めつけて」かまいません！
以下、Aも含めた7人を正7角形の頂点に配置して考えましょう：
B、C、D、E、F、G の各頂点もそれぞれ互いに3色の線分で結ばれています。
ここで、それらの線分の中に赤色の線分が1本でも含まれているとすると、
それでは次に、B、C、D、E、F、G を結ぶ線分の中に赤色の線分が1本もない状況を考えます。
ここで頂点の1つBについて考えます。Bは残りの5頂点と「青」または「緑」の線分で結ばれていますが、次のことが分かります：
「2色のうちどちらかの色は少なくとも3本の線分に使われている」
そこで、3本以上の線分に使われているのを「青」と「決めつけて」しまいましょう！
さらに頂点Bと「青」の線分で結ばれた頂点のうち3つを C、D、E と「決めつけて」しまいます。
つまり下図のようになります：
これら3頂点 C、D、E は「青」か「緑」の線分で結ばれていますが、もし「青」の線分で結ばれている頂点どうしがあれば、それらの頂点とBは「青い三角形」をつくり題意が成立することが分かります。
最後に「青」の線分がない場合。C、D、E はそれぞれ「緑」の線分で結ばれていることになりますが、この場合は3頂点 C、D、E が「緑の三角形」をつくることになります：
同色の三角形の存在は、元の問題における同じ話題をやりとりする3人組の存在を示しているので、元の問題も証明できたことになります！！
この問題の背景には「ラムゼーの定理」というものがあります：
ラムゼーの定理
$r,\,k_1,\,k_2,\,\ldots,\,k_r$ を $2$ 以上の整数とする。このとき，次の性質を満たす定数 $R_{r}(k_1,\,k_2,\,\ldots,\,k_r)$ が存在する：$n\geqq R_{r}(k_1,\,k_2,\,\ldots,\,k_r)$ ならば，$n$ 個の点からなる完全グラフの辺をどのように色 $1,\,2,\,\ldots,\,r$ で彩色しても，ある色 $i$ に対して，$k_i$ 個の点からなる色 $i$ の完全グラフが存在する。
- 「ラムゼーの定理」にはより一般化した定理も存在します。また、「完全グラフ」「彩色」などの用語はここでは説明しません。興味のある方は検索してみてください。
私が中高生だった頃と比べて、現在はネットでいろいろと調べられるので、数学などを探求的に学習するには良い時代になったと思います^^
実際には，$R_3(3,\,3,\,3)=17$ だそうです^^
今回ご紹介した『数学ゴールデン』が大ヒットして、日本中で数学オリンピックブームが巻き起こる…そんなことを夢想しております^^
もしそうなれば、多くの中高生（＆おませな小学生も！）が数学オリンピックを目指すことで全体の底上げになり、日本代表のレベルも上がっていくことでしょう！！
今回解説した問題を通して、数学オリンピックやグラフ理論に興味を持ってくれた若者が1人でもいたら嬉しいです^^♪
私もグラフ理論にはあこがれがあって、いつか本格的に勉強したいと思っています！
コメントを残す