鸽巢原理及其加强形式

  |  

摘要: 鸽巢原理

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:潮汐朝夕
我的知乎:潮汐朝夕
我的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$ 个巢,若已知:

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


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

矛盾。$\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}$,于是:

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

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

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

假设当运算 $I$ 次数后,$n$ 的各个位耗尽,也就是当 $i > I$ 时,$n_{i} = 0$,此后 $f_{i+1}$ 与 $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$ 次除法运算的被除数一样,商和余数自然也一样,这样就形成了一个循环。循环节为:

$\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$


Share