抽屉原理

定义

抽屉原理，亦称鸽巢原理（the pigeonhole principle）。

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

简单情况

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

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

推广

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

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

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

若满足 $⋃_{i = 1}^{k} A_{i}$ 则称为 $S$ 的一个覆盖（cover）
若一个覆盖还满足 $i \neq j \to A_{i} \cap A_{j} = \emptyset$ 则称为 $S$ 的一个划分。

鸽巢原理可以有如下叙述：对于 $S$ 的一个覆盖 ${A_{1}, A_{2} \dots A_{k}}$ 有至少一个集合 $A_{i}$ 满足 $| A_{i} | \geq ⌈ \frac{| S |}{k} ⌉$ 。

参考文献

Wikipedia: Pigeonhole principle
Discrete Mathematics and Its Applications: Chapter 6, Section 1

本页面最近更新：2023/5/6 19:22:00，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Ir1d, Enter-tainer, MegaOwIer, StudyingFather, Tiphereth-A, Xeonacid, aofall, CoelacanthusHex, Great-designer, hehelego, iamtwz, ksyx, Marcythm, Persdre, ranwen, shuzhouliu, william-song-shy
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用