鸽巢原理

摘录自 OI-Wiki

抽屉原理，亦称鸽巢原理（the pigeonhole principle)。
它常被用于证明存在性证明和求最坏情况下的解。

简单情况

将 $n+1$ 个物体，划分为 $n$ 组，那么有至少一组有两个（或以上）的物体。

这个定理看起来比较显然，证明方法考虑反证法：假如每个分组有至多 $1$ 个物体，那么最多有 $1\times n$ 个物体，而实际上有 $n+1$ 个物体，矛盾。

推广

将 $n$ 个物体，划分为 $k$ 组，那么至少存在一个分组，含有大于或等于 $\lceil {\displaystyle \frac{n}{k}}\rceil$ 个物品。

推广的形式也可以使用反证法证明：若每个分组含有小于 $\lceil {\displaystyle \frac{n}{k}}\rceil$ 个物体，则其总和 $S\le (\lceil {\displaystyle \frac{n}{k}}\rceil -1)\times k=k\lceil {\displaystyle \frac{n}{k}}\rceil -k<k({\displaystyle \frac{n}{k}}+1)-k=n$ 矛盾。

此外，划分还可以弱化为覆盖结论不变。
给定集合 $S$, 一个 $S$ 的非空子集构成的簇 $\{A_1,A_2\dots A_k\}$

• 若满足 $\bigcup _{i=1}^k{A}_i$ 则称为 $S$ 的一个覆盖（cover)
• 若一个覆盖还满足 $i\ne j\to A_i\cap A_j=\varnothing$ 则称为 $S$ 的一个划分。

鸽巢原理可以有如下叙述：对于 $S$ 的一个覆盖 $\{A_1,A_2\dots A_k\}$ 有至少一个集合 $A_i$ 满足 $\left|A_i\right|\ge \lceil {\displaystyle \frac{\left|S\right|}{k}}\rceil$。

---

最后更新: May 9, 2023