抽屉原理
定义
抽屉原理，亦称鸽巢原理（the pigeonhole principle）．
它常被用于证明存在性证明和求最坏情况下的解．
简单情况
将 𝑛 +1n+1
个物体，划分为 𝑛n 组，那么有至少一组有两个（或以上）的物体．
这个定理看起来比较显然，证明方法考虑反证法：假如每个分组有至多 11 个物体，那么最多有 1 ×𝑛1×n 个物体，而实际上有 𝑛 +1n+1 个物体，矛盾．
推广
将 𝑛n 个物体，划分为 𝑘k 组，那么至少存在一个分组，含有大于或等于 ⌈𝑛𝑘⌉⌈nk⌉ 个物品．
推广的形式也可以使用反证法证明：若每个分组含有小于 ⌈𝑛𝑘⌉⌈nk⌉ 个物体，则其总和 𝑆 ≤(⌈𝑛𝑘⌉ −1) ×𝑘 =𝑘⌈𝑛𝑘⌉ −𝑘 <𝑘(𝑛𝑘 +1) −𝑘 =𝑛S≤(⌈nk⌉−1)×k=k⌈nk⌉−k<k(nk+1)−k=n 矛盾．
此外，划分还可以弱化为覆盖结论不变． 给定集合 𝑆S, 一个 𝑆S 的非空子集构成的簇 {𝐴1,𝐴2…𝐴𝑘}{A1,A2…Ak}
- 若满足 ⋃𝑘𝑖=1𝐴𝑖⋃i=1kAi 则称为 𝑆S 的一个覆盖（cover）
- 若一个覆盖还满足 𝑖 ≠𝑗 →𝐴𝑖 ∩𝐴𝑗 =∅i≠j→Ai∩Aj=∅ 则称为 𝑆S 的一个划分．
鸽巢原理可以有如下叙述：对于 𝑆S 的一个覆盖 {𝐴1,𝐴2…𝐴𝑘}{A1,A2…Ak} 有至少一个集合 𝐴𝑖Ai 满足 |𝐴𝑖| ≥⌈|𝑆|𝑘⌉|Ai|≥⌈|S|k⌉．
参考文献
- Wikipedia: Pigeonhole principle
- _Discrete Mathematics and Its Applications_ : Chapter 6, Section 1
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Ir1d, Enter-tainer, MegaOwIer, Tiphereth-A, StudyingFather, Xeonacid, aofall, CoelacanthusHex, Great-designer, hehelego, iamtwz, ksyx, Marcythm, Persdre, ranwen, shuzhouliu, william-song-shy 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用