証明問題を解く上で最も基本的な道具のひとつである，鳩ノ巣原理 (はとのすげんり) について解説します．
いま，鳩の巣が $5$ 個あり，鳩が $6$ 羽いるとしましょう．これらの鳩を鳩の巣にどのようにいれたとしても，$2$ 羽以上の鳩が入っている箱が少なくともひとつ存在します．ただし，下右図のように，$1$ 羽もいれない巣があってもよいとします．
この主張はほとんど当たり前ですよね．(これを当たり前と思える人間の知性に感謝！)
鳩ノ巣原理 (部屋割り論法，ディリクレの引き出し原理) とは，この当たり前とも思えるつぎの命題のことをいいます．
鳩ノ巣原理： $n,m$ を自然数，$n > m$ とする．$n$ 個のものを $m$ 組にわけるとき，少なくともひとつの組は $2$ 個以上のものを含む．
この非常に基本的な命題が，数学の証明問題を解く上で幅広く役立つのです．
前節の鳩ノ巣原理をより精密にしてみましょう．たとえばいま，鳩の巣が $5$ 個あり，鳩が $72$ 羽いるとしましょう．前節の命題より，これらの鳩を鳩の巣にどのようにいれても，$2$ 羽以上の鳩が入っている箱が少なくともひとつ存在します．しかし，この $2$ という数字は考えられる最大の整数なのでしょうか？ 直感的に，$5$ つの巣に $72$ 羽もいれるのですから，もっと強い主張が言えるのではないかという気がします．実際，この場合は，$15$ 羽以上の鳩が入っている箱が少なくともひとつ存在するというより強い主張が言えます．一方で，『$16$ 羽以上の鳩が入っている箱が少なくともひとつ存在する』ということは残念ながら言えません．実際，($15,15,14,14,14$) という風に割り振ればよいです．
次の命題は，前節の鳩ノ巣原理を精密化したものです．
鳩ノ巣原理 (精密化)： $n,m$ を自然数，$n > m$ とする．$n$ 個のものを $m$ 組にわけるとき，少なくともひとつの組は $\lceil \frac{n}{m} \rceil$ 個以上のものを含む．
証明： (背理法) $i (1\le i \le m)$ 番目の組に含まれているものの個数を $a_i$ とする．全ての組が $\lceil \frac{n}{m} \rceil$ 未満のものを含んでいるとする．すなわち， $$a_i < \left\lceil \frac{n}{m} \right\rceil (1\le i \le m)$$ とする．両辺整数なので， $$a_i \le \left\lceil \frac{n}{m} \right\rceil-1 (1\le i \le m)$$ が従う．したがって， $$n=\sum_{i=1}^m a_i \le \sum_{i=1}^m \left(\left \lceil \frac{n}{m} \right \rceil-1\right)=m\left(\left \lceil \frac{n}{m} \right \rceil-1\right)$$ となる．最左辺と再右辺をくらべると， $$\frac{n}{m}+1 \le \left \lceil \frac{n}{m} \right \rceil$$ となるが， $$\frac{n}{m} \le \left \lceil \frac{n}{m} \right \rceil
さて，具体的な問題を通して，鳩ノ巣原理に慣れましょう．
例題 鳩と鳩の巣がある．鳩を鳩の巣にいれるとき，つぎの $\boxed{\phantom{\text{aaaa}}}$ に当てはまる最大の整数を求めよ． ($1$) 鳩が $6$ 羽，鳩の巣が $7$ 個のとき，少なくとも一つの鳩の巣には $\boxed{\phantom{\text{aaaa}}}$ 羽以上いる． ($2$) 鳩が $21$ 羽，鳩の巣が $7$ 個のとき，少なくとも一つの鳩の巣には $\boxed{\phantom{\text{aaaa}}}$ 羽以上いる． ($3$) 鳩が $100$ 羽，鳩の巣が $6$ 個のとき，少なくとも一つの鳩の巣には $\boxed{\phantom{\text{aaaa}}}$ 羽以上いる．
($1$) $1$ ($2$) $3$ ($3$) $17$
上の問題のポイントは，最大の整数を聞かれていることです．たとえば，($3$) で，鳩が $100$ 羽，鳩の巣が $6$ 個のとき，少なくとも一つの鳩の巣には $17$ 羽以上いることは言えますが，$18$ 羽以上いるということは言えません．一方で，たとえば，少なくとも一つの鳩の巣には $10$ 羽以上いることは言えますが，これは $17$ 羽以上いるという主張よりも弱い主張です．つまり，『鳩が $100$ 羽，鳩の巣が $6$ 個のとき，少なくとも一つの鳩の巣には $17$ 羽以上いる』というのは，数学的に確実に言える最も強い主張といえます． このように，数学的に確実に言える最も強い主張が何なのかを意識することが重要です．
問 任意に与えられた相異なる $5$ つの整数 $a,b,c,d,e$ に対して，その中から適当に $2$ つの整数を選んで，その差を $4$ の倍数にすることができる．これを示せ．
整数を $4$ で割った余りは $0,1,2,3$ のいずれかです．いま，$5$ つの整数 $a,b,c,d,e$ が与えられているので，鳩の巣原理より，この中には $4$ で割った余りが等しい $2$ つの整数が存在します．それらの差は必ず $4$ の倍数になります．
問 $xy$ 平面において，$x$ 座標，$y$ 座標がともに整数である点を格子点と呼ぶ．いま，互いに異なる $5$ つの格子点を任意に選ぶと，その中に次の性質を満たす格子点のペアが少なくともひとつ存在することを示せ．
性質： 一組の格子点を結ぶ線分の中点が，格子点となる．
$xy$ 平面上の点は次の $4$ 種類に分類できる． ($1$) $x$ 座標が偶数で，$y$ 座標が偶数 ($2$) $x$ 座標が偶数で，$y$ 座標が奇数 ($3$) $x$ 座標が奇数で，$y$ 座標が偶数 ($4$) $x$ 座標が奇数で，$y$ 座標が奇数
いま，$5$ つの格子点をえらんでいるので，鳩の巣原理より，分類が同じ $2$ 点が必ず存在します．それらの中点は必ず格子点になります．
問 『誕生月が同じ人が少なくとも $3$ 人いる』ということが確実に言えるためには，少なくとも何人の人を集めなければならないか．
誕生月は $12$ 種類．したがって，$25$ 人の人を集めればよい．
問 $n$ を自然数とする．いま，平面上の相異なる点に $2n+1$ 人の観測者が立っている．各観測者間の距離はすべて相異なる．各観測者は最も近い観測者を観測している．このとき，観測されていない観測者が少なくとも一人いることを示せ．
帰納法で示す．$n=1$ のとき，距離が最も近い $2$ 人の観測者 $A,B$ を考えると，この $2$ 人の観測者はお互いを観測しあっている．したがって，残りの観測者 $C$ は観測されていない． $n=k$ のとき，題意が成り立つと仮定する． $n=k+1$ のとき，観測者をそれぞれ $A_1,…,A_{2k+3}$ とする．一般性を失うことなく，距離が最も近い $2$ 人の観測者を $A_1,A_2$ としてよい．この $2$ 人はお互いを観測しあっている． ($1$) $A_3,…,A_{2k+3}$ の中に，$A_1,A_2$ を観測している者がいないときこのときは帰納法の仮定から，($A_3,…,A_{2k+3}$ はお互いを観測しあっていることになるので) $A_3,…,A_{2k+3}$ の中に，観測されていない者が少なくとも $1$ 人いる． ($2$) $A_3,…,A_{2k+3}$ の中に，$A_1,A_2$ を観測している者がいるとき
このとき，$A_3,…,A_{2k+3}$ の $2k+1$ 人を観測している者は $2k$ 人以下なので，鳩の巣原理より，$A_3,…,A_{2k+3}$ の中に観測されていない者が存在する．
