形式陈述

若有限集合 $A,B$$A,B$ 满足 $|A|>|B|$$|A|>|B|$，则不存在从 $A$$A$ 到 $B$$B$ 的单射。更一般地，把 $N$$N$ 个对象分到 $k$$k$ 个容器，至少一个容器含有 $\lceil N/k\rceil$$\lceil N/k\rceil$ 个对象。

直觉

总容量不足时，碰撞不可避免。证明的关键通常是发现合适的“对象”和“容器”。

例子与边界

任意 13 个人中至少两人出生在同一个月份。原理只保证某个容器拥挤，不指出是哪一个，也不提供寻找方法。

推论与应用

它用于证明重复余数、图中同度顶点、哈希冲突以及组合结构中的存在性结论。

参考资料

• Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th ed., §6.2.
• Miklós Bóna, A Walk Through Combinatorics, 4th ed., Chapter 2.