【SPONSORED LINK】

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

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

鳩の巣原理とは?

鳩の巣原理は例えば次のような定理です.

「血液型は4種類しかないので,人が5人いればこの中に同じ血液型の人がいる」

4人まではその中の全員の血液型が異なることはありますが,5人以上になると必ず同じ血液型の人が存在しますね.

同様に,「n個のものをA_1,A_2,\dots,A_mとm種類に分けるとき,n>mならばA_1,A_2,\dots,A_mの少なくとも1つには2個以上含まれている.」というのが鳩の巣原理です.

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

【SPONSORED LINK】

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

「当たり前やん!」

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

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

数学オリンピック2010~2014

数学オリンピック2005~2009

数学オリンピックの問題集はなかなか売れないのでしょうか.ちょっと値段が高めです.しかし,数学に自身のある人は挑戦してみるのもいいかもしれません.

鳩の巣原理の問題の例

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

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

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

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

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

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

鳩の巣原理

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

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

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

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

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

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

[考え方終]

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

[解答]

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

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

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

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

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

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

[解答終]

関連記事

以下,関連記事です.

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

SNSでもご購読できます。