抽屉原理/鸽巢原理

Pigeonhole Principle

本文介绍抽屉原理（也叫鸽巢原理，Pigeonhole Principle）。

在之前的内容里，我们不少用到了抽屉原理的思想。

例如在融合待定数组里，我们知道因为有 $n$ 个单元格里要填入 $n$ 种不同的数字，因为数字不能出现重复项，因此每一种数字都必须出现恰好一次；更进一步地，由于存在 $n$ 种数字要填入到 $n + 1$ 个单元格里，所以为了确保数字均能填入，有一种数字必须出现两次才能满足条件。

另外，数组的显隐性互补里我们也知道，由于两个数组互补，他们只能位于同一个区域下，所以规格的和一定是小于等于 9 的。所以不论哪一个超过 5，则必有另外一侧互补的数组的规格小于 5，因此数组实际做题中是不存在五数组及以上规格的情况的。

这种用法参考和借鉴了抽屉原理的主旨思想。本文将对这个思想进行细致的介绍。

基础定义

这个说法起源自狄利克雷（Dirichlet），就是提出那个狄利克雷函数的那个人。这个人是德国一名数学家，它最初将问题描述成这样：

若有 $n$ 个笼子和 $n + 1$ 只鸽子，如果所有的鸽子都会被关进鸽笼里的话，那么至少会有一个笼子里会有两只鸽子。

这似乎跟之前我们用到的技巧推理有所不同。别着急，这确实不完全一样。我们先解释它的基础用法。

这个例子里，它是显然的。因为鸽子要关进去，每一个笼子都分配最少一只鸽子，怎么着都会剩下一只鸽子尚未归入笼子里。所以它必须放入任何一个已经有一只鸽子的笼子里去，所以这便就有了这个结论。

比较奇怪的是，这个似乎跟我前面描述的融合待定数组的使用上来看，说法确实稍微比较相似，说它是抽屉原理都还能勉强说得过去；但是说数组没有五数组的原因也是抽屉原理就有点力不从心了。这里我们稍微把问题给转化下，你就可以明白这为什么也是了。

首先， $n + 1$ 只鸽子和 $n$ 个笼子是起始条件，我们需要进行放入操作，为了确保尽量少地安放鸽子，所以每一个笼子里的鸽子数量整体加起来应该是 $1 + 1 + 1 + \dots$ 这么多。这个数要确保等于 $n + 1$ ，而这个式子里已经存在了 $n$ 个 1，所以暂时我们模糊一些，用小于等于暂且表示一下：

1 + 1 + 1 + 1 + \dots \le n + 1

然后？然后你就可以清楚地明白，当你不等号左侧的元素数量满了之后，你不得不去调整里面的数值使得式子从不等号变为等号成立。这么一看，是不是这跟显隐性互补那个式子还挺像的？为了保证等式成立，你只能改变式子一边的元素使之不断增大。当到一定的平衡之后，就只能调里面的数值大小了（其中一个调大，另外的数必须变小才能维持这个等式相等性的平衡）。如果将式子侧重于这点来解释的话，那么数组那个说它也是抽屉原理你应该没啥问题了吧。

使用场景

问题 1：鸽巢原理推广

假设我们把前面的例子稍加改动。如有 $n$ 个笼子和 $kn + 1$ 只鸽子（其中 $k$ 是整数）。因为每一只鸽子都需要进笼，所以最次的分配方式是每一个笼子逐个让鸽子进去，一个一个地用完全部的笼子。用完之后继续让鸽子从第一个笼子开始，保证笼子内的鸽子数量尽量少地去分配。那么这样分配下来， $kn$ 只鸽子就刚好用完全部所有的笼子 $k$ 次。

于是，我们再多加一只鸽子进去，不论加在哪一个笼子，笼子里都会多一只鸽子。原本全部都是 $k$ 只，现在肯定就变成了 $k + 1$ 。所以，如果鸽子数量是 $kn + 1$ 的话，则必有至少一个笼子会有 $k + 1$ 只鸽子。

问题 2：发量问题

一个正常人的头发数量是 10 万根左右。倘若我们不让这个数过大（比如一个人有 100 万根头发什么的），那么，像是北京这样的城市里，由于人口数显然超过 100 万，所以必然能找得到两个人会有完全相同的发量。

问题 3：握手问题

如果有一个派对里有 $n$ 个人（假设 $n \ge 2$ ）。我们随意地让这些人进行两个人互相握手的操作。因为每一个人最终握手的次数都介于 $[0, n - 1]$ 这个区间内（就是说要么不握手，要么跟 1 个人握，要么 2 个人握手，这么一直下去，最多可以是跟其他所有 $n - 1$ 人都握过手）。但是，总的人数却有 $n$ 个，所以至少会有两个人，他们跟别人握手的人数数量是一样的。

问题 4：（计算机科学）哈希码碰撞问题

在计算机里，哈希码是一个用于象征一个数据的唯一标识码，它是一个由 32 个二进制数（0 或 1）构成的数。由于任意的数据都能映射为哈希码，所以样本容量是无限的。但由于他们最终都压缩到了一个哈希码能表示的范畴中，所以肯定存在有两份数据算出的哈希码是完全相同的。

这个现象在计算机里称为哈希码碰撞（Hash Collision），它是存在且无法消除的问题，虽然这个遇到的概率较小，但它确实存在。

问题 5：（数学）质数判别

在质数判别的时候，我们都知道需要穷举从 $2$ 到 $n - 1$ 之间的所有数字，并挨个尝试除法运算，看看是否余数是否都不为 0（不被整除）。但是实际上并不需要到 $n - 1$ 这么大，而是到 $\sqrt n$ 就行。这是为什么呢？

由于一个不是质数的数一定可以拆解为两个数的乘积，即

n=a \times b

则我们可以说 $a$ 和 $b$ 均为 $n$ 的因数。我们要试除，主要工作就是为了去找这样的因数是否存在。可两个数的乘积是一个定值 $n$ ，所以一旦有一个数增大，那么势必另外一个数就会减小，才能保证这两个数的乘积稳定为同一个数。

但是很显然，倘若我们验证了超过 $\sqrt n$ 的任意一个整数（假设它还真的是因数），那么势必另外一个因数就肯定比 $\sqrt n$ 要小。而比它要小的数已经被我们验证过了。所以，我们不需要验证超过 $\sqrt n$ 的任何整数。所以，试除操作只需要从 $2$ 到 $\left \lfloor \sqrt n \right \rfloor$ 即可。其中符号 $\left \lfloor x \right \rfloor$ 的意思是对 $x$ 进行向下取整，即不超过 $x$ 的所有数；如果 $\sqrt x$ 是整数则也需要验证一下。

问题 6：（量子力学）海森堡不确定性原理

是不是看到标题都觉得人没了？其实这也是从抽屉原理派生出来的一个体现。不过，这个是量子力学的领域。

海森堡发现位置 $\Delta x$ 和动量 $\Delta p$ 两个算符在矩阵表示下是不对易的。

这里补充个知识。在矩阵里，我们是有 $AB \ne BA$ 的，即矩阵不符合乘法交换律。“对易”指的是可以交换计算次序（易这个字在古代是有“交换”的意思的；所以这里的“对易”就是说互相交换的意思）。

而在量子力学里，先后出现了两种不同的表现形式。一个是波恩和海森堡使用表格记录数据的矩阵表达式子的形式（也是我们这里想说的形式），一个是微分方程表示的形式（薛定谔方程什么的）。这两种表现形式在之后被人证明在数学上是等价的，所以只是表现形式的不同罢了。不过这里就不扯了。

矩阵有不对易的这个说法。而对于不对易的算符，两者都不可同时精确测得物理量。满足这种不对易的算符除了位置和动量外，还有能量和时间、角动量和角度这些。

回到位置和动量。这两个算符满足这么一个关系：

\Delta x \cdot \Delta p \ge \frac{\hbar}2

其中的 $\hbar$ 是量子力学中的约化普朗克常数，而普朗克常数记作 $h$ ，而这个约化普朗克常数 $\hbar$ 等于 $\frac{h}{2\pi}$ 。总之就还是一个常量。

总之，两个数值的乘积不小于一个常数。当你精确测量位置 $\Delta x$ 时，由于我们可以看出，这个 $\Delta x$ 在书写上是类似数学、物理学里差量的写法，所以这个物理量被精确测量时相当于是说 $\Delta x \to 0$ （趋近于 0）。那么，由于它是大于等于的关系，所以 $\Delta p \to \infty$ 。这也就是说，当你精确测量其中一个量的时候，另一个量随之就会变为更为不确定（一个差量越小，另外一个只能越大才能满足此不等式）。

最后更新于2个月前