高校数学の裏技コミュの鳩の巣原理(ディリクレ部屋割り論法)

■1．鳩の巣原理
『n+1羽の鳩とn箱の巣箱があり，全ての鳩がこれらの巣箱のいずれかに入れば，巣のうちのどれか1つには2羽以上の鳩が同居していることになる』

という当たり前の論法を鳩の巣原理(ディリクレの部屋割り論法とも呼ばれる)という．数学的表現にすると，

『DとRを有限集合とする．|D|＞|R|とし，fをDからRへの任意の写像とする．このとき，f(x)=f(y)となるようなx,y∈Dが存在する．』

■2．例題
【例題2】
n個の自然数a[k](k=1,2,…,n)からなる集合Sが与えられているとき，Sのある部分集合でその要素の和がnで割り切れるものが存在することを示せ．
【証明】
b[k]=Σ[i=1,k]a[i]
を満たすようなn個の数b[k](k=1,2,…,n)をつくる．全てのb[k]がnで割り切れないと仮定すると，b[k]をnで割ったときの余りは
　　1,2,…,n-1のどれか
であるから，鳩の巣原理によりnで割った余りが等しい2数が存在する．それらをb[p],b[q](p＜q)とする．すると，
　　b[p]-b[q]=Σ[k=p+1,q]a[k]
はnで割り切れ，しかも，Sの部分集合の和になっている．
よって，Sの部分集合で，要素の和がnで割り切れるものが存在する．

※鳩の巣原理は，『何かある条件を満たすものの存在を示す』ときの初等的かつ強力な武器になります．中間値の定理もこれと同じ理論です．

■3．その他鳩の巣原理で示せる問題

【例題3-1】
5以下の正の数を6つ考える．その中のどれか2つは必ず差が1未満になることを示せ．
(北海道高等学校数学コンテスト)

【例題3-2】
pは3以上の素数で，k=(p-1)/2とする．
(1) 0^2,1^2,2^2,…,k^2をpで割るときの余りは全て異なることを示せ．
(2) 0≦a≦k,0≦b≦kをみたす整数a,bで，a^2+b^2+1がpで割り切れるものが存在することを示せ．
(芝浦工大)

【例題3-3】
空間にn個の格子点の間を結ぶ線分を全て考える．このとき，これらの線分の中点の少なくとも1つが必ず格子点となるためのnの満たすべき条件を求めよ．
(津田塾大)

【例題3-4】
次の不等式を満たす整数a,b,cで，どれか1つは0でなく，かつどの絶対値も2^6以下であるものが存在することを示せ．
|a+b√2+c√3|＜1/2007