最后更新: 2025-01-22 08:54 查看: 171 次纠错评论(0) 课件开VIP

鸽笼原理基本原理

定理 $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 盘棋。

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：没有了

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

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