【SPONSORED LINK】

鳩の巣原理の基本と使い方

数学で重要な定理の一つに,「鳩の巣原理」というものがあります.「引き出し原理」「ディリクレ(Dirichlet)の箱入れ原理」ともいうこともあります.

非常に簡単な定理で,内容を聞くと,

「うん,そらそうやろうな」

と思う人も多いことでしょう.

高校ではあまり習いませんが,大学受験の数学にも出ることがありますし,驚くべき威力を発揮することもあります.

この記事では,「鳩の巣原理」の説明し,例を挙げて考えてみます.

【SPONSORED LINK】

鳩の巣原理とは?

さて,次のことは正しいでしょうか?

「5人いればその中に同じ血液型の人がいる」

まあ,正しいですね.血液型はA,B,O,ABの4つですから,5人いればそのうちのどれかは2人いることになります.

この事実はまさに「鳩の巣原理」によるもので,「鳩の巣原理」は次のように述べられます.

[鳩の巣原理] nmはともに正の整数で,n>mを満たすとする.n個のものをm組に分けるとき,少なくとも1つの組は2個以上の対象を含む.

要するに,n>mとして,n個のボールをm個の箱に分けて入れると,どれか1つの箱には2つ以上のボールが入っているということです.

さっきの血液型の例では,n=5m=4ですね.

「5人をA型,B型,AB型,O型と4種類に分けるとき,5>4からA型,B型,AB型,O型の少なくとも1つは2人以上いる」ということです.

「鳩の巣原理」という名前を意識すると,「n羽の鳩をm個の巣に移すとき,n>mならば少なくとも1つの巣には2羽の鳩がいる」ということになります.

「当たり前やん!」

そう,当たり前です.私も初めて聞いたときはそう思いました.ですが,冒頭にも書いた通り,大学入試でも鳩の巣原理を用いる問題があり,鳩の巣原理がとても有効に使えることがあるのは知っておいて損はないでしょう.

なお,鳩の巣原理は数学オリンピックでは頻出の定理で,鳩の巣原理を用いて解く問題が多く出題されています.数学オリンピックの過去問も売られているので挙げておきますね.

  • 数学オリンピック2012〜2016(数学オリンピック財団 著,日本評論社)
  • 数学オリンピックチャンピオンの美しい解き方(テレンス・タオ 著,青土社)

余談ですが,後者の「数学オリンピックチャンピオンの美しい解き方」の著者のテレンス・タオ氏は,24歳にしてカリフォルニア大学ロサンゼルス校正教授になっています.

数学最高峰の賞であるフィールズ賞も受賞しており,おそらく世界でもっとも数学ができる人でしょう.

試しに「テレンス・タオ 逸話」で検索してみるととても面白いかもしれませんね.

鳩の巣原理の問題の例

さて,「鳩ノ巣原理の例題といえばこの問題」と言っても良いほど有名な次の問題を解いてみます.

問)1辺の長さが10の正方形の内部に10個の点を任意に取る.この10個の点からうまく2点を選んで2点間の距離を5未満とできることを示せ.

[考え方]

鳩の巣原理を使うには「何を巣とするか」「何を鳩とするか」が重要です.

問題を少し読み替えると「距離が5未満となるような2点が少なくとも1組存在することを示せ」なので,「10個の点を9個のグループに分けて,このうちのどれか1グループには2個の点が存在する.」という方針でいこうと思います.

つまり,10個の点は10羽の鳩と見ています.次に9個の巣はどのように取ればいいのかと考えます.

この10個の点にとっての世界は1辺の長さが10の正方形です.

ですから,正方形を9個に分割してみようと考えるわけです.正方形を9つに分割すると,その分割の少なくとも1つの中には2個の点が存在します.

鳩の巣原理

曲線で分割したりギザギザな折れ線で分割したり,正方形の分割はいろいろ考えられますが,一番自然な方法は各辺を3等分して9つの小正方形に分割する方法でしょう.

この分割をすると,1つの小正方形の1辺の長さは\dfrac{10}{3}なので,対角線の長さは\dfrac{10\sqrt{2}}{3}です.

小正方形の内部の2点で最も距離が長いのは2点が向かい合う頂点にあるときですから,この対角線の長さが5未満であることを証明すればOKです.

これは証明できるでしょうか?

ひねられても応用できる数学の勉強法1|証明編1】で証明は結果からさかのぼって考える逆算が考えやすいと書きました.

\dfrac{10\sqrt{2}}{3}<5であることを示すためには,両辺に\dfrac{3}{10}をかけた\sqrt{2}<1.5が成り立つことを示さなければなりません.

\sqrt{2}はおよそ1.41ですから\sqrt{2}<1.5が確かに成り立ちます.\sqrt{2}<1.5は近似ではなく,きちんと論証しなければなりませんが,とりあえずこの方針で証明できそうなことは分かりました.

[考え方終]

それでは解答を書きます.

[解答]

正方形の各辺を3等分し,図のように正方形を9個の小正方形に分割する.

このとき,鳩の巣原理により,9個の小正方形のいずれか1個は周及び内部に2個の点を含む.この小正方形をAとする.

Aの2点間の距離が最大となるのは2点が向かい合う頂点にあるときなので,Aの対角線の長さが1.5未満であることを示せばよい.

Aの1辺の長さは\dfrac{10}{3}なので,Aの対角線の長さは\dfrac{10\sqrt{2}}{3}である.

\dfrac{10\sqrt{2}}{3} <\dfrac{10\sqrt{2.15}}{3} =\dfrac{10\!\cdot\!1.5}{3} =5

だから,Aの対角線の長さは5未満であることが分かったので,題意は示された.

[解答終]

関連記事

以下,関連記事です.

【良いと思ったらシェアを!】

SNSでもご購読できます。