鸽巢原理及其加强形式

摘要: 鸽巢原理

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

鸽巢原理是组合数学中最古老的原理之一，也称为抽屉原理或Dirichlet原理。Dirichlet 在 1834 年提出了这一原理，但这不可能是他首先发现的。

鸽巢原理最简单的叙述是：“三只鸽子飞进两个巢，必有一个巢里有至少两只鸽子”。本文我们看一下鸽巢原理及其变种和推广。

鸽巢原理

定理（鸽巢原理）

设有 $m$ 只鸽子飞进 $n$ 个巢，则必定存在某个巢内飞进了至少 $\left\lceil\frac{m}{n}\right\rceil$ 只鸽子。

---

证明（反证法）：

若每个巢至多 $\left\lceil\frac{m}{n}\right\rceil - 1$ 只鸽子，则至多共有 $(\left\lceil\frac{m}{n}\right\rceil - 1)n < \frac{m}{n}n = m$ 只鸽子，矛盾。$\Box$

鸽巢原理的加强形式

定理（鸽巢原理加强形式）

设有 $m$ 只鸽子飞进编号分别为 $h_{1}, h_{2}, \cdots, h_{n}$ 的 $n$ 个巢，若已知：

$$m \geq a_{1} + a_{2} + \cdots + a_{n} - n + 1, \quad a_{i} \geq 0 (1 \leq i \leq n)$$

则必定存在某个巢 $h_{i}$ 中飞进了至少 $a_{i}$ 只鸽子。

---

证明（反证法）：若对任意 $1 \leq i \leq n$，巢 $h_{i}$ 内至多飞进 $a_{i} - 1$ 只鸽子，则鸽子数最多为：

$$\sum\limits_{i = 1}\limits^{n}(a_{i} - 1) = \sum\limits_{i=0}\limits^{n}a_{i} - n < \sum\limits_{i=0}\limits^{n}a_{i} - n + 1 \leq m$$

矛盾。$\Box$

集合与映射的等价描述

将鸽子抽象化，鸽巢原理及其加强形式可以用集合与映射的语言等价地描述。

定理（鸽巢原理）

设 $A, B$ 是两个非空有限集，$f: A\rightarrow B$ 为一个映射，则：

(1) $\exists b_{1}\in B$，使得 $|f^{-1}(b_{1})| \geq \left\lceil\frac{|A|}{|B|}\right\rceil$

(2) $\exists b_{2}\in B$，使得 $|f^{-1}(b_{2})| \leq \left\lfloor\frac{|A|}{|B|}\right\rfloor$

---

定理（鸽巢原理加强形式）

设 $A$ 是一个非空有限集，$B = \{b_{1}, b_{2}, \cdots, b_{n}\}$，$f: A\rightarrow B$ 为一个映射，若 $|A| = \sum\limits_{i=1}\limits^{n}x_{i} - n + 1$，则：

(1) $\exists b_{i}\in B$，使得 $|f^{-1}(b_{i})| \geq x_{i}$

(2) $\exists b_{i}\in B$，使得 $|f^{-1}(b_{i})| \leq x_{i}$

---

鸽巢原理在数论中的应用

mod

有 $n$ 个数 $\{a_{i}\}, i=1,2,\cdots,n$，$a_{i} \mod{m}$ 会得到 $0,1,\cdots, m$ 中的一个数。因此可以看做有 $m$ 个类。

于是由鸽巢原理，当 $n > m$ 时，一定 $\exists a_{i}, a_{j}$，使得 $a_{i} \equiv a_{i} \mod{m}$。

有理数

定理：一个有理数写成小数如果有无限位，则一定在某一位开始循环。

---

证明（构造）：

设有理数为 $\frac{n}{m}$，

考虑 $n/m$ 的竖式除法，其中每次运算的除数均为 $m$。

记第 $i$ 次运算的被除数为 $f_{i}$，商为 $g_{i}$，余数为 $r_{i}$，于是：

$$f_{i} = mg_{i} + r_{i} \\ r_{i} < m \\$$

按照带余除法的运算规则，第 $i$ 次运算的结果如下：

$$g_{i} = \left\lfloor f_{i} / m\right\rfloor \\ r_{i} = f_{i} \mod m \\$$

记 $n$ 在第 $i$ 位的数字为 $n_{i}$，$n = n_{1}n_{2}\cdots$，第 1 次运算时 $f_{1} = n_{1}$，第 $i+1$ 次运算的被除数为：

$$f_{i+1} = 10\cdot r_{i} + n_{i+1}$$

每次运算的商 $g_{i}$ 就是 $\frac{n}{m}$ 写为小数形式的第 $i$ 位，这样写出的 $\frac{n}{m}$ 的小数形式不包含小数点位置，并且有前导零，如下：

$$g_{1}g_{2}\cdots g_{i}\cdots$$

假设当运算 $I$ 次数后，$n$ 的各个位耗尽，也就是当 $i > I$ 时，$n_{i} = 0$，此后 $f_{i+1}$ 与 $r_{i}$ 的关系变为：

$$f_{i+1} = 10\cdot r_{i}$$

当 $j = I + m + 1$，第 $j$ 次运算刚好是 $i > I$ 之后的第 $m+1$ 次运算，由于 $r_{i}$ 只能取到 $0,1,\cdots,m-1$，由鸽巢原理，$r_{j}$ 肯定跟 $r_{I+1}, r_{I+2},\cdots, r_{I+m}$ 中的某一个相同，记为 $r_{k}$。也就是 $r_{j} = r_{k}$。

又由于 $i > I$ 时 $f_{i+1} = 10r_{i} = 10r_{k} = f_{k+1}$，因此第 $j+1$ 次除法运算与第 $k+1$ 次除法运算的被除数一样，商和余数自然也一样，这样就形成了一个循环。循环节为：

$$g_{k}g_{k+1}\cdots g_{I+m}$$

$\Box$

互质

定理：从 $1,2,\cdots,2n$ 中，选出 $n+1$ 个数，至少有一对是互质的。

---

证明(构造)：

已知 $i$ 和 $i+1$ 一定是互质的。所以将 $1$ 到 $2n$ 构造为 $[1,2], [2,3], \cdots, [2n-1, 2n]$ 共 $2n-1$ 类，除了 $1$ 和 $2n$，$1$ 到 $2n$每个数字都占了两类。

当从其中选出 $n+1$ 个数，则至少要占 $2 + 2(n-1) = 2n$ 个类。而总的类的个数只有 $2n-1$，由鸽巢原理，一定有某两个数属于同一类，这就意味着这两个数字满足 $i$ 和 $i+1$ 的关系，它们是互质的。$\Box$

---