抽屉原理

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

简单情况

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

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

推广

将 个物体，划分为 组，那么至少存在一个分组，含有大于或等于 个物品。

推广的形式也可以使用反证法证明：若每个分组含有小于 个物体，则其总和 矛盾。

此外，划分还可以弱化为覆盖结论不变。
给定集合 , 一个 的非空子集构成的簇

• 若满足 则称为 的一个覆盖（cover)
• 若一个覆盖还满足 则称为 的一个划分。

鸽巢原理可以有如下叙述：对于 的一个覆盖 有至少一个集合 满足 。

参考文献

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

build本页面最近更新：2021/8/6 23:58:35，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：Enter-tainer, Great-designer, hehelego, Ir1d, ksyx, MegaOwIer, ranwen, StudyingFather, william-song-shy
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论