The Pigeonhole Principle and Its Applications | 鸽巢原理及其应用

📚 The Pigeonhole Principle and Its Applications | 鸽巢原理及其应用

The Pigeonhole Principle, also known as Dirichlet’s Box Principle, is one of the most intuitive yet powerful tools in combinatorics and discrete mathematics. It states that if more objects are placed into fewer containers, then at least one container must contain more than one object. Despite its simplicity, this principle yields elegant solutions to a wide range of mathematical problems, from number theory to geometry.

鸽巢原理，又称狄利克雷抽屉原理，是组合数学与离散数学中最直观却最有力的工具之一。它指出：如果将多于容器数量的物体放入容器中，则至少有一个容器包含不止一个物体。尽管这个原理看似简单，它却能优雅地解决从数论到几何的各类数学问题。

1. The Basic Statement | 基本原理

The simplest form of the Pigeonhole Principle can be stated as follows: If \(n+1\) or more objects are placed into \(n\) boxes, then there exists at least one box containing at least two objects. For example, if 6 pigeons fly into 5 pigeonholes, one hole must house at least 2 pigeons.

鸽巢原理的最简形式可以表述为：如果将 \(n+1\) 个或更多物体放入 \(n\) 个盒子中，则至少有一个盒子含有至少两个物体。例如，如果6只鸽子飞入5个鸽巢，则至少有一个鸽巢中至少有2只鸽子。

If n + 1 objects are distributed among n boxes, at least one box contains ≥ 2 objects.

若将 n + 1 个物体放入 n 个盒子，则至少有一个盒子含有 ≥ 2 个物体。

This principle relies on the fundamental idea of counting: when the number of items exceeds the number of categories, repetition is unavoidable.

该原理基于计数这一基本思想：当物品数量超过类别数量时，重复是不可避免的。

2. The Generalized Pigeonhole Principle | 推广的鸽巢原理

A more powerful version states that if \(N\) objects are placed into \(k\) boxes, then at least one box contains at least \(\lceil N/k \rceil\) objects, where \(\lceil x \rceil\) is the ceiling function. For instance, placing 100 objects into 7 boxes guarantees one box with at least \(\lceil 100/7 \rceil = 15\) objects.

一个更强版本的原理指出：如果将 \(N\) 个物体放入 \(k\) 个盒子中，则至少有一个盒子包含至少 \(\lceil N/k \rceil\) 个物体，其中 \(\lceil x \rceil\) 为向上取整函数。例如，将100个物体放入7个盒子，则必然有一个盒子中至少有 \(\lceil 100/7 \rceil = 15\) 个物体。

If N objects are placed into k boxes, at least one box contains ≥ ⌈N/k⌉ objects.

若将 N 个物体放入 k 个盒子，则至少有一个盒子含有 ≥ ⌈N/k⌉ 个物体。

The proof is straightforward: if every box contained at most \(\lceil N/k \rceil – 1\) objects, the total would be at most \(k(\lceil N/k \rceil – 1) < N\), contradicting the assumption.

证明十分直接：如果每个盒子至多含有 \(\lceil N/k \rceil – 1\) 个物体，则总数至多为 \(k(\lceil N/k \rceil – 1) < N\)，与假设矛盾。

3. Application: Pigeonholes Among People | 应用：人群中的鸽巢

Problem. Show that among any 13 people, at least two share a birth month.

问题。证明在任意13个人中，至少有两个人的出生月份相同。

Solution. There are 12 months (pigeonholes) and 13 people (pigeons). By the basic principle, at least one month contains at least \(\lceil 13/12 \rceil = 2\) people.

解。一共有12个月份（鸽巢）和13个人（鸽子）。根据基本原理，至少有一个月份至少包含 \(\lceil 13/12 \rceil = 2\) 个人。

Problem. How many people must be gathered to guarantee that at least 4 share the same birthday month?

问题。至少需要聚集多少人才能保证至少有4个人出生在同一月份？

Solution. By the generalized principle, we need \(\lceil N/12 \rceil = 4\), so the smallest \(N\) is \(3 \times 12 + 1 = 37\).

解。根据推广原理，我们需要 \(\lceil N/12 \rceil = 4\)，因此最小的 \(N\) 为 \(3 \times 12 + 1 = 37\)。

4. Application: Divisibility and Remainders | 应用：整除与余数

Problem. Show that among any \(n+1\) integers, there exist two whose difference is divisible by \(n\).

问题。证明在任意 \(n+1\) 个整数中，存在两个整数，它们的差能被 \(n\) 整除。

Solution. When an integer is divided by \(n\), the possible remainders are \(0, 1, 2, \ldots, n-1\) — exactly \(n\) categories. With \(n+1\) integers, at least two share the same remainder. Their difference is then a multiple of \(n\).

解。当一个整数除以 \(n\) 时，可能的余数为 \(0, 1, 2, \ldots, n-1\)，恰好有 \(n\) 类。在 \(n+1\) 个整数中，至少有两个的余数相同。它们的差即为 \(n\) 的倍数。

Problem. Prove that there exists a power of 2 whose decimal representation ends in at least 100 zeros when multiplied by some integer.

问题。证明存在某个 2 的幂次，当乘以某个整数后，其十进制表示以至少100个零结尾。

Solution sketch. Consider the \(101\) numbers \(2^0, 2^1, \ldots, 2^{100}\). Look at their remainders modulo \(5^{100}\). There are only \(5^{100}\) possible remainders, but we have \(101\) numbers—wait, this does not directly apply. A better approach: consider the \(101\) remainders of \(2^i\) modulo \(5^{100}\); since there are \(101\) numbers and \(5^{100}\) is far larger, the pigeonhole principle as stated does not immediately work. Instead, we use the fact that among \(5^{100} + 1\) powers, two are congruent modulo \(5^{100}\).

证明思路。考虑 \(101\) 个数 \(2^0, 2^1, \ldots, 2^{100}\)，考察它们模 \(5^{100}\) 的余数。可能的余数只有 \(5^{100}\) 个，但只有 \(101\) 个数——这并不能直接应用。更好的方法是：在 \(5^{100} + 1\) 个幂中，必有两个模 \(5^{100}\) 同余。

5. Application: Geometry and Distances | 应用：几何与距离

Problem. Prove that among any 5 points placed inside an equilateral triangle of side length 1, there exist two points whose distance is at most \(1/2\).

问题。证明在边长为1的等边三角形内任意放置5个点，必有两个点之间的距离至多为 \(1/2\)。

Solution. Divide the triangle into 4 smaller equilateral triangles of side length \(1/2\) by joining the midpoints of the sides. These 4 small triangles are our pigeonholes. With 5 points, by the pigeonhole principle, at least two points lie in the same small triangle. The maximum distance between any two points in a triangle of side \(1/2\) is \(1/2\) (the diameter). Hence, the two points are at most \(1/2\) apart.

解。连接三角形三边中点，将原三角形分成4个边长为 \(1/2\) 的小等边三角形。这4个小三角形就是鸽巢。由于有5个点，根据鸽巢原理，至少有两个点落在同一个小三角形内。边长为 \(1/2\) 的三角形内任意两点间的最大距离为 \(1/2\)（即直径）。因此，这两点之间的距离至多为 \(1/2\)。

6. Application: Subset Sums | 应用：子集和

Problem. Show that among any 10 distinct integers between 1 and 100, there exist two disjoint subsets with the same sum.

问题。证明在1到100之间的任意10个不同整数中，存在两个不相交的子集，它们的和相等。

Solution. A 10-element set has \(2^{10} = 1024\) subsets. The sum of any subset is at most \(91 + 92 + \cdots + 100 = 955\) (if we choose the 10 largest) and at least 0. More generally, the maximum sum of any subset is \(10 \times 100 = 1000\), so the possible sums range from 0 to 1000, a total of 1001 possibilities. Since \(1024 > 1001\), two subsets have the same sum. Removing the common elements from both subsets yields two disjoint subsets with equal sums.

解。一个含10个元素的集合共有 \(2^{10} = 1024\) 个子集。任意子集的和至多为 \(91 + 92 + \cdots + 100 = 955\)（若选最大的10个），至少为0。更一般地，任意子集的最大和为 \(10 \times 100 = 1000\)，因此可能的和在0到1000之间，共1001种。由于 \(1024 > 1001\)，必有两个子集的和相等。从这两个子集中去掉共同元素，便得到两个和相等的不相交子集。

7. Application: Sequences and Monotonicity | 应用：数列与单调性

Problem. Prove that any sequence of \(n^2 + 1\) distinct real numbers contains either an increasing subsequence of length \(n+1\) or a decreasing subsequence of length \(n+1\).

问题。证明任意由 \(n^2 + 1\) 个不同实数组成的数列中，必然包含一个长度为 \(n+1\) 的递增子序列或长度为 \(n+1\) 的递减子序列。

Solution. For each term \(a_i\), define \((u_i, d_i)\), where \(u_i\) is the length of the longest increasing subsequence ending at \(a_i\), and \(d_i\) is the length of the longest decreasing subsequence ending at \(a_i\). If no increasing or decreasing subsequence of length \(n+1\) exists, then \(1 \le u_i \le n\) and \(1 \le d_i \le n\), so there are at most \(n^2\) possible pairs. Since there are \(n^2+1\) terms, two terms \(a_i\) and \(a_j\) (with \(i < j\)) have the same pair \((u, d)\). However, if \(a_i < a_j\), then \(u_j \ge u_i + 1\), a contradiction; if \(a_i > a_j\), then \(d_j \ge d_i + 1\), also a contradiction. Thus such a subsequence must exist.

解。对于每一项 \(a_i\)，定义 \((u_i, d_i)\)，其中 \(u_i\) 是以 \(a_i\) 结尾的最长递增子序列长度，\(d_i\) 是以 \(a_i\) 结尾的最长递减子序列长度。如果不存在长度为 \(n+1\) 的递增或递减子序列，则 \(1 \le u_i \le n\) 且 \(1 \le d_i \le n\)，因此可能的数对至多有 \(n^2\) 种。由于共有 \(n^2+1\) 项，必有两项 \(a_i\) 和 \(a_j\)（\(i < j\)）具有相同的数对 \((u, d)\)。然而，若 \(a_i < a_j\)，则 \(u_j \ge u_i + 1\)，矛盾；若 \(a_i > a_j\)，则 \(d_j \ge d_i + 1\)，同样矛盾。因此这样的子序列必然存在。

8. The Erdős–Szekeres Theorem | 埃尔德什–塞凯赖什定理

The result above is a special case of the Erdős–Szekeres theorem, a cornerstone of combinatorial geometry. One well-known consequence states that among any \( (r-1)(s-1) + 1 \) distinct real numbers, there exists an increasing subsequence of length \(r\) or a decreasing subsequence of length \(s\).

上述结果是组合几何中一座基石——埃尔德什–塞凯赖什定理的特例。该定理的一个著名推论指出：在任意 \((r-1)(s-1) + 1\) 个不同实数中，必然存在长度为 \(r\) 的递增子序列或长度为 \(s\) 的递减子序列。

This theorem elegantly demonstrates how the pigeonhole principle can be used to prove nontrivial results in combinatorics.

该定理优雅地展示了鸽巢原理如何用于证明组合学中的深刻结论。

9. Common Exam Pitfalls | 常见考试误区

Misidentifying pigeonholes. Students often confuse which set serves as pigeons and which as pigeonholes. Always ask: what are we forced to repeat?
错误识别鸽巢。学生常常混淆哪一个是鸽子、哪一个是鸽巢。始终要问：什么必然重复？
Ignoring the ceiling function. In the generalized form, forgetting to round up leads to incorrect minimum bounds.
忽略向上取整。在推广形式中，忘记向上取整会导致最小值计算错误。
Applying to non-integer contexts carelessly. Ensure that all objects fall into well-defined categories.
不加区分地应用于非整数情境。确保所有对象能落入明确定义的类别中。
Not justifying the maximum distance in geometry. When using geometric pigeonhole arguments, clearly state the diameter of each small region.
在几何问题中不说明最大距离。使用几何鸽巢论证时，需明确说明每个小区域的直径。

10. Extended Example: AIME-Level Problem | 进阶例题：竞赛级别问题

Problem. A student selects 11 distinct integers from the set \(\{1, 2, \ldots, 20\}\). Prove that among the selected numbers, one divides another.

问题。学生从集合 \(\{1, 2, \ldots, 20\}\) 中选取11个不同的整数。证明在这些选出的数中，必有一个数能整除另一个数。

Solution. Partition the set \(\{1, 2, \ldots, 20\}\) into 10 chains by odd factors:

解。将集合 \(\{1, 2, \ldots, 20\}\) 按奇数因子分成10条链：

Chain 1	{1, 2, 4, 8, 16}
Chain 2	{3, 6, 12}
Chain 3	{5, 10, 20}
Chain 4	{7, 14}
Chain 5	{9, 18}
Chain 6	{11}
Chain 7	{13}
Chain 8	{15}
Chain 9	{17}
Chain 10	{19}

Each chain consists of numbers where each term divides the next. There are 10 chains (pigeonholes) and 11 selected numbers (pigeons). By the pigeonhole principle, two selected numbers belong to the same chain, and within a chain one divides the other.

每条链中的数都有相邻整除关系，即链中每一项整除其后一项。共有10条链（鸽巢），而选出了11个数（鸽子）。根据鸽巢原理，必有两个选出的数属于同一条链，而在同一条链中，其中一个数整除另一个数。

11. Summary of Key Formulas | 关键公式总结

Principle	Statement
Basic Form	\(n+1\) objects in \(n\) boxes ⇒ at least 2 in one box
Generalized Form	\(N\) objects in \(k\) boxes ⇒ at least \(\lceil N/k \rceil\) in one box
Contrapositive	If each box holds at most \(m\), then \(N \le km\)

原理	表述
基本形式	\(n+1\) 个物体放入 \(n\) 个盒子 ⇒ 至少有一个盒子有2个物体
推广形式	\(N\) 个物体放入 \(k\) 个盒子 ⇒ 至少有一个盒子有 \(\lceil N/k \rceil\) 个物体
逆否形式	若每个盒子至多有 \(m\) 个物体，则 \(N \le km\)

12. Practice Problems | 练习与自测

Show that among any 50 people, at least 5 were born in the same month.
证明：在任意50个人中，至少有5个人出生在同一月份。
Prove that in any set of 7 integers, there are two whose difference is divisible by 6.
证明：在任意7个整数中，存在两个整数，它们的差能被6整除。
How many cards must be drawn from a standard 52-card deck to guarantee at least 3 of the same suit?
从一副标准52张扑克牌中至少抽取多少张，才能保证至少有3张同花色？
Show that among 6 points in a \(3 \times 4\) rectangle, two points are within distance \(\sqrt{5}\).
证明：在 \(3 \times 4\) 的矩形内任意放置6个点，必有两个点之间的距离不超过 \(\sqrt{5}\)。

Answers: (1) \(\lceil 50/12 \rceil = 5\). (2) 6 possible remainders. (3) 9 cards: \(3 \times 4 + 1 = 9\). (4) Divide the rectangle into 5 rectangles of size \(1 \times 2\) or similar; the diagonal of each is at most \(\sqrt{5}\).

答案：(1) \(\lceil 50/12 \rceil = 5\)。(2) 余数只有6种。(3) 9张：\(3 \times 4 + 1 = 9\)。(4) 将矩形分成5个小矩形；每个小矩形的对角线至多为 \(\sqrt{5}\)。

Published by TutorHao | Mathematics Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

The Pigeonhole Principle and Its Applications | 鸽巢原理及其应用