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

鸽笼原理的加强形式

定理5．3 设 $q_1, q_2, \cdots, q_n$ 都是正整数，若把 $q_1+q_2+\cdots+q_n-n+1$ 个元素分成 $n$ 个组，则
必然发生：或者第一组中至少有 $q_1$ 个元素；或者第二组中至少有 $q_2$ 个元素；$\cdots$ ；或者第 $n$ 组中至少有 $q_n$ 个元素。

证明：用反证法证明。若结论不成立，则对于 $i=1,2, \cdots, n$ ，第 $i$ 个组中至多有 $q_i-1$ 个元素，则 $n$ 个组的元素个数的总和不超过

$$
\sum_{i=1}^n\left(q_i-1\right)=q_1+q_2+\cdots+q_n-n
$$

这就导致矛盾。
由此定理立即可得 $q_1=q_2=\cdots=q_n=r$ 时的特殊情况。
推论5．1 若将 $n(r-1)+1$ 个元素分成 $n$ 个组，则至少有一个组中含有 $r$ 个或者更多的元素（这里 $n, ~ r$ 皆为正整数）。

推论5．2 若 $n$ 个正整数 $m_1, m_2, \cdots, m_n$ 的平均数满足不等式：

$$
\frac{m_1+m_2+\cdots+m_n}{n}>r-1
$$

则 $m_1, m_2, \cdots, m_n$ 中至少有一个不小于 $r_{\text {。 }}$
证明：因为 $\left(m_1+m_2+\cdots+m_n\right)>(r-1) n$ ，故

$$
\left(m_1+m_2+\cdots+m_n\right) \geqslant(r-1) n+1
$$

这就相当于把不少于 $n(r-1)+1$ 个元素分成 $n$ 个组，而 $m_i$ 就是第 $i$ 个组中的元素个数。由推论 5.1 知，必存在 $m_i$ 使得 $m_i \geqslant r$ 。

例 5.6 两个同心圆盘，将其圆周都均分为 200 段，从大盘上任选 100 段涂上红色，其余涂上蓝色，而在小盘的每个小段上任意涂上红色或蓝色。证明在旋转小盘时可以找到某个位置，使得小盘上至少有 100 个小段与大盘上对应段颜色相同。

证明：固定大盘，对小盘上任一段，在它旋转过程中，都将经历大盘上所有的 200 个段，从而构成 200 种颜色组合，其中同色的恰有 100 组。因小盘上共有 200 段，故小盘上的所有段在旋转一周后，与大盘对应段构成的同色组共有 20000 个。而旋转一周，将移动 200 次。设第 $i$ 次移动时产生的同色组个数为 $m_i$（这里 $i=1,2, \cdots, 200$ ），则总的同色组个数就是 $m_1+$ $m_2+\cdots+m_{200}=20000$ ，因此 200 个整数 $m_1, ~ m_2, ~ \cdots, m_{200}$ 的平均数满足下述不等式： $20000 / 200=100>100-1$ 。由推论 5.2 得，必存在某个位置，使得小盘上至少有 100 个小段与大盘上对应段颜色相同。

例 5.7 设 $a_1, a_2, \cdots, a_{n^2+1}$ 是 $n^2+1$ 个不同实数的序列，则必可从此序列中选出 $n+1$ 个数的子序列，使这子序列为递增序列或递减序列。

证明：若存在长度为 $n+1$ 的递增序列，结论成立。
若不存在长度为 $n+1$ 的递增序列，设 $m_k$ 为从 $a_k$ 开始的递增子序列的最大长度，则有 $1 \leqslant$ $m_k \leqslant n$ 。这样有 $m_1, m_2, \cdots, m_{n^2+1}$ 共 $n^2+1$ 个数。又因 $m_k$ 的取值为 $1,2, \cdots, n$ ，这相当于把 $n^2+1$ 个元素分成 $n$ 个组，现在

$$
\frac{n^2+1}{n}=n+\frac{1}{n}>n=(n+1)-1 \text { 。 }
$$

由推论 5.2 知必存在 $n+1$ 个数是相同的，即：

$$
m_{k 1}=m_{k 2}=\cdots=m_{k_{n+2}}=l\left(l \leqslant k_1<k_2 \leqslant \cdots<k_{n+1} \leqslant n^2+1\right)
$$

这样即得到一个子序列

$$
a_{k_1}, a_{k_2} \cdots a_{k_{n+1}\left(l \leqslant k_1<k_2<\cdots<k_{n+1} \leqslant n^2+1\right)}
$$

下面证明这是一个递减序列。
若不是递减序列，则存在 $i$ ，使得 $a_{k_i}<a_{k_{i+1}}$ 。因为 $k_i<k_{i+1}$ ，故可在以 $a_{k_{i+1}}$ 开始的最长递增子序列前边加上 $a_{k_i}$ ，则得到一个长度为 $l+1$ 的以 $a_{k_i}$ 开始的递增子序列，即 $m_{k_i} \geqslant l+1$ ，与 $m_{k_i}=l$ 矛盾，所以 $a_{k_i} \geqslant a_{k_{i+1}}$ 。

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：鸽笼原理基本原理

下一篇：基本计数原理

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