　【SPONSORED LINK】

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

2015/6/11 2019/10/29 ワンステップ数学

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

耳慣れない名前の定理かもしれませんが，内容を聞くと「当たり前やん！」と思えるほど簡単な定理です．

高校ではあまり積極的には習いませんが，大学受験の数学にも出ることがあり，適切に用いれば驚くべき威力を発揮します．

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

【SPONSORED LINK】

目次

1 解説動画
2 鳩の巣原理とは？
3 鳩の巣原理の問題
- 3.1 問題1
- 3.2 問題2
4 参考文献

解説動画

この記事の解説動画もアップロードしています．

「チャンネル登録」「コメント」「高評価」は，今後の動画作成の励みになるので，是非よろしくお願いします！

こちらから【チャンネル登録】ができますので，ぜひ応援よろしくお願いします！

鳩の巣原理とは？

次の[主張]を考えます．

[主張]　5人いれば，その中に同じ血液型の人がいる

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

したがって，この主張は正しいですね．

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

[鳩ノ巣原理]　正の整数 $n$ に対して， $n+1$ 個以上の[対象]を $n$ 組に分けるとき，少なくとも1つの組は2個以上の[対象]を含む．

「鳩ノ巣原理」という名前を意識すると，「 $n+1$ 羽以上の鳩を $n$ 個の巣に移すとき，少なくとも1つの巣には2羽の鳩がいる」ということになります．

上で書いた血液型の例は， $n=4$ の場合ですね．

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

どうでしょう．直感的には当たり前ではないでしょうか？

私も初めて聞いたときは「当たり前やん！」と思いました．

ですが，この当たり前な内容の定理が，非常に強力な武器になることがあるのです．冒頭にも書いた通り，大学入試でも鳩ノ巣原理を用いる問題があり，鳩ノ巣原理がとても有効に使えることがあります．

鳩の巣原理の問題

では，鳩ノ巣原理を用いて問題を解いてみます．

問題1

まずは1問目です．

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です．

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

以前の記事【ひねられても応用できる数学の勉強法１｜証明編１】で証明は結果からさかのぼって考える逆算が考えやすいと書きました．

$\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の対角線の長さが5未満であることを示せばよい．

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

$\dfrac{10\sqrt{2}}{3}<\dfrac{10\sqrt{2.25}}{3}=\dfrac{10\cdot 1.5}{3}=5$

だから，Aの対角線の長さは5未満であることが分かった．

以上より，題意が従う．

[解答終]

問題2

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

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

[考え方]

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

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

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

の2つです．

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

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

[考え方終]

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

[解答]

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

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

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

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

$\dfrac{2^{k}\cdot a}{2^{\ell}\cdot b}=2^{k-\ell}$

となる．

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

以上より，題意が従う．

[解答終]

参考文献

実は，鳩ノ巣原理は数学オリンピックでは頻出の定理で，鳩ノ巣原理を用いて解く問題が多く出題されています．

数学オリンピックの過去問も売られているので挙げておきますね．

数学オリンピック2014-2018(数学オリンピック財団著，日本評論社)
Amazon 楽天市場
数学オリンピックチャンピオンの美しい解き方(テレンス・タオ著，青土社)
Amazon 楽天市場

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

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

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