17 世纪末的伦敦，城中颇受欢迎《雅典信使报》刊登过这样一个看似荒诞的问题：世界上是否存在头发根数完全相同的两个人？
对此，当时的编辑给出的答复是：“问题没法给出答案，因为既无法通过实验验证，也无法通过逻辑论证。”
他们不知道，实际上用数学立即就能给出肯定的答案。
人类头皮上的毛囊数量，学界公认普遍落在 9 万至 15 万之间，即便是发量非常浓密也极难突破 100 万根。我们可以把发丝数量从 （光头）到 的每一个整数，都当作一个独立的分类标签——这样一共构成了 个彼此隔离的"抽屉"。
当人群被按其发量依序贴上标签时，前 100 万人或许还能侥幸占据互不重复的数值。但只要登记人数迈入第 1000001 位的瞬间，答案已出：第 1000001 个人必然会跌落进某个已被占据的数字之中。
这种无需追踪细节、仅凭总量与容量的边界冲突就能确立必然性的论证方式，在数学上被称为计数论证（Counting Argument）。它的核心基石，正是离散数学中基础定理之一——鸽巢原理（Pigeonhole Principle）。
鸽巢原理的经典表述十分直观：若将 个物件放入 个容器中，且 ，则至少有一个容器容纳了多于一个物件。
实际上早在 1622 年，法国耶稣会士让·勒雷雄就在其著作中记录下了这一思维的萌芽，但直到 1834 年，德国数学家彼得·古斯塔夫·勒热纳·狄利克雷在研究丢番图逼近问题时，对该原理作出了更系统的表述，并将其命名为抽屉原理（Schubfachprinzip）。
基础的鸽巢原理只断言了至少存在两个元素放到了一个容器里。当待分配的对象数量远超容器容量时，这一原理还可以进一步延伸。
设定自然数 与 。若将 个对象分配进 个集合中，鸽巢原理可以给出更强的结论：至少有一个集合内部容纳的对象数量不低于 。
直接看一个小例子，把 7 个物品放进 3 个抽屉（这里 ，物品 ， ），就可以直接断言：必定至少有一个抽屉装了不少于 件物品。
我们可以逐步验证这个结论：即便前 6 件物品被绝对平均地分配（每个抽屉恰好分到 2 件），剩下的第 7 件物品，无论落入哪一个抽屉，都会打破平衡，让该抽屉的物品数达到 3 件。
对于任意给定的正整数 与 ，这一关系可以推广为一般形式：在所有集合中，装有最多对象的那个集合，其包含的对象数量下限为
上面 是下取整函数，代表取小于或等于 的最大整数； 是上取整函数，代表取大于或等于 的最小整数。
有个这个工具，回头再看头发的问题，比如当代伦敦市人口规模约 900.2 万（ ）与 100 万个发量可能值（ ）代入公式，便得出了比“至少两人相同”更强的定量结论：
这一推导表明：在整座伦敦城中，必然至少有 10 个人的头发生长着完全相同的根数。道理很直接——若每个抽屉都只容纳 9 人，全部 100 万个抽屉合起来也只能安置 900 万人；余下的 2000 人无论如何分配，都必将强行推高某些抽屉的承载量。
应用三则
在实际问题中，鸽巢原理最擅长快速确定各种边界条件——即"最少需要做多少次，才能确保必然发生某种结果"。
1. 摸袜子问题
假设一个袋子里混放着大量黑色和蓝色的袜子，且袜子不分左右脚。闭着眼睛去摸，最少要拿几只，才能确保凑出一双同色的袜子？
答案是3 只。
这里，两种颜色就是两个抽屉（ ）。根据鸽巢原理，只要摸取的袜子数量大于颜色种类（ ），就必然会有至少两只袜子落进同一个颜色分类里。
2. 握手问题与图论度数
在由 个人（ ）参加的聚会中，大家自由相互握手。是否存在一种可能，让场内每个人的握手次数都互不相同？
答案是不可能。
每个人握手的对象数量，只能是 到 之间的某个整数，表面上看刚好有 种可能的握手次数。
但这里存在一个关键的逻辑互斥："握手 0 次"（没和任何人握手）与"握手 次"（和其余所有人都握过手），绝不可能同时出现——如果有人握了 次手，全场每个人就都至少握过 1 次，不可能再有人是 0 次；反过来，如果有人握了 0 次手，其他人最多只能和剩下的 个人握手，也绝不可能有人达到 次。
这意味着，无论现场情况如何，实际可用的握手次数最多只有 种（即至多 个抽屉）。把 个人分配进至多 种握手次数中，根据鸽巢原理：聚会中必然至少有两个人，他们的握手次数完全相同。
在图论中，这一结论对应一条基础定理：在任何顶点数大于 1 的简单图中，必定存在至少两个度数（Degree）相同的顶点。
3. 子集和问题
给定包含 9 个数字的集合 。如果任意挑出 6 个不同的数字，能否断定其中必定存在两个数字，它们的和正好等于 10？
答案是必然存在。
我们不需要把所有可能的抽取情况（共 种组合）逐一列举，只需把这 9 个数字归入 5 个抽屉：4 个"相加等于 10"的配对抽屉—— 、 、 、 ；再加 1 个单元素抽屉 。
现在，把挑出的 6 个数字，分别放进各自所属的抽屉。因为挑选了 6 个数字，而抽屉只有 5 个（ ），根据鸽巢原理：必定至少有一个配对抽屉里的两个数字被同时选中。而无论被同时选中的是哪一组配对，它们的和都必定等于 10。结论由此成立。
从概率到必然
鸽巢原理最迷人的地方，是它划出了"概率上可能"与"逻辑上必然"之间的分界线。我们熟悉的生日问题就是一个很好的例子。
从概率分布来看，只要一个房间里聚集 23 个人，出现同月同日生的概率就已经超过 50%。但这仍然只是"很可能"，而非必然。若要百分之百的绝对确定性，只要房间里聚集 367 人(对应闰年366天)，鸽巢原理就会给出必然重叠的结论数。
这一逻辑，也直接揭示了现代数据架构中哈希算法（Hashing）的核心局限。
哈希函数的作用，是把种类几乎无穷的原始数据——文件、密码、任意长度的字符串，统一压缩映射到一个固定长度的哈希值空间里（并存入哈希表以实现极速寻址）。这里，原始数据可能的种类数记为 ，固定位宽（例如 256 位）的哈希值一共有 种取值。现实中所有可能出现的文件与数据串的数量，在数学上远远超过这个有限的 ，即 。
把远多于 的数据塞进容量只有 的哈希值空间，根据鸽巢原理：世界上不存在任何一种能够完全避免重复的无损哈希算法——必然存在两个完全不同的原始文件，计算出完全相同的哈希值。这种现象被称为哈希碰撞（Hash Collision）。
因此，现代密码学与计算机工程从不试图消灭碰撞——数学规律已经决定了这不可能实现。算法工程师真正能做的，是通过算法设计，把找到一次碰撞所需要的计算难度，推向现实中难以企及的高度。
说到底，鸽巢原理讲的就是一件事：抽屉装不下了，重复就一定会发生。
不必知道细节，就能笃定地宣布答案。这种只证明存在、却不负责找出具体是谁的证明方式，在数学中被称为非构造性证明，它是纯数学思维里朴素也相当有用的一种工具。
参考资料：维基百科(Pigeonhole_principle)
原标题：《什么是鸽巢原理？从人类头发谜题到哈希碰撞，一文看懂强大的计数论证思维工具》
来源：遇见数学
编辑：杨樂多
转载内容仅代表作者观点
不代表中科院物理所立场
如需转载请联系原公众号
热门跟贴