最后更新: 2025-01-22 08:54 ● 参与者查看: 17 次纠错分享参与项目词条搜索

鸽笼原理基本原理

定理 $5.1 n+1$ 只鸽子飞回 $n$ 个笼子，至少有一个鸽笼含有不少于 2 只的鸽子。
这个定理的证明是非常简单的，现抽去具体的＂鸽子＂，＂鸽笼＂等物理属性，从数学上看，就是把 $s$ 个元素分成 $t$ 个组，当不能均匀分放时，必有一个组的元素个数要超出＂平均数＂。形式地叙述为：

定理5．2 $s(s \geqslant 1)$ 个元素分成 $t$ 个组，那么必存在一个组至少含有 $\lceil s / t\rceil$（这里厂为＂上整数＂记号）个元素。

证明：用反证法证明。若每个组至多含有 $(\lceil s / t\rceil-1)$ 个元素，则 $t$ 个组共有元素 $t(\lceil s / t\rceil-1)$ ，因为 $s / t \leqslant\lceil s / t \ll(s / t)+1$ ，所以有 $t(\lceil s / t\rceil-1)<s$ ，这就导致矛盾。故必存在一个组至少含有 $\mid s / t\rceil$ 个元素。

一些简单结论列举如下。
任意 13 个人中，至少有二人生日在同一个月。
任意 50 个人中，至少有 $\lceil s / t\rceil\lceil 50 / 12\rceil=5$ 人生日同月。
例 5.1 设 $f$ 是从 $D$ 到 $R$ 的函数，这里 $|D|>|R|$ ，令 $i=\lceil|D| /|R|\rceil$ ，则 $D$ 中存在 $i$ 个元素 $d_1, d_2 \cdots$ ， $d_i$ ，使得 $f\left(d_1\right)=f\left(d_2\right)=\cdots=f\left(d_i\right)$ 。

证明：此问题相当于把 $|D|$ 个元素分到 $|R|$ 个组中去，因此由定理 5.2 得，在这 $|R|$ 个组中有一个组至少含有 $i=\lceil|D| /|R|\rceil$ 个元素。在同一个组中元素对应的函数值是相等的。所以在 $D$ 中至少存在 $i$ 个元素 $d_1, d_2 \cdots, d_i$ ，使得 $f\left(d_1\right)=f\left(d_2\right)=\cdots=f\left(d_i\right)$ 。

例5．2 在 $n+1$ 个小于或等于 $2 n$ 的互不相等的正整数中，必存在两个互质的数。
证明：把 $1,2, \cdots, 2 n$ 这 $2 n$ 个数分成 $n$ 个组：$\{1,2\},\{3,4\} \cdots,\{2 n-1,2 n\}$ 。则问题归结为从 $n$ 个组中任取 $n+1$ 个数，由定理 5.1 知，至少有 2 个数取自同一组，由于这两个数是相邻的正整数，故互质。

例 5.3 在 $1,2 \cdots, 2 n$ 中任取 $n+1$ 个互不相同的数中，必存在两个数，其中一个数是另一个数的倍数。

证明：因为任何正整数 $n$ 都可表示成 $n=2^a \cdot b$（这里 $a=0,1,2, \cdots$ ，且 $b$ 为奇数）。设取出的 $n+1$ 个数为 $k_1, k_2, \cdots, k_n+1$ ，则：$k_i=2^{a_i / b_i}$ 。

由于 $b_1, b_2 \cdots, b_{n+1}$ 是奇数，共有 $n+1$ 个，而在 $\{1,2, \cdots, 2 n\}$ 中只有 $n$ 个不同的奇数，所以必存在 $i, ~ j$ ，使得 $b_i=b_j$ 。

不妨设 $k_i>k_j$ ，则有 $k_i / k_j=2^{a_i-a_j}$ 为正整数，因此 $k_i$ 是 $k_j$ 的倍数。
例5．4（狄利克雷逼近定理）假设 $\alpha$ 是一个无理数，而 $K$ 是一个正整数，则必定存在一个有理数 $p / q(1 \leqslant q \leqslant K)$ ，满足

$$
\left|\alpha-\frac{p}{q}\right|<\frac{1}{q(K+1)} .
$$

证明：将实数区间 $[0,1]$ 均分为 $K+1$ 个子区间：

$$
\left[0, \frac{1}{K+1}\right),\left[\frac{1}{K+1}, \frac{2}{K+1}\right), \cdots,\left[\frac{K-1}{K+1}, \frac{K}{K+1}\right),\left[\frac{K}{K+1}, 1\right)
$$

现在考察下列 $K+2$ 个实数： $0, \alpha-\lfloor\alpha\rfloor, 2 \alpha-,\lfloor 2 \alpha\rfloor, \cdots, K \alpha-\lfloor K \alpha\rfloor, 1$ 。由于它们都位于区间 $[0,1]$ 之中，由定理 5.2 可知必有两个处于同一子区间，即存在

$$
|(i \alpha-\lfloor i \alpha\rfloor)-(j \alpha-\lfloor j \alpha\rfloor)|=|(i-j) \alpha-(\lfloor i \alpha\rfloor-\lfloor j \alpha\rfloor)|<\frac{1}{K+1}
$$

其中 $i \neq j$ ，不妨假设 $K \geqslant i>j \geqslant 0$ ，并且令 $q=i-j$ ，令 $p=\lfloor i \alpha\rfloor-\lfloor j \alpha\rfloor$ ，即得

$$
|q \alpha-p|<\frac{1}{K+1}
$$

将不等式两边同时除以 $q$ 便可得证。

例 5.5 一个国际象棋选手为参加国际比赛，突击练习 77 天，要求每天至少下一盘棋，每周至多下 12 盘棋。证明：无论如何安排，总可使他在这 77 天里有连续几天共下了 21 盘棋。

证明：用 $a_i$ 表示从第 1 天到第 $i$ 天下棋的总盘数 $(i=1,2, \cdots, 77)$ 。由于规定每天至少下一盘棋，且每周至多下 12 盘棋，故有

$$
1 \leqslant a_1<a_2<\cdots<a_{77}<12 \times(77 / 7)=132
$$

现构造一个新的序列

$$
a_1+21, a_2+21, \quad \cdots, a_{77}+21
$$

可得这样的序列

$$
a_1, \cdots, a_{77}, a_1+21, a_2+21, \cdots, a_{77}+21
$$

共有 154 个整数，但每个皆不超过 153 ，所以必存在 $i, ~ j(j<i)$ ，使得

$$
a_i=a_j+21(j<i)
$$

则有 $a_i-a_j=21$ ，即在 $j+1, j+2, \cdots, j+(i-j)$ 的连续 $i-j$ 天中下了 21 盘棋。

上一篇：没有了

下一篇：鸽笼原理的加强形式

本文对您是否有用？有用 (0) 无用 (0)