基本鳩の巣原理

背理法のため、結論が成り立たないと仮定する:$k$ 個の箱のそれぞれが高々 $1$ 個の物しか含まないとする。

このとき分配された物の総数は高々 $k\times1=k$ である。

しかし実際には $n$ 個の物を分配しており、仮定より $n>k$ であるから、分配された物の総数は $n>k$ である。

同じ物の集合に対するこの2つの数え方は矛盾する($n>k$ であると同時に総数 $\le k$ でもある)。したがって仮定は誤りであり、少なくとも1つの箱には少なくとも $2$ 個の物が入らなければならない。