ワンステップ数学３<br>鳩ノ巣原理の基本と使い方のコツを解説

次のことは当たり前ですね？

４つの巣に５羽の鳩が集まっているとき，どこかの巣には鳩が２羽以上いる．

より一般に「巣より鳩の方が多いとき，どこかの巣には鳩が２羽以上いる」といえますね．

この論法のことを数学では鳩ノ巣原理といいます．鳩の巣原理の他に引き出し原理やディリクレ(Dirichlet)の箱入れ原理ということもあります．

当たり前すぎて「定理というほどのことか？」と訝しむ人もいらっしゃるかもしれませんが，適切に用いればあっという間に解けてしまう問題も少なくありません．

高校数学ではそれほど積極的に学ぶ機会のない定理ではありますが，大学受験の数学にも出ることもあるので一度は触れておきたい話題のひとつです．

数学オリンピックでは鳩ノ巣原理を用いる問題は頻出です．

この記事では

鳩ノ巣原理とは何か？
鳩の巣原理を用いて解ける問題の例

を順に説明します．

鳩の巣原理とは？
鳩の巣原理の問題
1. 問題１
2. 問題２

鳩の巣原理とは？

冒頭で述べたことを，もう少しきちんと表現すると次のようになりますね．

[鳩ノ巣原理]　$m$, $n$を正の整数とする．$m$個の対象を$n$組に分けるとき，$n<m$なら少なくとも１つの組には対象が２個以上属する．

「鳩ノ巣原理」という名前を意識すると，「$m$羽の鳩を$n$個の巣に集めるとき，$m>n$なら少なくとも１つの巣には鳩が２羽いる」ということになりますね．

鳩以外の具体例を挙げるなら，人の血液型はA型，B型，AB型，O型の４種類なので，５人いれば少なくとも１つの血液型には２人以上属していることになりますね．

このように，鳩の巣原理は「ペアの存在を示す問題」に使えそうな定理だと分かりますね．

このタイプの鳩の巣原理が最も簡単なものですが，もう少し発展させた次の定理も成り立ちますね．

[鳩ノ巣原理（発展）]　$m$, $n$, $k$を正の整数とする．$m$個の対象を$n$組に分けるとき，$kn<m$なら少なくとも１つの組には対象が$k+1$個以上属する．

例えば，９人いれば少なくとも１つの血液型には３人以上属していることになりますが，これは発展版の鳩の巣原理の$k=2$の場合になっていますね．

鳩の巣原理の問題

それでは，鳩ノ巣原理の威力を見て頂きましょう．

問題１

１辺の長さが$10$の正方形の内部に１０個の点を任意に取る．この１０個の点からうまく２点を選べば２点間の距離を$5$未満とできることを示せ．

この問題を「距離が$5$未満となるような２点が少なくとも１組存在することを示せ」と読み替えれば，「ペアの存在証明」ですから鳩の巣原理が使えないか考えましょう．

この問題で１０個の点でペアを作ることになるので

「１０個の点を９個のグループに分けて，このうちのどれか１グループには２個の点が存在する」

という方針を採りましょう．

つまり，正方形を９個に分割すればどんな分け方であっても，その分割の少なくとも１つの中には２個の点が存在することになりますね．

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

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

よって，あとは$\dfrac{10\sqrt{2}}{3}<5$を示せばよいですね．

正方形を図のように合同な９個の小正方形に分割する．

このとき，鳩ノ巣原理により９個の小正方形のいずれか１個は周及び内部に２個の点を含む．この小正方形をAとする．

小正方形Aの周および内部にある２点間の距離が最大となるのは２点が向かい合う頂点にあるときであり，小正方形Aの１辺の長さは$\dfrac{10}{3}$なので，対角線の長さは$\dfrac{10\sqrt{2}}{3}$である．

$\begin{align*} \frac{10\sqrt{2}}{3}<\frac{10\sqrt{2.25}}{3}=\frac{10\cdot 1.5}{3}=5 \end{align*}$

だから，Aの対角線の長さは$5$未満なのでAに含まれる２点を選べば，この距離は$5$以下である．

問題２

少し難しい問題も考えておきます．

正の整数$n$に対して，$1$以上$2n$以下の$n+1$個の整数を考える．このとき，一方の整数が他方の整数を割り切るような2整数が存在することを示せ．

$n+1$個の整数の中に，一方の整数が他方の整数を割り切るような整数のペアが存在することを示すので，鳩ノ巣原理を使う場合には「巣」を$n$個用意することになります．

ここでポイントになるのは

1以上$2n$以下の$2n$個の整数の中には，$n$個の奇数が存在する．
もし自然数$k$が自然数$\ell$を割り切るとき，$k$に含まれる重複を含めた素因数は$\ell$の素因数としても含まれる．

の２つです．

１つ目のポイントから，$n+1$個の整数を奇数になるまで2で割ってできた$n+1$個の奇数の中には等しい奇数$a$, $b$ ($a=b$)が存在します．

２つ目のポイントから，この等しい２つの奇数$a$, $b$の2で割る前のもとの自然数は，素因数2の個数だけが違うので，一方が他方を割り切ることになりますね．

$1$以上$2n$以下の$n+1$個の整数を全て奇数になるまで$2$で割ると，「$n+1$個の奇数」$\dots(*)$ができる．

$1$以上$2n$以下の奇数は全部で$n$個存在するから，鳩ノ巣原理より$(*)$の中に等しい２つの奇数$a$, $b$ ($a=b$)が存在する．

この等しい奇数$a$, $b$を$2$で割る前の整数は，それぞれ$2^{k}\cdot a$, $2^{\ell}\cdot b$と表せる．

$a$, $b$は対称だから$k\geqq\ell$としてよく，このとき$a=b$より

$\begin{align*} \frac{2^{k}\cdot a}{2^{\ell}\cdot b}=2^{k-\ell} \end{align*}$

となる．$2^{k-\ell}$は整数だから，$2^{\ell}\cdot b$は$2^{k}\cdot a$を割り切る．

以上より，題意が従う．

ワンステップ数学３
鳩ノ巣原理の基本と使い方のコツを解説

鳩の巣原理とは？

鳩の巣原理の問題

問題１

問題２

コメント