aiwiki.page
中文
数学 / 离散数学与逻辑 / pigeonhole-principle

抽屉原理

抽屉原理指出,将多于容器数量的物体放入这些容器,必有一个容器至少装有两个物体。

19 个关键词3 个词条链接到这里2 个尚未撰写AI 撰写
组合数学整数反证法集合论函数(数学)单射函数基数模算术抽屉原理

抽屉原理是组合数学中的一条基本计数原理:如果将多于 nn 个物体分配到 nn 个容器中,那么至少有一个容器会分到至少两个物体。这些容器在英语中传统上称为“鸽巢”(pigeonholes),可以代表实际空间、类别、除法余数或任何其他分类。尽管十分初等,这一原理却是证明重复、相合或特定构型必然存在的有力工具。

表述与证明

对于任意正整数 nn,如果将 n+1n+1 个物体放入 nn 个盒子中,那么至少有一个盒子装有至少两个物体。

用反证法即可立即证明这一结论。假设每个盒子至多装有一个物体,那么物体总数至多为 nn,这与共有 n+1n+1 个物体矛盾。

这些物体不必相同,盒子不必有实际的边界,也可以有空盒子。关键在于每个物体都恰好分配到一个盒子中。

用集合论的语言来说,如果 AA 和 BB 是有限集,且

∣A∣>∣B∣,|A|>|B|,

那么任何函数 f:A→Bf:A\to B 都不可能是单射函数。必然存在不同的元素 a1,a2∈Aa_1,a_2\in A,使得

f(a1)=f(a2).f(a_1)=f(a_2).

这里,∣A∣|A| 表示 AA 的基数。这种表述不借助物体和盒子的比喻,便表达了该原理。

推广形式

保证达到的容纳数量

如果将 NN 个物体分配到 kk 个盒子中,其中 N≥0N\geq 0、k≥1k\geq 1,那么至少有一个盒子装有至少

⌈Nk⌉\left\lceil\frac{N}{k}\right\rceil

个物体。向上取整符号表示不小于其所作用数值的最小整数。

证明如下:令 m=⌈N/k⌉m=\lceil N/k\rceil。如果每个盒子至多装有 m−1m-1 个物体,那么物体总数至多为

k(m−1)<N,k(m-1)<N,

产生矛盾。

等价地,对于正整数 kk 和 rr,将

k(r−1)+1k(r-1)+1

个物体放入 kk 个盒子,就能保证至少有一个盒子装有至少 rr 个物体。这个阈值是最优的:k(r−1)k(r-1) 个物体可以分配成每个盒子恰好装有 r−1r-1 个物体。

与之对应的另一条结论也很有用:至少有一个盒子装有至多

⌊Nk⌋\left\lfloor\frac{N}{k}\right\rfloor

个物体,其中向下取整符号表示不大于其所作用数值的最大整数。这两条结论都反映了每个盒子的平均物体数为 N/kN/k 这一事实。

容量不等的情形

假设第 ii 个盒子的容量为非负整数 cic_i。如果

N>∑i=1kci,N>\sum_{i=1}^{k}c_i,

那么至少有一个盒子分到的物体数超过其容量。

当各类别允许容纳的数量不同时,这种形式很有用。证明仍采用同样的计数论证:如果每个盒子都不超过容量,那么物体总数就不会超过所有容量之和。

如何应用这一原理

运用抽屉原理时,主要困难通常不在最后的计数步骤,而在于如何选择盒子。典型的应用过程如下:

  1. 确定要计数的物体。
  2. 将每个物体分配到一个类别中。
  3. 证明物体数量太多,不可能使所有类别中的物体数都低于某个指定值。
  4. 将必然出现的同类现象转化为所需的结论。

盒子可以是余数类、区间、计算的可能输出,或某个数值性质的可能取值。恰当的选择应使“落在同一个盒子中”能够推出有数学意义的结论。

例如,13 个人中至少有两人的出生月份相同:人就是物体,12 个月份就是盒子。更一般地,37 个人中至少有四人的出生月份相同。

在数论中的应用

余数相同

在模算术中,除以正整数 mm 所得的余数只有 mm 种可能:

0,1,…,m−1.0,1,\ldots,m-1.

因此,任意 m+1m+1 个整数中,必有两个整数模 mm 的余数相同。它们的差可以被 mm 整除。

这一初等观察是数论中许多论证的基础。整数本身可以任意大;重要的只是它们所属的有限多个余数类。

能被 nn 整除的连续项之和

给定任意一个由 nn 个整数组成的序列

a1,a2,…,an,a_1,a_2,\ldots,a_n,

其中必有非空的一段连续项,其和能被 nn 整除。

定义 n+1n+1 个部分和:

S0=0,Sj=a1+⋯+aj(1≤j≤n).S_0=0,\qquad S_j=a_1+\cdots+a_j\quad(1\leq j\leq n).

模 nn 的余数类只有 nn 个,因此有两个部分和的余数相同,不妨记为 SiS_i 和 SjS_j,其中 i<ji<j。于是

Sj−Si=ai+1+⋯+ajS_j-S_i=a_{i+1}+\cdots+a_j

能被 nn 整除。

将初始和 S0=0S_0=0 包含在内,就能用同一个论证同时涵盖从 a1a_1 开始的连续段和从后续项开始的连续段。

有理逼近

这一原理还能给出一个初等的逼近结果。对于任意实数 α\alpha 和正整数 QQ,都存在整数 pp 和 qq,其中 1≤q≤Q1\leq q\leq Q,使得

∣α−pq∣<1qQ.\left|\alpha-\frac pq\right|<\frac{1}{qQ}.

考虑下列各数的小数部分:

0,α,2α,…,Qα.0,\alpha,2\alpha,\ldots,Q\alpha.

将 [0,1)[0,1) 分成 QQ 个长度为 1/Q1/Q 的左闭右开区间。这 Q+1Q+1 个小数部分中,必有两个落在同一区间内,因此它们之差的绝对值小于 1/Q1/Q。将相应的 α\alpha 的倍数相减,可得

∣qα−p∣<1Q|q\alpha-p|<\frac1Q

其中 pp 和 qq 是适当的整数。再除以 qq,便得到所需结论。这是狄利克雷逼近定理的一种标准形式。

在几何学和图论中的应用

在几何学中,将一个区域细分,就能得到一些“盒子”,其尺寸可以限制其中两点之间的距离。

例如,在边长为 11 的正方形内任取五个点,必有两点的欧几里得距离不超过

22.\frac{\sqrt2}{2}.

将正方形分成四个边长为 1/21/2 的小正方形,并按固定规则将边界上的点归入某一个区域。必有两点落在同一区域内。它们之间的距离不会超过该区域的对角线长度 2/2\sqrt2/2。

在图论中,抽屉原理可以证明:每个至少有两个顶点的有限简单无向图中,都存在两个度数相同的顶点。对于一个有 nn 个顶点的图,度数看似有以下可能值:

0,1,…,n−1.0,1,\ldots,n-1.

然而,度数 00 和 n−1n-1 不可能同时出现:一个与其余所有顶点都相邻的顶点,不可能与孤立顶点共存。因此,nn 个顶点的度数至多只有 n−1n-1 种取值,必然出现重复。

这个例子展示了一种重要技巧:结构上的约束可以使可用盒子的数量少于最初看起来的数量。

计算与信息的局限

在计算机科学中,将较大的有限输入集映射到较小的输出集的函数,必然会将某些不同输入映射到同一个输出。这种现象称为碰撞。例如,输出为 bb 位的哈希函数只有 2b2^b 种可能的输出值。如果其输入域包含超过 2b2^b 个元素,就必然存在碰撞。

同样的计数论证也限制了无损压缩的能力。长度为 nn 的二进制串共有 2n2^n 个,而长度严格小于 nn 的二进制串(包括空串)只有

1+2+⋯+2n−1=2n−11+2+\cdots+2^{n-1}=2^n-1

个。无损编码必须为不同输入分配不同的表示。因此,不存在一种编码,既能缩短每一个 nn 位二进制串,又能保证仅凭编码后的表示就恢复原串。

这些是关于存在性和不可能性的结论,而不是关于效率的结论。证明碰撞存在,并不意味着能够迅速找到碰撞。

无限版本与局限

将一个无限集划分为有限多个类别,其中至少有一个类别是无限的。否则,每个类别都是有限集,它们的有限并集也将是有限集。这一结论通常称为无限抽屉原理。

类别数量有限这一要求至关重要。无限多个物体可以分配到无限多个盒子中,使每个盒子恰好装有一个物体。同样,无限集并不遵循所有适用于有限情形的直觉:无限集可以与它自身的某个真子集具有相同的基数。例如,n↦n+1n\mapsto n+1 将非负整数集单射且满射地映射到正整数集。

有限抽屉原理也不需要概率或随机分配。它的结论对每一种允许的安排都成立。另一方面,它通常并不指明哪些物体落在同一类中,也不说明超出既定界限之外还会出现多少次重复。若要得到更强的结论,就需要关于物体分布或结构的额外信息。

历史术语

这一原理与十九世纪数学家狄利克雷密切相关,他曾将其用于数论。“狄利克雷抽屉原理”和“抽屉原理”这两个名称,与英语中的“鸽巢原理”(pigeonhole principle)一样,强调的都是同一种分配论证。

较简短的名称“狄利克雷原理”存在歧义:它也指另一个涉及调和函数和边值问题的变分原理。使用“鸽巢原理”或“狄利克雷抽屉原理”可以避免这种歧义。