抽屉原理

参考资料

• 抽屉原理 - OI Wiki

简介

抽屉原理，亦称鸽巢原理（Pigeonhole Principle）。

它常被用于证明存在性证明和求最坏情况下的解。

抽屉原理

将 $n+1$ 个物品放入 $n$ 个抽屉中，物品最多的抽屉中至少有 $2$ 个。

将 $n$ 个物品放入 $k$ 个抽屉中，物品最多的抽屉中至少有 $\lceil\frac{n}{k}\rceil$ 个。