鳩ノ巣原理の意味と例(身近な例から超難問まで)

鳩ノ巣原理

44 個のもの33 グループに分けると,必ず 22 個以上属するグループが存在する。 鳩ノ巣原理のイメージ

より一般に,mm 個のものnn 個のグループにわける。mmnn より大きいなら,必ず2つ以上のものが属するグループが存在する。

ものの数がグループ数よりも多いので当たり前ですね。この当たり前な主張を鳩ノ巣原理と言います。

鳩ノ巣原理の身近な例

まずは,身近な例です。

5人いれば,血液型が同じ2人組が存在します。

血液型をA型,O型,B型,AB型の4種類として,「5人を4グループに分ける」状況で鳩ノ巣原理を使うとわかります。

367人いれば,誕生日が同じ2人組が存在します。

誕生日は366通りとして,「367人を366グループに分ける」状況で鳩ノ巣原理を使うとわかります。

ちなみに,鳩ノ巣原理にはいろいろな言い方・書き方があります。

  • 鳩ノ巣原理(mm 羽の鳩を nn 個の巣にグループわけするイメージ)
  • 鳩の巣原理
  • 部屋割論法
  • ディリクレの箱入れ原理

有名な問題(倍数・格子点)

鳩ノ巣原理を使って簡単な問題を解いてみましょう。

問題1

44 つの整数 a,b,c,da,b,c,d がある。この中から 22 つ選べば,その差を 33 の倍数にできることを証明せよ。

解答

a,b,c,da,b,c,d33 で割った余りに注目して 33 グループに分けると,鳩ノ巣原理より,とある同じグループに 22 個以上属する。その 22 個は 33 で割った余りが同じなので差が 33 の倍数になる。

問題1は整数の問題でしたが,他にも座標や図形などいろいろな分野で鳩ノ巣原理は活躍します。難関大学の入試では鳩ノ巣原理を知らないと厳しい問題もあります。いろいろな問題に慣れておきましょう。

次は,1996年の早稲田大学の入試問題です。

問題2

xyxy 座標平面において,互いに異なる5個の格子点を任意に選ぶと,その中に「2点を結ぶ線分の中点が格子点」になるような2点が存在することを示せ。

ただし,格子点とは,xx 座標,yy 座標がともに整数である点のこと。

解答

5つの格子点を,xx 座標,yy 座標がそれぞれ奇数か偶数かで4グループに分ける。

つまり,(奇,奇),(奇,偶),(偶,奇),(偶,偶) の4グループ。

すると,鳩ノ巣原理より同じグループに属する2点が存在する。偶奇が等しい整数の平均は整数なので,その2点の中点は格子点となる。

鳩ノ巣原理を使う難問

鳩ノ巣原理は数学オリンピックでは頻出です。CC(組み合わせ)分野の中で最も重要なテクニックの1つと言えます。

数学オリンピックでは鳩ノ巣原理を知っていることは前提で,それをうまく応用できるかが問われます。応用力を身につけるためには鳩ノ巣原理に関する問題をたくさん解いて経験を積むのが一番です。

図形の問題

問題3

3×33\times 3 の正方形内に 1010 個の点を打ったとき,その中で距離が 2\sqrt{2} 以下となる2点が存在することを証明せよ。

解答

鳩ノ巣原理

3×33\times 3 の正方形を 1×11\times 1 の小正方形 99 個に分割する。鳩ノ巣原理より,1010 個の点の中に同じ小正方形に属する 22 点が存在する。同じ小正方形に属する 22 点の距離は 2\sqrt{2} 以下なので目標の主張が示された。

1983年国際数学オリンピックフランス大会の第4問です。

問題4

正三角形 ABCABC において,3つの辺上の点全体の集合を EE とおく。 EE を2つに分割するとき,どちらか一方は直角三角形をなす3点を含むことを示せ。

方針

背理法で証明します。直角三角形を作り出すために,各辺と垂直な3つの線分で三角形を構成します。鳩ノ巣原理で m=3,n=2m=3,n=2 としたものを用います。あとは愚直に場合わけをしていずれの場合も直角三角形が構成できることを示せばOKです。

証明

直角三角形が存在しないと仮定する。

EE を2つに分割したグループ名を XXYY と書くことにする。

三辺 AB,BC,CAAB,BC,CA1:21:2 に内分する点を P,Q,RP,Q,R とおくと,ABRP,BCPQ,CAQRAB\perp RP,BC\perp PQ, CA\perp QR

鳩ノ巣原理により P,Q,RP,Q,R の中で少なくとも2点は同じグループに属する。対称性より,P,QP,QXX に属するとしても一般性を失わない。

鳩ノ巣原理の例題

(以下かんたん)

(i)辺 BCBC 上の QQ 以外のある点 DDXX に属している場合

三角形 PQDPQD は3点が XX に属する直角三角形なので矛盾

(ii)辺 BCBC 上の QQ 以外の全ての点が YY に属している場合

(ii-a) RRYY に属する場合

RR から BCBC に下ろした垂線の足を SS とおくと,三角形 RSCRSC は3点が YY に属する直角三角形なので矛盾。

(ii-b) RRXX に属する場合

(i)の議論より,P,Q,RP,Q,R 以外全て YY に属す必要がある。このとき AA から BCBC に下ろした垂線の足を MM とおくと,三角形 AMCAMC は3点が YY に属する直角三角形なので矛盾。

整数の問題

次は,1985年国際数学オリンピックフィンランド大会の第4問です。

問題5

MM を1985個の異なる自然数からなる集合とする。いずれの自然数も 2323 より大きい素因数は持たない。このとき MM の要素のうち 44 つをうまく選べばそれらの積が自然数の4乗の形で書けることを示せ。

方針

素因数のべきでグループわけします。直接鳩ノ巣原理を用いようとしてもうまくいきません。まずは積が平方数となる2つの数の組をたくさん集めて,さらにそれを2つ合体させて所望の数を獲得します。

解答

2323 以下の素数は 99 個。それぞれの素因数のベキの偶奇でグループわけを行う。つまり,MM の要素を 29=5122^9=512 グループにわける。同じグループのものは掛け合わせると平方数になるので,鳩ノ巣原理から,かけて平方数(=n12=n_1^2 )になるペア (a1,b1)(a_1,b_1) が存在する。残り 19831983 個の数に対しても同様な議論を用いると,かけて平方数(=n22=n_2^2 )になるペア (a2,b2)(a_2,b_2) が存在する。

これを(頑張れば730回くらい繰り返せるけど)513513 回繰り返してかけて平方数(=ni2=n_i^2 )になるペア (ai,bi)(a_i,b_i)513513 個作る。

さらに,nin_i たちに同様な議論を適用することで ninjn_in_j が平方数(=n2=n^2 )になるようなペアが存在することが分かる。よって,aibiajbj=ni2nj2=n4a_ib_ia_jb_j=n_i^2n_j^2=n^4 となり目標の主張が示された。

鳩ノ巣原理の応用

鳩ノ巣原理が活躍する他の例です。

鳩ノ巣原理の一般的な主張とその証明

さきほどの鳩ノ巣原理よりも強い以下の主張が成立します。

鳩ノ巣原理(一般の場合)

mm 個のものを nn グループに分けると mn\left\lceil \dfrac{m}{n}\right\rceil 個以上からなるグループが少なくとも1つは存在する。

ただし,mn\left\lceil \dfrac{m}{n}\right\rceil とは,mn\dfrac{m}{n} 以上の最小の整数を表します。

99 人を 44 グループにわけると,33 人以上いるグループが少なくとも1つは存在する。
m=9,n=4m=9,n=4 の例。94=3\left\lceil \dfrac{9}{4}\right\rceil=3 になる)

鳩ノ巣原理が成り立つことの証明

背理法で証明する。各グループに属する個数が mn1\left\lceil \dfrac{m}{n}\right\rceil-1 以下と仮定すると,

個数の合計 mmn×(mn1)n\times\left(\left\lceil \dfrac{m}{n}\right\rceil-1\right) 以下である。

つまり,mn(mn1)m\leq n\left(\left\lceil \dfrac{m}{n}\right\rceil-1\right)

これを変形すると

mn+1mn\dfrac{m}{n}+1\leq \left\lceil \dfrac{m}{n}\right\rceil

となるが,これは「mn\left\lceil \dfrac{m}{n}\right\rceilmn\dfrac{m}{n} 以上の最小の整数」に矛盾。

なぜ「鳩の巣原理」ではなく「鳩ノ巣原理」のように「の」をカタカナで書くことが多いのでしょうかね。

Tag:国際数学オリンピックの過去問

Tag:数学Aの教科書に載っている公式の解説一覧