抽屉原理及其应用

盐城师范学院毕业论文(设计)

抽屉原理及其应用

许莉娟

(数学科学学院，2003（4）班，03213123号)

[摘 要]抽屉原理是数学中的重要原理,在解决数学问题时有非常重要的作用.各种形式的抽屉原理在高等数学和初等数学中经常被采用.本文着重从抽屉的构造方法阐述抽屉原理在高等数学和初等数学（竞赛题）中的应用,同时指出了它在应用领域中的不足之处.

[关键词]抽屉原理 高等数学 初等数学

抽屉原理也称为鸽笼原理或鞋箱原理，它是组合数学中的一个最基本的原理.抽屉原理主要用于证明某些存在性问题及必然性题目，如几何问题、涂色问题等.抽屉原理的简单形式可以描述为：“如果把n?1个球或者更多的球放进n个抽屉，必有一个抽屉至少有两个球.”它的正确性十分明显，很容易被并不具备多少数学知识的人所接受，如果将其灵活地运用，则可得到一些意想不到的效果.

各种形式的抽屉原理在高等数学和初等数学中经常被采用，使用该原理的关键在于如何巧妙地构造抽屉，即如何找出合乎问题条件的分类原则，抽屉构造得好，可得出非常巧妙的结论，下面我们着重从抽屉的构造途径去介绍抽屉原理在高等数学和初等数学(竞赛题)中的应用，同时指出它在应用领域中的不足之处.

一、抽屉原理

陈景林、阎满富编著的中国铁道出版社出版的《组合数学与图论》一书中对抽屉原理给出了比较具体的定义，概括起来主要有下面几种形式:

原理Ⅰ 把多于n个的元素按任一确定的方式分成n个集合，则一定有一个集合中含有两个或两个以上的元素.

原理Ⅱ 把m个元素任意放到n(m?n)个集合里，则至少有一个集合里至少有k个元素，其中

?m　　　,　　当n能整除m时,??nk???m??　　?1　,　　当n不能整除m时.　　???n???

原理Ⅲ 把无穷个元素按任一确定的方式分成有穷个集合，则至少有一个集合中仍含无穷个元素.

第 1 页 共 9 页

盐城师范学院毕业论文(设计)

原理Ⅱ、Ⅲ是对原理Ⅰ的进一步深入阐述，把抽屉原理推入了更深更广的层次.并且我们很容易对其进行证明，可见它们都是非常简单的原理，可是，正是这样一些简单的原则，在初等数学乃至高等数学中，有着许多应用.巧妙地运用这些原则，可以很顺利地解决一些看上去相当复杂，甚至觉得简直无法下手的数学题目.

二、抽屉的构造途径

在利用抽屉原理解题时，首先要明确哪些是“球”，哪些是“抽屉”，而这两者通常不会现成存在于题目中，尤其是“抽屉”，往往需要我们用一些巧妙的方法去构造.下面举例说明几种常见的抽屉构造法.

（一）利用等分区间构造抽屉

所谓等分区间简单的说即是：如果在长度为1的区间内有多于n个的点，可考虑把区间n等分成n个子区间，这样由抽屉原理可知，一定有两点落在同一子区间，它们之间的

1距离不大于.这种构造法常用于处理一些不等式的证明.

n例1 已知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个抽屉)，每一小段长为.由抽屉原理，11个点(数)中至少

101?11?有??+1=2个点落在同一条小线段上，这两点相应的数之差的绝对值?.

1010??

0 1

图1

例2 任给7个实数，证明必存在两个实数a,b满足0?3(a?b)?1+ab.

2,　?　,7),显然Qi∈(?证明 设七个实数为a1,a2,a3,?,a7，作Qi=arctgai(i?1,　??22,)，

把(???22,)等分成六个区间：(??2,??3)，(??3,??6)，(??6,0)，(0,?6)，(

????,)，(,)，6332由抽屉原理，Q1,Q2,?,Q7必有两个属于同一区间，不妨设为Qi,Qj,而不论Qi,Qj属于哪个小区间都有0?Qi?Qj??6，由正切函数的单调性可知，0?tg(Qi?Qj)?tg?6?13(?)，

第 2 页 共 9 页

盐城师范学院毕业论文(设计)

不妨记a?tgQi,b?tgQj，则tg(Qi?Qj)=

1a?ba?b,而由(?)知0?，又因为有 ?1?ab1?ab3a?b?0(Qi?Qj),1+ab?0, 从而有0?3(a?b)?1+ab.

对于给定了一定的长度或区间并要证明不等式的问题，我们常常采用等分区间的构造方法来构造抽屉，正如上面的两个例子，在等分区间的基础上我们便很方便的构造了抽屉，从而寻找到了证明不等式的一种非常特殊而又简易的方法，与通常的不等式的证明方法(构造函数法，移位相减法)相比，等分区间构造抽屉更简易，更容易被人接受.

（二）利用几何图形构造抽屉

在涉及到一个几何图形内有若干点时，常常是把图形巧妙地分割成适当的部分，然后用分割所得的小图形作抽屉.这种分割一般符合一个“分划”的定义，即抽屉间的元素既互不重复，也无遗漏；但有时根据解题需要，分割也可使得抽屉之间含有公共元素.

例3 如果直径为5的圆内有10个点，求证其中有某两点的距离小于2.

证明 先将圆分成八个全等的扇形，再在中间作一个直径d=1.8的圆(如图2)，这就把已知的圆分成了9个区域(抽屉).由抽屉原理，圆内的10个点(球)，必有两点落在同一区域内，只须证明每个区域中的两点的距离都小于2.显然，小圆内任两点间的距离小于2，又曲边扇形ABCD中，AB?2，AD?2，CD?2，而任两点距离最大者AC，有

AC=OA2?OC2?2OA?OCcos45?

=2.52?0.92?2.5?0.9?2 =3.88<2.

图2

（三）利用整数分组制构造抽屉

例4 对于m?1个不同的自然数，若每一数都小于2m,那么可以从中选取三个数，使

第 3 页 共 9 页

盐城师范学院毕业论文(设计)

其中两个数之和等于第三个数.

证明 把这m?1个自然数按单调递增顺序排列：a0?a1???am，作bi?ai?a0，

i=1,　2,　?　,m,则0?b1?b2???bm?am?2m，考察a1,a2,?,am,b1,b2,?,bm这2m个小于

2m的自然数，显然有bi?ai(i=1,　2,　?　,m)，则必有ai?bj=aj?a0,即a0?ai=aj.

例5 证明：从任意给出的5个整数中必能选出3个数，它们的和能被3整除. 证明 设这5个整数为t1,t2,?,t5，这些整数被3除的余数无非是0、1、2，把这些余数看作3个抽屉.若每个抽屉都有数，则各取一个，由0+1+2=3能被3整除知，这3个数之和也能被3整除；若不然，5个数至多落入2个抽屉，由抽屉原理知，至少有一个抽屉

?5?落入??+1=3个数，这3个数同余，其和能被3整除.

?2?（四）利用奇偶性分类构造抽屉

例6 平面上至少应给出几个格点(也称整点，即横坐标、纵坐标都是整数的点)，才能使得其中至少有两个点的连线的中点仍是一格点.

分析 设两个格点的坐标为(x1,y1),(x2,y2),则连线的中点坐标(

x1?x2y1?y2). ,22易见，为保证中点坐标为整数，当且仅当x1与x2,y1与y2同奇偶；因此，可按奇偶性将所有格点的坐标分类，共有(奇,奇)，(奇,偶)，(偶,奇)，(偶,偶)四种情况，把这四种情况看作抽屉，由抽屉原理，至少应给出5个格点，才能保证至少有两点属于同一类，从而才有两点连线的中点是格点(结果是显然的，证明从略).

（五）利用分组构造抽屉

利用这种构造法解题，确定分组的“对象”很关键.确定了“对象”之后，其个数相对于“球”的个数而言，又往往显得太多.只有把这些“对象”分成适当数量的组(即抽屉)后，才能应用抽屉原理.

例7 由小于100的27个不同的奇数组成的集合中，必有两个数，其和为102.

3,　5,　?　,99共50个数，现在要用它做成26个抽屉，而且至分析 小于100的奇数有1,　少有一抽屉不少于两个数，这两个数之和恰为102就解决了.

证明 将小于100的所有奇数分成26个组(抽屉)：A1={1},A2={3,99},A3={5,97},?,Ak

={2k-1,103-2k},?,A25={49,53},A26={51}.因为有27个奇数，??27?+1=2，所以由抽屉原 ??26?理，必有两个奇数落在同一抽屉，这两个数之和恰好等于102.

例7的分组对象较为明显，而有的题目的分组对象没有直接给出，要先把它们找出来，再分组.有时，虽然明确了分组对象，但抽屉(组)的构造不是很直观，须用递推方法进行

第 4 页 共 9 页

盐城师范学院毕业论文(设计)

分类.

（六）利用状态制构造抽屉

例8 设有六点，任意三点不共线，四点不共面，如果把这六个点两两用直线联系起来，并把这些直线涂以红色或者蓝色.求证：不论如何涂色，总可以找到三点，做成以它们为顶点的三角形，而这三角形三边涂有相同的颜色.

分析 设已知六点为A1,A2,A3,A4,A5,A6,由于任三点不共线，所以任三点均可作为某三角形的三个顶点.

证明 从六个点中任取一点A1，将A1与其余五点相连得到五条线段，线段如下所示：

A1A2,A1A3,A1A4,A1A5,A1A6,这五条线段只有两种颜色即红色或者蓝色，由抽屉原理知，至少有三条涂有同一种颜色.(颜色为抽屉，线段为元素)，不妨设A1A2,A1A3,A1A4,涂有红色，这时我们考察△A2A3A4.

(1)若△A2A3A4中有一条红色边，如A2A3，则△A1A2A3为三边同红的三角形； (2)若△A2A3A4中无一条红色边，则△A2A3A4就是三边均为蓝色的三角形. 综合所述，抽屉的构造方法大致可归结为两大类：一类是分割图形构造抽屉；一类是用分类的概念构造抽屉.抽屉构造之巧妙，常令人惊叹不已，拍案叫绝，抽屉的构造方法也不胜枚举，在这里我们旨在做到举一反三. 抽屉原理是组合数学中貌似平凡却透着不平凡应用定理之一，是Ramsey定理的基础，下面我们就来探讨抽屉原理在高等数学和初等数学(竞赛题)中的应用.

三、抽屉原理的应用

（一）抽屉原理在高等数学中的应用

高等数学中一些问题抽象，复杂，解答比较困难，如果一些问题巧妙地运用抽屉原理会收到很好的效果，下列举例介绍抽屉原理在高等数学中的巧妙应用.

例9 设A为n阶方阵，证明：存在1?i?n，使秩(Ai)=秩(Ai?1)=秩(Ai?2)??

　,　2,　?　,n这n+1个一,E?A0,A,A2,?,An,An?1,E证明 因为n阶方阵的秩只能是0,1的个数多于秩的个数，由抽屉原理可知，存在k,l满足1?k

秩(Ak)= 秩(Al),

但

秩(Ak)?秩(Ak?1)???秩(Al),

所以

秩(Ak)=秩(Ak?1),

利用此式与秩的性质得

第 5 页 共 9 页

本文来源：https://www.bwwdw.com/article/g83f.html