抽屉原理是组合数学中的一条基本计数原理:如果将多于 个物体分配到 个容器中,那么至少有一个容器会分到至少两个物体。这些容器在英语中传统上称为“鸽巢”(pigeonholes),可以代表实际空间、类别、除法余数或任何其他分类。尽管十分初等,这一原理却是证明重复、相合或特定构型必然存在的有力工具。
表述与证明
对于任意正整数 ,如果将 个物体放入 个盒子中,那么至少有一个盒子装有至少两个物体。
用反证法即可立即证明这一结论。假设每个盒子至多装有一个物体,那么物体总数至多为 ,这与共有 个物体矛盾。
这些物体不必相同,盒子不必有实际的边界,也可以有空盒子。关键在于每个物体都恰好分配到一个盒子中。
用集合论的语言来说,如果 和 是有限集,且
那么任何函数 都不可能是单射函数。必然存在不同的元素 ,使得
这里, 表示 的基数。这种表述不借助物体和盒子的比喻,便表达了该原理。
推广形式
保证达到的容纳数量
如果将 个物体分配到 个盒子中,其中 、,那么至少有一个盒子装有至少
个物体。向上取整符号表示不小于其所作用数值的最小整数。
证明如下:令 。如果每个盒子至多装有 个物体,那么物体总数至多为
产生矛盾。
等价地,对于正整数 和 ,将
个物体放入 个盒子,就能保证至少有一个盒子装有至少 个物体。这个阈值是最优的: 个物体可以分配成每个盒子恰好装有 个物体。
与之对应的另一条结论也很有用:至少有一个盒子装有至多
个物体,其中向下取整符号表示不大于其所作用数值的最大整数。这两条结论都反映了每个盒子的平均物体数为 这一事实。
容量不等的情形
假设第 个盒子的容量为非负整数 。如果
那么至少有一个盒子分到的物体数超过其容量。
当各类别允许容纳的数量不同时,这种形式很有用。证明仍采用同样的计数论证:如果每个盒子都不超过容量,那么物体总数就不会超过所有容量之和。
如何应用这一原理
运用抽屉原理时,主要困难通常不在最后的计数步骤,而在于如何选择盒子。典型的应用过程如下:
- 确定要计数的物体。
- 将每个物体分配到一个类别中。
- 证明物体数量太多,不可能使所有类别中的物体数都低于某个指定值。
- 将必然出现的同类现象转化为所需的结论。
盒子可以是余数类、区间、计算的可能输出,或某个数值性质的可能取值。恰当的选择应使“落在同一个盒子中”能够推出有数学意义的结论。
例如,13 个人中至少有两人的出生月份相同:人就是物体,12 个月份就是盒子。更一般地,37 个人中至少有四人的出生月份相同。
在数论中的应用
余数相同
在模算术中,除以正整数 所得的余数只有 种可能:
因此,任意 个整数中,必有两个整数模 的余数相同。它们的差可以被 整除。
这一初等观察是数论中许多论证的基础。整数本身可以任意大;重要的只是它们所属的有限多个余数类。
能被 整除的连续项之和
给定任意一个由 个整数组成的序列
其中必有非空的一段连续项,其和能被 整除。
定义 个部分和:
模 的余数类只有 个,因此有两个部分和的余数相同,不妨记为 和 ,其中 。于是
能被 整除。
将初始和 包含在内,就能用同一个论证同时涵盖从 开始的连续段和从后续项开始的连续段。
有理逼近
这一原理还能给出一个初等的逼近结果。对于任意实数 和正整数 ,都存在整数 和 ,其中 ,使得
考虑下列各数的小数部分:
将 分成 个长度为 的左闭右开区间。这 个小数部分中,必有两个落在同一区间内,因此它们之差的绝对值小于 。将相应的 的倍数相减,可得
其中 和 是适当的整数。再除以 ,便得到所需结论。这是狄利克雷逼近定理的一种标准形式。
在几何学和图论中的应用
在几何学中,将一个区域细分,就能得到一些“盒子”,其尺寸可以限制其中两点之间的距离。
例如,在边长为 的正方形内任取五个点,必有两点的欧几里得距离不超过
将正方形分成四个边长为 的小正方形,并按固定规则将边界上的点归入某一个区域。必有两点落在同一区域内。它们之间的距离不会超过该区域的对角线长度 。
在图论中,抽屉原理可以证明:每个至少有两个顶点的有限简单无向图中,都存在两个度数相同的顶点。对于一个有 个顶点的图,度数看似有以下可能值:
然而,度数 和 不可能同时出现:一个与其余所有顶点都相邻的顶点,不可能与孤立顶点共存。因此, 个顶点的度数至多只有 种取值,必然出现重复。
这个例子展示了一种重要技巧:结构上的约束可以使可用盒子的数量少于最初看起来的数量。
计算与信息的局限
在计算机科学中,将较大的有限输入集映射到较小的输出集的函数,必然会将某些不同输入映射到同一个输出。这种现象称为碰撞。例如,输出为 位的哈希函数只有 种可能的输出值。如果其输入域包含超过 个元素,就必然存在碰撞。
同样的计数论证也限制了无损压缩的能力。长度为 的二进制串共有 个,而长度严格小于 的二进制串(包括空串)只有
个。无损编码必须为不同输入分配不同的表示。因此,不存在一种编码,既能缩短每一个 位二进制串,又能保证仅凭编码后的表示就恢复原串。
这些是关于存在性和不可能性的结论,而不是关于效率的结论。证明碰撞存在,并不意味着能够迅速找到碰撞。
无限版本与局限
将一个无限集划分为有限多个类别,其中至少有一个类别是无限的。否则,每个类别都是有限集,它们的有限并集也将是有限集。这一结论通常称为无限抽屉原理。
类别数量有限这一要求至关重要。无限多个物体可以分配到无限多个盒子中,使每个盒子恰好装有一个物体。同样,无限集并不遵循所有适用于有限情形的直觉:无限集可以与它自身的某个真子集具有相同的基数。例如, 将非负整数集单射且满射地映射到正整数集。
有限抽屉原理也不需要概率或随机分配。它的结论对每一种允许的安排都成立。另一方面,它通常并不指明哪些物体落在同一类中,也不说明超出既定界限之外还会出现多少次重复。若要得到更强的结论,就需要关于物体分布或结构的额外信息。
历史术语
这一原理与十九世纪数学家狄利克雷密切相关,他曾将其用于数论。“狄利克雷抽屉原理”和“抽屉原理”这两个名称,与英语中的“鸽巢原理”(pigeonhole principle)一样,强调的都是同一种分配论证。
较简短的名称“狄利克雷原理”存在歧义:它也指另一个涉及调和函数和边值问题的变分原理。使用“鸽巢原理”或“狄利克雷抽屉原理”可以避免这种歧义。