定理已证明
推广的抽屉原理
命题陈述
如果把 n 件物品分配到 k 个盒子中,那么必有一个盒子装有至少 ⌈n/k⌉ 件物品。
为什么成立?
基本原理只能保证某处有 2 件物品;推广版本把这一点精确化为把 n 件物品平均分配到 k 个盒子时被迫达到的确切最小值,使用相同的反证思路,但与 ⌈n/k⌉−1 而不是 1 比较。
证明思路
为反证,假设每个盒子都至多装有 ⌈n/k⌉−1 件物品。
那么分配出去的物品总数至多为 k(⌈n/k⌉−1)。
由于 ⌈n/k⌉ 是不小于 n/k 的最小整数,故 ⌈n/k⌉−1<n/k,于是 k(⌈n/k⌉−1)<k⋅kn=n。
于是分配出去的总数严格小于 n,这与全部 n 件物品都已分配相矛盾。因此必有一个盒子装有至少 ⌈n/k⌉ 件物品。