一般化された鳩の巣原理

背理法のため、すべての箱が高々 $\lceil n/k\rceil-1$ 個の物しか含まないと仮定する。

このとき分配された物の総数は高々 $k\left(\lceil n/k\rceil-1\right)$ である。

$\lceil n/k\rceil$ は $n/k$ 以上の最小の整数であるから、$\lceil n/k\rceil-1<n/k$ であり、したがって $k\left(\lceil n/k\rceil-1\right)<k\cdot\frac{n}{k}=n$ となる。

よって分配された総数は $n$ より真に小さく、$n$ 個すべての物が分配されたことと矛盾する。したがって少なくとも1つの箱には少なくとも $\lceil n/k\rceil$ 個の物が入る。