鸽笼原理的简单美

luyuanhong

鸽笼原理的简单美

原创 围城里的猫 MathSpark 2025 年 03 月 03 日 17:31 陕西

一个基本理念如何带来巨大成果

数学里充满了有趣的问题。我特别喜欢那些提供数学问题的网站，它们会给你新的数学问题来解决。据我观察，现在组合数学很火，这些网站也紧跟潮流，出了不少组合数学的问题。组合数学只是计数的一个花哨的说法。它通常涉及确定某件事可以有多少种方式。以下是一个例子：

小美的抽屉里有无限多的袜子，颜色分别是红色、蓝色、黄色和绿色，并且这些袜子不分左右脚。小美需要从抽屉里拿出多少只袜子，才能保证她至少有一双同色的袜子？

你应该能够在不进行任何计算的情况下解决这个问题。答案是 5 只袜子。当小美从抽屉里取出 5 只袜子后，她必然会有一双同色的袜子。甚至在取出 5 只袜子之前，她就可能已经得到了一对相同颜色的袜子。但即使她抽出了 5 种不同颜色的袜子，也仍然可以保证至少有一对相同颜色的袜子。这个问题可以很容易地可视化。



我们创建了 4 个盒子，每个颜色对应一个盒子。如果碰巧遇到最坏的情况，前 4 只随机选出的袜子各自颜色不同，那么结果就是这样。



我们知道，接下来取出的这只袜子必须放入这四个盒子中的一个，而每个盒子里已经各有一只袜子。这意味着，第五只袜子必然会与其中一个盒子里的袜子颜色相同，从而形成一双配对的袜子。



这种创建一定数量的盒子并将物品放入这些盒子的方法被称为鸽笼原理（Pigeonhole Principle）。从实际角度来看，这是一个非常显而易见的事实：如果将个物品放入个容器中，并且，那么至少有一个容器中必然会包含多于一个物品。

这个原理的名字来源于过去用来存放邮件或留言的信格（pigeonhole）。这些格子状的存储结构曾经被广泛用于交流和传递信息，直到今天，在某些特定场合仍然能找到它们的身影。我记得我的大学里某些部门仍然保留着这样的信格。然而，随着时间的推移，“鸽笼原理”逐渐变成了一个更具象的概念，即把鸽子放入盒子，这一点让我觉得更有趣！



我们可以运用这个原理来推广袜子问题。在上面的例子中，我们有 4 种颜色，因此可以对应 4 个盒子。这等价于 m=4 。一旦我们开始取出 n=m+1 只袜子，我们就满足 n＞m ，因此至少有一个盒子里会包含两只袜子。这意味着，对于任何包含 m 种不同颜色袜子的抽屉，当你至少抽取 m+1 只袜子时，必然会有一双颜色相同的袜子。

鸽笼原理最早由业余数学家 Jean Leurechon 在 1624 年的一本著作中提出。随后，在 1834 年，数学家 Peter Dirichlet 对其进行了更正式的定义。Dirichlet 是一位极富创造力的数学家，定期发表关于数论和傅里叶变换的研究成果，并且他的名字还出现在狄利克雷函数（Dirichlet Function）中。然而，他很可能并未通过 Leurechon 了解到鸽笼原理，而是独立得出了这一结论。



袜子问题的例子对你来说可能显而易见。甚至鸽笼原理（Pigeonhole Principle） 本身看起来也是一个非常基础的概念。那么，为什么数学家们如此重视这个看似微不足道的原理呢？

简单的答案是，鸽笼原理常常可以将非常困难的问题变得直截了当。 关键在于如何定义“盒子”，以及如何定义“鸽子”。许多巧妙运用鸽笼原理的问题在最初看起来与组合数学（combinatorics）毫无关系，直到你换个角度重新审视它们。例如，考虑下面这个问题：

设有一个边长为 n 的正方形，证明如果在该正方形内随机放置 5 个点，那么至少存在一对点，它们之间的距离最多为 n/√2 单位。

如果不借助鸽笼原理，这个问题可能会显得相当困难。让我们试着将其可视化。



在继续之前，看看你是否能自己想出答案！记住要使用鸽笼原理（Pigeonhole Principle），并仔细思考如何定义“盒子”和“鸽子”。

要解决这个看似困难的问题，你只需要巧妙地定义“盒子”。首先，将这个正方形划分为四个大小相等的小正方形。



现在，将每个小正方形定义为“盒子”，并将这些点定义为“鸽子”。由于鸽子的数量多于盒子的数量，根据鸽笼原理（Pigeonhole Principle），至少有一个盒子必须包含两个点。

在这个盒子内，两点之间的最大距离等于该小正方形的对角线长度。



利用勾股定理（Pythagorean Theorem），我们可以得出，在一个小正方形内，任意两点之间的最大距离为 n/√2 。由于至少有一个小正方形内包含两个点，因此这两个点之间的距离最多为这个值。

我们可以轻松地使用鸽笼原理（Pigeonhole Principle） 证明这个结论！这种巧妙的技巧在各种证明中频繁出现，尤其是在组合数学（combinatorics） 中。

接下来，让我们来看另一个利用鸽笼原理 变得微不足道的有趣问题。

给定任意正整数，证明在前 x^2 个斐波那契数（Fibonacci Numbers）中，至少有一个斐波那契数能够被 x 整除。

我不会详细展开这个证明，但实际上，利用鸽笼原理可以轻松解决这个问题。

总体而言，鸽笼原理是一个极其灵活的数学工具，能够应用于各种数学问题。欢迎在评论区分享你最喜欢的鸽笼原理应用！



围城里的猫