抽屉原理

这本质上是一个计数命题,通过反证法证明:如果每个盒子至多装 $1$ 件物品,那么所有盒子总共容纳的物品数不可能超过 $k$。

为反证,假设结论不成立:$k$ 个盒子中的每一个都至多装有 $1$ 件物品。

那么分配出去的物品总数至多为 $k\times1=k$。

但我们分配的是 $n$ 件物品,且由假设 $n>k$,所以分配出去的物品总数是 $n>k$。

对同一批物品的这两种计数相互矛盾($n>k$,但总数又 $\le k$),所以反证假设不成立:必有一个盒子装有至少 $2$ 件物品。

基本原理只能保证某处有 $2$ 件物品;推广版本把这一点精确化为把 $n$ 件物品平均分配到 $k$ 个盒子时被迫达到的确切最小值,使用相同的反证思路,但与 $\lceil n/k\rceil-1$ 而不是 $1$ 比较。

为反证,假设每个盒子都至多装有 $\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$ 件物品都已分配相矛盾。因此必有一个盒子装有至少 $\lceil n/k\rceil$ 件物品。