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

鳩ノ巣原理：
$n$ 人を $m$ グループに分けると $⌈ \frac{n}{m} ⌉$ 人以上いるグループが少なくとも1つは存在する。

$⌈ x ⌉$ は $x$ 以上の最小の整数を表します。例 $⌈ 3 ⌉ = 3, ⌈ \frac{10}{3} ⌉ = 4$

鳩ノ巣原理

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

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

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

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

問題1

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

証明

$3 \times 3$ の正方形を $1 \times 1$ の小正方形 $9$ 個に分割する。鳩ノ巣原理より， $10$ 個の点の中に同じ小正方形に属する $2$ 点が存在する。同じ小正方形に属する $2$ 点の距離は $\sqrt{2}$ 以下なので題意は示された。

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

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

問題2

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

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

証明

直角三角形が存在しないと仮定する。
$E$ を2つに分割したグループ名を $X$ ， $Y$ と書くことにする。
三辺 $A B, B C, C A$ を $1 : 2$ に内分する点を $P, Q, R$ とおくと， $A B ⊥ R P, B C ⊥ P Q, C A ⊥ Q R$
鳩ノ巣原理により $P, Q, R$ の中で少なくとも2点は同じグループに属する。対称性より， $P, Q$ が $X$ に属するとしても一般性を失わない。

（以下かんたん）
(i)辺 $B C$ 上の $Q$ 以外のある点 $D$ が $X$ に属している場合
三角形 $P Q D$ は3点が $X$ に属する直角三角形なので矛盾

(ii)辺 $B C$ 上の $Q$ 以外の全ての点が $Y$ に属している場合
(ii-a) $R$ が $Y$ に属する場合
$R$ から $B C$ に下ろした垂線の足を $S$ とおくと，三角形 $R S C$ は3点が $Y$ に属する直角三角形なので矛盾。
(ii-b) $R$ が $X$ に属する場合
(i)の議論より， $P, Q, R$ 以外全て $Y$ に属す必要がある。このとき $A$ から $B C$ に下ろした垂線の足を $M$ とおくと，三角形 $A M C$ は3点が $Y$ に属する直角三角形なので矛盾。

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

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

問題3

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

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

証明

$23$ 以下の素数は $9$ 個。それぞれの素因数のベキの偶奇でグループわけを行う。つまり， $M$ の要素を $2^{9} = 512$ グループにわける。同じグループのものは掛け合わせると平方数になるので，鳩ノ巣原理から，かけて平方数（ $= n_{1}^{2}$ ）になるペア $(a_{1}, b_{1})$ が存在する。残り $1983$ 個の数に対しても同様な議論を用いると，かけて平方数（ $= n_{2}^{2}$ ）になるペア $(a_{2}, b_{2})$ が存在する。
これを（頑張れば730回くらい繰り返せるけど） $513$ 回繰り返してかけて平方数（ $= n_{i}^{2}$ ）になるペア $(a_{i}, b_{i})$ を $513$ 個作る。

さらに， $n_{i}$ たちに同様な議論を適用することで $n_{i} n_{j}$ が平方数（ $= n^{2}$ ）になるようなペアが存在することが分かる。よって， $a_{i} b_{i} a_{j} b_{j} = n_{i}^{2} n_{j}^{2} = n^{4}$ となり題意は示された。

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

Tag: 国際数学オリンピックの過去問
Tag: 数学Aの教科書に載っている公式の解説一覧
★数学オリンピック対策の公式まとめ