抽屉原理

抽屉原理, 又称鸽巢原理、鸽笼原理, 是组合学中的基本结论, 它说明, 若将 $n$ 个物品放入 $m$ 个抽屉, 且 $n>m$, 则必有一个抽屉中有至少两个物品. 更一般地, 若 $n>km$, 其中 $k$ 是自然数, 则必有一个抽屉中有至少 $k+1$ 个物品.

1叙述

对有限集

定理 1.1 (抽屉原理). 设 $A,B$ 为有限集, 并记 $|A|=n$, $|B|=m$.

•	若 $n>m$, 则不存在 $A$ 到 $B$ 的单射.

•	更一般地, 若 $n>km$, 其中 $k$ 是自然数, 则对任意映射 $f:A\to B$, 存在 $b\in B$, 使得 $|f^{-1}(b)|>k$.

对无限集

定理 1.2 (抽屉原理). 设 $A,B$ 为集合.

•	若 $|A|>|B|$, 则不存在 $A$ 到 $B$ 的单射.

•	更一般地, 若 $|A|>\alpha |B|$, 其中 $\alpha$ 是基数, 则对任意映射 $f:A\to B$, 存在 $b\in B$, 使得 $|f^{-1}(b)|>\alpha$.

注意到, 定理的第一条实际上是平凡的, 因为该性质正是集合论中对不等式 $|A|>|B|$ 的定义.

术语翻译

抽屉原理 • 英文 pigeonhole principle • 德文 Schubfachprinzip (n) • 法文 principe des tiroirs (m) • 日文 鳩の巣原理 (はとのすげんり) • 韩文 비둘기집 원리