内容发布更新时间 : 2024/12/26 14:51:18星期一 下面是文章的全部内容请认真阅读。
Beihang College of Software 北航软件学院
原理3. 把无穷个元素按任一确定的方式分成有限个集合，则至少有一个集合中仍含无穷个元素。
卢开澄在《组合数学》（第三版）中将抽屉原理（书中称为鸽巢原理）又进行了推广[2]。
鸽巢原理：设k和n都是任意正整数，若至少有kn+1只鸽子分配在n个鸽巢中，则至少存在一个鸽巢中有至少k+1只鸽子。
?m?1?推论1.有m只鸽子和n个鸽巢，则至少有一个鸽巢中有不少于??+1只
?n?鸽子。
推论2.若将n(m-1)+1个球放入n个盒子里，则至少有一个盒子有m个球。
推论3.若m1,m2,mn是n个正整数，而且r=
m1?m2?n?mn，则
m1,m2,mn中至少有一个数不小于r。
另外，抽屉原理还可以用映射的形式来表示，即:设A和B是两个有限集，如果A>B，那么对从A到B的任何满射f，至少存在a1,a2,使f?a1??f?a2?。
3.抽屉原理的构造
通过了解抽屉原理的形式，我们可以利用它的特殊形式来解决不同的问题。首先，必须明确题目中应该以什么为抽屉，什么为物品。其次，构造合适的抽屉，需要注意的是抽屉的数量一定要少于物品的数量。最后，运用抽屉原理解决问题。其中，最重要最有难度的就是如何构造抽屉，构造抽屉是运用抽屉原理解题的关键，下面介绍几种常用的构造抽屉的方法。
3.1分割图形构造抽屉
在一个几何图形内有若干已知点，我们可以根据问题的要求把图形进行适当的分割，用这些分割成的图形作为抽屉，再对已知点进行分类，集中对某一个或几个抽屉进行进行讨论，使问题得到解决。
例1：在边长为2米的正方形内，任意放入13个点．求证：必有4个点，以它们为顶点的四边形的面积不超过1平方米。
5
Beihang College of Software 北航软件学院
(1) (2)
证明：把边长为2米的正方形分割成面积为1平方米的4个小正方形，如图1．因为13=3×4+1，所以由抽屉原理知，至少有4个点落在同一个面积为1平方米的小正方形内（或边上），以这4个点为顶点的四边形的面积总小于或等于小正方形的面积，即以这4个点为顶点的四边形的面积不超过1平方米。
3.2利用划分数组来构造抽屉
利用此方法解题的关键是要明确分组的“对象”,然后将这些对象分成适当的数组,再应用抽屉原理,问题便得以解决。
例2：任意给定7个不同的整数,求证:其中必有两数之和或差是10的倍数。 证明：设这7个不同的整数分别为t1,t2,...,t7,它们分别除以10后,得到的余数是从0到9中的一个数。
(1)若这7个余数中有两个数相同:设ti?10p?k,tj?10q?k?p、q为整数?,则ti?tj?10?p?q?,即ti?tj是10即存在两数之差是10的倍数。 的倍数， (2)若这7个余数中任何两个都不同,由抽屉原理知,至少有一数被10除余数为6、7、8、9四个数中的一个。
将余数为6的数与余数为4的数划为一组,余数为7的数与余数为3的数划为一组,余数为8的数与余数为2的数划为一组,余数为9的数与余数为1的数划为一组。于是便有,这7个不同的余数,除0,5外,其余的必有一组数它们做和是10的倍数。
3.3利用划分集合来构造抽屉
例3：在1,4,7,10,13，?，100中任选出20个数，其中至少有不同两组数，
6
Beihang College of Software 北航软件学院
其和都等于104，试证明之。
证明 给定的数共有34个，其相邻两数的差均为3，我们把这些数分成如下18个不相交的集合{且把它们看作是18个抽1}，{52}，{4,100}，{7,97}，，{49,55}，屉，从已知的34个数中任选20个数，即使把前两个抽屉中的数1和52都取出，则剩下的18个数在后面的16个抽屉中至少有不同的两个抽屉中的数全部被取出，这两个抽屉中的数互不相同，每个抽屉中的两个数的和都是104。
3.4利用等分区间构造抽屉
所谓等分区间简单的说即是：如果在长度为1的区间内有多于n个的点，可考虑把区间n等分成n个子区间，这样由抽屉原理可知，一定有两点落在同一子
1区间，它们之间的距离不大于.这种构造法常用于处理一些不等式的证明。
n例4：已知11个数x1,x2,?,x11,全满足0?xi?1 ,i＝1, 2 ? ,11,证明必有两个
xi,xj(i?j)满足xi?xj?1。 10证明 如图1，将实数轴上介于0与1那段(连同端点)等分为10小段(这10
1个小段也就是10个等分区间，即10个抽屉)，每一小段长为.由抽屉原理，
10?11?11个点(数)中至少有??+1=2个点落在同一条小线段上，这两点相应的数之差
?10?的绝对值?1。 10
0 1
图1
例5：任给7个实数，证明必存在两个实数a,b满足0?3(a?b)?1+ab. 证明 设七个实数为a1,a2,a3,?,a7，作Qi=arctga2, ? ,7),显然Qi∈i(i?1, (?(0,??22,)，把(???22,)等分成六个区间：(??2,??3)，(??3,??6)，(??6,0)，
?6)，(
??63,)，(
??,)，由抽屉原理，Q1,Q2,?,Q7必有两个属于同一区间，
32不妨设为Qi,Qj,而不论Qi,Qj属于哪个小区间都有0?Qi?Qj?的单调性可知，0?tg(Qi?Qj)?tg
?6，由正切函数
?6?7
13(?)，不妨记a?tgQi,b?tgQj，则
Beihang College of Software 北航软件学院
tg(Qi?Qj)=
a?b,而由(?)知1?ab0?a?b?1?ab13，又因为有
a?b?0(Qi?Qj),1+ab?0, 从而有0?3(a?b)?1+ab。
对于给定了一定的长度或区间并要证明不等式的问题，我们常常采用等分区间的构造方法来构造抽屉，正如上面的两个例子，在等分区间的基础上我们便很方便的构造了抽屉，从而寻找到了证明不等式的一种非常特殊而又简易的方法，与通常的不等式的证明方法(构造函数法，移位相减法)相比，等分区间构造抽屉更简易，更容易被人接受。
3.5利用奇偶性分类构造抽屉
例6：平面上至少应给出几个格点(也称整点，即横坐标、纵坐标都是整数的点)，才能使得其中至少有两个点的连线的中点仍是一格点。
证明 设两个格点的坐标为(x1,y1),(x2,y2),则连线的中点坐标(
x1?x2y1?y2,)。易见，为保证中点坐标为整数，当且仅当x1与x2,y1与y2同
22奇偶；因此，可按奇偶性将所有格点的坐标分类，共有(奇,奇)，(奇,偶)，(偶,
奇)，(偶,偶)四种情况，把这四种情况看作抽屉，由抽屉原理，至少应给出5个格点，才能保证至少有两点属于同一类，从而才有两点连线的中点是格点(结果是显然的，证明从略)。
3.6利用状态制构造抽屉
例7：设有六点，任意三点不共线，四点不共面，如果把这六个点两两用直线联系起来，并把这些直线涂以红色或者蓝色.求证：不论如何涂色，总可以找到三点，做成以它们为顶点的三角形，而这三角形三边涂有相同的颜色。
分析 设已知六点为A1,A2,A3,A4,A5,A6,由于任三点不共线，所以任三点均可作为某三角形的三个顶点。
证明 从六个点中任取一点A1，将A1与其余五点相连得到五条线段，线段如下所示： A1A2,A1A3,A1A4,A1A5,A1A6,这五条线段只有两种颜色即红色或者蓝色，由抽屉原理知，至少有三条涂有同一种颜色.(颜色为抽屉，线段为元素)，不妨设A1A2,A1A3,A1A4,涂有红色，这时我们考察△A2A3A4。
8
Beihang College of Software 北航软件学院
(1)若△A2A3A4中有一条红色边，如A2A3，则△A1A2A3为三边同红的三角形。
(2)若△A2A3A4中无一条红色边，则△A2A3A4就是三边均为蓝色的三角形. 抽屉构造之巧妙，常令人惊叹不已，拍案叫绝，抽屉的构造方法也不胜枚举，在这里我们旨在做到举一反三. 抽屉原理是组合数学中貌似平凡却透着不平凡应用定理之一，是Ramsey定理的基础，下面我们就来探讨抽屉原理在高等数学和初等数学(竞赛题)中的应用。
4.抽屉原理的应用
4.1抽屉原理在数学中的应用
接下来，在了解了抽屉原理的基本形式以及多位学者所发展的推广形式的基础上，我们通过一些比较典型的实例来说明抽屉原理在高等数学中代数、数论、几何这三个方面的应用。
4.1.1解决代数问题
用集合的语言抽屉原理可以叙述如下：
（1）设n个元素按任意确定方式分成有限个集合，那么至少有一个集合含有两个元素。
（2）设有无穷多个元素按任意确定方式分成有限个集合，那么至少有一个集合含有无穷多个元素。
例1证明:有限群中的每个元素的阶均有限。 ．
证明：设G为n阶有限群，任取a∈G，则由抽屉原理可知
a,a2,a3,......,an,an?1中必有相等的．不妨设as?at,1?t?s?n?1于是有
as?t?e，从而a的阶有限。
例2：设A为n阶方阵，证明：存在 ．．
1?k?n,使秩（Ak）=秩（Ak?1）证明：因为n阶方阵的秩只能是0,1,2,3，?，n这n?1个数之一，而
9