鳩の巣原理
印象的な例
「ロンドンに髪の毛の本数が同じ人がいる」ということの論証に利用する．
たとえば「ロンドンには、同じ本数の髪の毛を持った少なくとも2人の人間が存在する」。証明してみよう。ふつう、髪の毛の本数は15万本ほどであるから、100万本以上の髪の毛を持っている人間はいないと考えることができる。ロンドンの人口は100万を超える。もし、髪の毛の本数ごとに鳩の巣を割り当て、巣にロンドンの人々を割り当てるなら、（当然の下限である0本から上限として置いた99万9999本までの巣に100万を超える人々を割り当てるのだから）少なくとも同じ髪の毛の本数を持った2人の人間が必ず存在する。
しかし，髪の毛の本数が同じ人が何人いるのかとか，髪の毛の本数が同じ人のその本数は?とかの問には答えられない．
前述した「ロンドンには、同じ本数の髪の毛を持った少なくとも2人の人間が存在する」ということの証明の面白いところは、同じ本数の髪の毛の人が存在することを証明しているにもかかわらず、具体的にどの2人が同じ本数の髪の毛を持つのかは分からないということである。鳩の巣原理を使った証明にはこのような特徴をもつものが多く、何らかの性質を満たすものが存在することを証明するにもかかわらず、どれがその性質を満たすのかについては何も分からない。 もちろん100万人以上いるロンドン市民の髪の毛の本数を全員チェックすればどの２人が同じ本数の髪の毛を持つのか分かるが、このような非効率的なことをしなくても定理が証明できるのが鳩の巣原理の利点である。 (チェックが多項式時間でできないにもかかわらず、鳩の巣原理により存在性のみが言える例もある)。
実用
ハッシュテーブルが必ず重複してしまうことの証明．
感想
鳩の巣のような格子状の物体を眺めていて思い出した．
半年間の間に確実に読んだ記事なのだが， 人に説明できるレベルまで詳細は思い出せなかったのが 悔しかった ので，記録しておく．
