鳩の巣原理

内容

$n+1$ 個以上の物を $n$ 個の箱に入れるならば、少なくとも一つの箱には二つ以上の物が入る。より一般に、$kn+1$ 個の物を $n$ 個の箱に入れるならば、ある箱には少なくとも $k+1$ 個の物が入る。

なぜ正しいのか?

鳩の数が巣の数より多ければ、どこかの巣に二羽以上入らざるを得ない——容れ物より品物の数が真に多ければ、少なくとも一つの容れ物は二つ以上の品物を持つほかない。当たり前に聞こえるが、単純な個数の不一致だけから繰り返しや衝突を強制するこの技法は、驚くほど強力な証明手法である。

この定理を使うトピック

関連する定理

ステップごとの証明

この定理のステップごとの証明はまだありません。