1. 高校数学の美しい物語
  2. 鳩ノ巣原理を使う数学オリンピックの問題

鳩ノ巣原理を使う数学オリンピックの問題

更新日時 2021/03/07
鳩ノ巣原理

nn 人を mm グループに分けると nm\lceil \dfrac{n}{m}\rceil 人以上いるグループが少なくとも1つは存在する。

x\lceil x\rceilxx 以上の最小の整数を表します。例 3=3,103=4\lceil 3\rceil=3,\lceil \dfrac{10}{3}\rceil=4

目次
  • 鳩ノ巣原理

  • 鳩ノ巣原理を用いた簡単な例題

  • 数学オリンピックの過去問

  • 数学オリンピックの過去問その2

鳩ノ巣原理

非常に当たり前な主張ですが,難関大学の入試では鳩ノ巣原理を知らないと厳しい問題が出題されることもあります。

また,鳩ノ巣原理は数学オリンピックでは超頻出です。CC(組み合わせ)分野の中で最も重要なテクニックと言っても過言ではありません。

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

鳩ノ巣原理を用いた簡単な例題

問題1

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問です。

問題2

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

方針

背理法で証明します。直角三角形を作り出すために,各辺と垂直な3つの線分で三角形を構成します。鳩ノ巣原理で n=3,m=2n=3,m=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 に属する直角三角形なので矛盾。

数学オリンピックの過去問その2

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

問題3

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 となり題意は示された。

鳩ノ巣原理はディリクレの原理とも言います。

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

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

数学オリンピック対策の公式まとめ

人気記事
  1. 高校数学の美しい物語
  2. 鳩ノ巣原理を使う数学オリンピックの問題