抽屉原理

抽屉原理（pigeonhole principle）说明：把比抽屉数更多的物品分别放进抽屉，至少有一个抽屉含有两件或更多物品。这里“抽屉”可以是实际的容器，也可以是一种分类，例如整数的余数、人的出生月份，或记录所处的某个状态。它把一个关于总数的事实，转化成“某一类中必有重复”的结论。

考虑把 11 件物品放入 4 个箱子，每件物品恰好放在一个箱子里。至少有一个箱子含有 3 件物品：如果每箱至多 2 件，四箱总共至多有 8 件，放不下全部 11 件。这一结论与摆放顺序、箱子外观、随机与否都无关。

从物品总数得到一个必然结论

用 $n_{1}, n_{2}, n_{3}, n_{4}$ 表示四个箱子中的物品数。它们都是非负整数，并且

$n_{1} + n_{2} + n_{3} + n_{4} = 11.$

若四个数全都不超过 2，左边便不超过 $4 \times 2 = 8$ ，与等式矛盾。这就是证明中的关键：先假设我们想保证的情况完全没有发生，再计算所有箱子最多能容纳多少物品。

下图给出一种实际分配 $(3, 3, 3, 2)$ 。它不仅满足“某箱至少有 3 件”，还说明仅凭 11 件、4 箱这两个信息，不能保证某箱有 4 件，因为图中就没有这样的箱子。

尽量均匀地摆放，可以看见整数下界为什么恰好是 3。图是一种达到下界的分配，前面的总数论证覆盖所有分配。

最基本的形式是：若 $N > m$ ，把 $N$ 件物品分到 $m$ 个箱子，每件恰入一箱，则某箱至少有两件。证明只需把刚才的“每箱至多 2 件”换成“每箱至多 1 件”。箱子允许空着；若有空箱，其余箱子更难避免重复。MIT：Pigeonhole Principle

广义形式为什么要向上取整

设 $N, m$ 都是正整数。把 $N$ 件物品分入 $m$ 个箱子，至少有一个箱子的物品数达到

$⌈ \frac{N}{m} ⌉ .$

符号 $⌈ x ⌉$ 表示不小于 $x$ 的最小整数，叫作向上取整。例如 $⌈ 11 / 4 ⌉ = 3$ ，而 $⌈ 12 / 4 ⌉ = 3$ ，整数本来已满足要求，不再增加一。

平均每箱有 $N / m$ 件，至少一箱不能低于这个平均数；箱中物品数又必须是整数，所以最低保证值要向上取整。可以把这段理由写成严格的反证。令 $r = ⌈ N / m ⌉$ ，假设每箱都不足 $r$ 件，则每箱至多 $r - 1$ 件。然而

$r - 1 < \frac{N}{m}, m (r - 1) < N .$

于是所有箱子合起来至多 $m (r - 1)$ 件，小于已知总数 $N$ ，矛盾。因此某箱至少有 $r$ 件。

这个下界在一般情况下不能再提高。把整数除法写成

$N = q m + s, 0 \leq s < m .$

先给每箱放 $q$ 件，再给其中 $s$ 个箱子各加一件。如果 $s = 0$ ，最大箱数为 $q = N / m$ ；如果 $s > 0$ ，最大箱数为 $q + 1 = ⌈ N / m ⌉$ 。这就构造出恰好达到保证值的分配。

反过来，给定正整数 $r$ ，若要无论如何分配，都保证有一箱至少 $r$ 件，所需的最少物品数是

$m (r - 1) + 1.$

因为 $m (r - 1)$ 件仍可每箱恰放 $r - 1$ 件，再多一件就无法维持这个上限。例如 4 箱要保证有一箱至少 4 件，需要 13 件；12 件还可以分成 $(3, 3, 3, 3)$ 。

抽屉可以是一种函数分类

实际运用时，最有用的一步通常是选好分类规则。设有限集合 $A$ 是物品，有限集合 $B$ 是可用标签，给每件物品指定一个标签就是函数 $f : A \to B$ 。标签相同的物品放进同一个“抽屉”。

当 $| A | > | B |$ 时， $f$ 不可能是单射：必有两个不同物品 $a_{1}, a_{2}$ 满足 $f (a_{1}) = f (a_{2})$ 。否则每个标签至多接收一件物品，全部标签也只能容纳 $| B |$ 件。

这种说法交代了模型的两个条件：每件物品都获得标签，而且每件只获得一个标签。如果分类有重叠，应先规定重叠对象归入哪一类；如果有对象不属于任何一类，原来的抽屉计数就漏掉了物品。分类可以很巧妙，但分配规则必须明确。

例如，从整数里任取五个不同的数，按除以 4 的余数分类。整数除法保证余数恰是 $0, 1, 2, 3$ 中的一个，所以只有四个抽屉。五个整数中至少两个余数相同；若它们写成 $4 u + r$ 与 $4 v + r$ ，相减便得到 $4 (u - v)$ 。因此至少两个数的差能被 4 整除。

在具体一组数 $2, 5, 8, 11, 14$ 中，余数分别为 $2, 1, 0, 3, 2$ 。下图的余数 2 类同时收到了 2 和 14；它们的差为 $14 - 2 = 12$ 。没有必要让原来的整数大小接近，真正重要的是它们落入同一个余数类。

用余数作抽屉，把“两个数之差可整除”的目标变成“两个标签相同”。

一般地，任取 $m + 1$ 个整数，都有两个差能被正整数 $m$ 整除。这正是同余关系为抽屉原理提供分类的一个例子。

把连续一段的和变成两个前缀的差

下面的问题看起来不再是“两个数同类”：给定正整数 $n$ 和任意 $n$ 个整数 $a_{1}, \dots, a_{n}$ ，能否找到连续的一段，长度至少为一，使这段的和能被 $n$ 整除？答案是一定可以。

先看五个数 $2, 4, 1, 3, 2$ 。把从开头起的和依次记下来，并加上一个尚未取任何数时的和 $S_{0} = 0$ ：

已取项数 $j$	0	1	2	3	4	5
前缀和 $S_{j}$	0	2	6	7	10	12
除以 5 的余数	0	2	1	2	0	2

前缀和 $S_{1} = 2$ 和 $S_{3} = 7$ 余数相同。把它们相减，第一项被消掉，只剩第 2 至第 3 项：

$S_{3} - S_{1} = (a_{1} + a_{2} + a_{3}) - a_{1} = a_{2} + a_{3} = 4 + 1 = 5.$

下图突出标出这两个前缀边界。被截出的连续一段位于两个边界之间，而不是任意选出的几个数。

物品是六个前缀和，抽屉是五种余数；先找到重复余数，再用相减找回连续的一段。

一般证明沿着同样的步骤。定义

$S_{0} = 0, S_{j} = a_{1} + \dots + a_{j} (1 \leq j \leq n) .$

共有 $n + 1$ 个前缀和，却只有 $n$ 种模 $n$ 的余数。由抽屉原理，存在两个不同下标 $0 \leq i < j \leq n$ ，使 $S_{i} \equiv S_{j} (\mod n)$ 。因此

$S_{j} - S_{i} = a_{i + 1} + \dots + a_{j} \equiv 0 (\mod n) .$

因为 $i < j$ ，这段确实非空。整数可以为负数，也可以为零，证明仍成立；余数按 $0, \dots, n - 1$ 的通常约定取值。引入 $S_{0}$ 很有用：若某个前缀和本身能被 $n$ 整除，它就与 $S_{0}$ 归入同一类，不必另分一种情况。

证明也给出了寻找方法：从左到右计算前缀余数，记录每个余数第一次出现的位置。再次遇到相同余数时，用这两个位置截取原序列。这比逐一检查所有连续片段更直接。

结论的边界

抽屉原理保证的是至少存在一个符合要求的抽屉，不是每个抽屉都如此，也不指定哪一个。11 件物品可以全部放入同一箱，其余三箱为空；这仍满足“有一箱至少三件”。

“物品比箱子多”的严格不等式也不能随便改成等号。四件物品分四箱时，可以各放一件，从而完全没有重复。类似地，保证至少 $r$ 件的门槛是 $m (r - 1) + 1$ ，少一件就存在平均分配的反例。

有限性在这里有实质作用。无限多个对象分入有限个箱子时，至少一箱含有无限多个对象：若每箱都有限，有限个有限集合的并仍有限。但若箱子也有无限多个，重复不再必然出现，例如把第 $k$ 个对象放入第 $k$ 个箱子，每箱仍只有一个。

这一原理也不能单凭总数给出概率。“一定有重复”是对所有分配的结论；“某个指定箱子重复的可能性有多大”还需要随机机制，属于概率问题。

历史与参考资料

抽屉原理也常称狄利克雷抽屉原理。它与数论中按有限类别寻找重复的证明方法关系密切。由戴德金整理、1863 年初版的狄利克雷《数论讲义》中，相关论证被用于 Pell 方程问题；当时的论证并没有固定使用今天的名称。MacTutor 的术语史还记录了 1941 年 Raphael M. Robinson 论文中的英语 “pigeonhole principle” 用法，说明“抽屉”和“鸽巢”是同一计数思想的不同比喻。圣安德鲁斯大学 MacTutor：Pigeonhole Principle 术语史

Michel Goemans，Pigeonhole Principle，MIT 18.310，2013。基本形式、广义形式与把对象归类的证明方法。
Mathematics for Computer Science：The Pigeonhole Principle，MIT Open Learning Library。以向上取整表示广义下界。
Jeff Miller 等，Earliest Known Uses of Some of the Words of Mathematics，P，MacTutor。Pigeonhole Principle 条目的文献与命名记录。