跳转至

# 抽屉原理

## 定义

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

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

## 简单情况

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

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

## 推广

将 𝑛 n 个物体，划分为 𝑘 k 组，那么至少存在一个分组，含有大于或等于 ⌈𝑛 𝑘⌉⌈n k⌉ 个物品．

推广的形式也可以使用反证法证明：若每个分组含有小于 ⌈𝑛 𝑘⌉⌈n k⌉ 个物体，则其总和 𝑆 ≤(⌈𝑛 𝑘⌉ −1) ×𝑘 =𝑘⌈𝑛 𝑘⌉ −𝑘 <𝑘(𝑛 𝑘 +1) −𝑘 =𝑛 S≤(⌈n k⌉−1)×k=k⌈n k⌉−k<k(n k+1)−k=n 矛盾．

此外，划分还可以弱化为覆盖结论不变．
给定集合 𝑆 S, 一个 𝑆 S 的非空子集构成的簇 {𝐴 1,𝐴 2…𝐴 𝑘}{A 1,A 2…A k}

- 若满足 ⋃𝑘 𝑖=1 𝐴 𝑖⋃i=1 k A i 则称为 𝑆 S 的一个覆盖（cover）
- 若一个覆盖还满足 𝑖 ≠𝑗 →𝐴 𝑖 ∩𝐴 𝑗 =∅i≠j→A i∩A j=∅ 则称为 𝑆 S 的一个划分．

鸽巢原理可以有如下叙述：对于 𝑆 S 的一个覆盖 {𝐴 1,𝐴 2…𝐴 𝑘}{A 1,A 2…A k} 有至少一个集合 𝐴 𝑖 A i 满足 |𝐴 𝑖| ≥⌈|𝑆|𝑘⌉|A i|≥⌈|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 协议之条款下提供，附加条款亦可能应用