抽屉原理及其应用.doc

抽屉原理及其应用.doc 盐城师范学院毕业论文(设计) 抽屉原理及其应用 许莉娟 (数学科学学院～2003,4,班～03213123号) [摘 要]抽屉原理是数学中的重要原理,在解决数学问时有非常重要的作用.各种形式的抽屉原理在高等数学和初等数学中经常被采用.本文着重从抽屉的构造方法阐述抽屉原理在高等数学和初等数学,竞赛题,中的应用,同时指出了它在应用领域中的不足之处. [关键词]抽屉原理 高等数学 初等数学 抽屉原理也称为鸽笼原理或鞋箱原理，它是组合数学中的一个最基本的原理.抽屉原理主要用于证明某些存在性问题及必然性题目，如几何问题、涂色问题等.抽屉原理的简 n，1单形式可以描述为:“如果把个球或者更多的球放进个抽屉，必有一个抽屉至少有n 两个球.”它的正确性十分明显，很容易被并不具备多少数学知识的人所接受，如果将其灵活地运用，则可得到一些意想不到的效果. 各种形式的抽屉原理在高等数学和初等数学中经常被采用，使用该原理的关键在于如何巧妙地构造抽屉，即如何找出合乎问题条件的分类原则，抽屉构造得好，可得出非常巧妙的结论，下面我们着重从抽屉的构造途径去介绍抽屉原理在高等数学和初等数学(竞赛题)中的应用，同时指出它在应用领域中的不足之处. 一、抽屉原理 陈景林、阎满富编著的中国铁道出版社出版的《组合数学与图论》一书中对抽屉原理给出了比较具体的定义，概括起来主要有下面几种形式: 原理? 把多于个的元素按任一确定的方式分成个集合，则一定有一个集合中含有nn 两个或两个以上的元素. (m,n)k原理? 把个元素任意放到个集合里，则至少有一个集合里至少有个元mn 素，其中 m ,　　　,　　当能整除时,nm,n,k,,m，，,　　　,　　当不能整除时.　　，1nm,,,n，，, 原理? 把无穷个元素按任一确定的方式分成有穷个集合，则至少有一个集合中仍含无穷个元素. 第 1 页 共 9 页 盐城师范学院毕业论文(设计) 原理?、?是对原理?的进一步深入阐述，把抽屉原理推入了更深更广的层次.并且我们很容易对其进行证明，可见它们都是非常简单的原理，可是，正是这样一些简单的原则，在初等数学乃至高等数学中，有着许多应用.巧妙地运用这些原则，可以很顺利地解决一些看上去相当复杂，甚至觉得简直无法下手的数学题目. 二、抽屉的构造途径 在利用抽屉原理解题时，首先要明确哪些是“球”，哪些是“抽屉”，而这两者通常不会现成存在于题目中，尤其是“抽屉”，往往需要我们用一些巧妙的方法去构造.下面举例说明几种常见的抽屉构造法. (一)利用等分区间构造抽屉 所谓等分区间简单的说即是:如果在长度为1的区间内有多于个的点，可考虑把区n 间等分成个子区间，这样由抽屉原理可知，一定有两点落在同一子区间，它们之间的 nn 1距离不大于.这种构造法常用于处理一些不等式的证明. n 0,x,1　,i,1,　2　？　,11i,jx,x,？,xx,x例1 已知11个数,全满足,证明必有两个()1211iij 1x,x满足. ,ij10 证明 如图1，将实数轴上介于0与1那段(连同端点)等分为10小段(这10个小段也 1就是10个等分区间，即10个抽屉)，每一小段长为.由抽屉原理，11个点(数)中至少10 111，，有+1=2个点落在同一条小线段上，这两点相应的数之差的绝对值. ,,,1010，， 0 1 图1 ,(a,b)abb3例2 任给7个实数，证明必存在两个实数满足01+. ,,a ,,a,a,a,？,ai,1,　2,　？　,7QarctgaQ证明 设七个实数为，作=(),显然?(,)，,1237iii22 ,,,,,,,,,,,,,,,,把(,)等分成六个区间:()，()，()，()，()，()，0,,,,,,,,0222336663326 Q,Q,？,QQ,QQ,Q由抽屉原理，必有两个属于同一区间，不妨设为,而不论属于哪127ijij 1,,00,tg(Q,Q),tg,(,)个小区间都有，由正切函数的单调性可知，，,Q,Q,ijij663 第 2 页 共 9 页 盐城师范学院毕业论文(设计) a,ba,b1,(,)a,tgQ,b,tgQtg(Q,Q)不妨记，则=,而由知0，又因为有 ,ijij1，ab1，ab3 ,a,b,0ab,0(a,b)abQ,Q3(),1+, 从而有01+. ,ij 对于给定了一定的长度或区间并要证明不等式的问题，我们常常采用等分区间的构造方法来构造抽屉，正如上面的两个例子，在等分区间的基础上我们便很方便的构造了抽屉，从而寻找到了证明不等式的一种非常特殊而又简易的方法，与通常的不等式的证明方法(构造函数法，移位相减法)相比，等分区间构造抽屉更简易，更容易被人接受. (二)利用几何图形构造抽屉 在涉及到一个几何图形内有若干点时，常常是把图形巧妙地分割成适当的部分，然后用分割所得的小图形作抽屉.这种分割一般符合一个“分划”的定义，即抽屉间的元素既互不重复，也无遗漏;但有时根据解题需要，分割也可使得抽屉之间含有公共元素. 例3 如果直径为5的圆内有10个点，求证其中有某两点的距离小于2. d证明 先将圆分成八个全等的扇形，再在中间作一个直径=1.8的圆(如图2)，这就把已知的圆分成了9个区域(抽屉).由抽屉原理，圆内的10个点(球)，必有两点落在同一区域内，只须证明每个区域中的两点的距离都小于2.显然，小圆内任两点间的距离小于2， AB,ADABCDCDAC又曲边扇形中，2，2，2，而任两点距离最大者，有 ,, 22,ACOA，OC,2OA,OCcos45= 222.5，0.9,2.5，0.9，2= 23.88=<. 图2 (三)利用整数分组制构造抽屉 m，12m例4 对于个不同的自然数，若每一数都小于,那么可以从中选取三个数，使 第 3 页 共 9 页 盐城师范学院毕业论文(设计) 其中两个数之和等于第三个数. m，1a,a,？,ab,a,a证明 把这个自然数按单调递增顺序排列:，作， 01mii01,　2,　？　,m0,b,b,？,b,a,2ma,a,？,a,b,b,？,bi2m=,则，考察这个小于12mm12m12m i1,　2,　？　,ma，a2mb,aa,ba,aa的自然数，显然有(=)，则必有=,即=. iiijj00ij 例5 证明:从任意给出的5个整数中必能选出3个数，它们的和能被3整除. t,t,？,t证明 设这5个整数为，这些整数被3除的余数无非是0、1、2，把这些余125 数看作3个抽屉.若每个抽屉都有数，则各取一个，由0+1+2=3能被3整除知，这3个数之和也能被3整除;若不然，5个数至多落入2个抽屉，由抽屉原理知，至少有一个抽屉 5，，落入+1=3个数，这3个数同余，其和能被3整除. ,,2，， (四)利用奇偶性分类构造抽屉 例6 平面上至少应给出几个格点(也称整点，即横坐标、纵坐标都是整数的点)，才能使得其中至少有两个点的连线的中点仍是一格点. x，xy，y1212xyxy 设两个格点的坐标为(),(),则连线的中点坐标(). ,,,121222 xxyy易见，为保证中点坐标为整数，当且仅当与,与同奇偶;因此，可按奇偶性将所1221 有格点的坐标分类，共有(奇,奇)，(奇,偶)，(偶,奇)，(偶,偶)四种情况，把这四种情况看作抽屉，由抽屉原理，至少应给出5个格点，才能保证至少有两点属于同一类，从而才有两点连线的中点是格点(结果是显然的，证明从略). (五)利用分组构造抽屉 利用这种构造法解题，确定分组的“对象”很关键.确定了“对象”之后，其个数相对于“球”的个数而言，又往往显得太多.只有把这些“对象”分成适当数量的组(即抽屉)后，才能应用抽屉原理. 例7 由小于100的27个不同的奇数组成的集合中，必有两个数，其和为102. 1,　3,　5,　？　,99分析 小于100的奇数有共50个数，现在要用它做成26个抽屉，而且至少有一抽屉不少于两个数，这两个数之和恰为102就解决了. AAAA证明 将小于100的所有奇数分成26个组(抽屉):={1},={3,99},={5,97} ,？,23k1 27，，AAkk={2-1,103-2}={49,53},={51}.因为有27个奇数，+1=2，所以由抽屉原 ,？,2526,,26，， 理，必有两个奇数落在同一抽屉，这两个数之和恰好等于102. 例7的分组对象较为明显，而有的题目的分组对象没有直接给出，要先把它们找出来，再分组.有时，虽然明确了分组对象，但抽屉(组)的构造不是很直观，须用递推方法进行 第 4 页 共 9 页 盐城师范学院毕业论文(设计) 分类. (六)利用状态制构造抽屉 例8 设有六点，任意三点不共线，四点不共面，如果把这六个点两两用直线联系起来，并把这些直线涂以红色或者蓝色.求证:不论如何涂色，总可以找到三点，做成以它们为顶点的三角形，而这三角形三边涂有相同的颜色. A,A,A,A,A,A,分析 设已知六点为由于任三点不共线，所以任三点均可作为某三123456 角形的三个顶点. AA证明 从六个点中任取一点，将与其余五点相连得到五条线段，线段如下所示: 11 AA,AA,AA,AA,AA,这五条线段只有两种颜色即红色或者蓝色，由抽屉原理知，至1213141516 AA,AA,AA,少有三条涂有同一种颜色.(颜色为抽屉，线段为元素)，不妨设涂有红色，121314 AAA这时我们考察?. 234 AAAAAAAA(1)若?中有一条红色边，如，则?为三边同红的三角形; 23423123 AAAAAA(2)若?中无一条红色边，则?就是三边均为蓝色的三角形. 234234 综合所述，抽屉的构造方法大致可归结为两大类:一类是分割图形构造抽屉;一类是用分类的概念构造抽屉.抽屉构造之巧妙，常令人惊叹不已，拍案叫绝，抽屉的构造方法也不胜枚举，在这里我们旨在做到举一反三. 抽屉原理是组合数学中貌似平凡却透着不平凡应用定理之一，是Ramsey定理的基础，下面我们就来探讨抽屉原理在高等数学和初等数学(竞赛题)中的应用. 三、抽屉原理的应用 (一)抽屉原理在高等数学中的应用 高等数学中一些问题抽象，复杂，解答比较困难，如果一些问题巧妙地运用抽屉原理会收到很好的效果，下列举例介绍抽屉原理在高等数学中的巧妙应用. ii，1i，2AAA,i,n(A),？例9 设为阶方阵，证明:存在1，使秩()=秩()=秩 n 02nn，1E,E0,1　,　2,　？　,nA,A,A,？,A,A证明 因为阶方阵的秩只能是这+1个一,,nn ,,klkl的个数多于秩的个数，由抽屉原理可知，存在,满足1<使 n klAA秩()= 秩(), 但 kk，1l,,,AAA秩()秩()„秩(), 所以 kk，1AA秩()=秩(), 利用此式与秩的性质得 第 5 页 共 9 页 盐城师范学院毕业论文(设计) ,ABBABCBC秩()秩()+秩()-秩(), A,B,C这里的是任意三个可乘矩阵，用数学归纳法可证 k，mk，m，1AA秩()=秩(). 其中为非负整数，故命题的结论成立. m Pp,p,？,pk,l(1,k,l,n)pp？例10 从阶群中任取个元素，证明存在,使 nn12nkk，1p,e(单位元). l |P|,ne,p,pp,？,pp？pn，1证明 ，用所取元素的积及作序列:,那么它的项e11212n Ppp？p,e都是中的元素，根据抽屉原理，上述序列中必有两项相等.如果，此时，12jk,1,l,j符合要求;否则有 l,j,1pp？p,pp？pp？p ()， 12j12jj，1l 于是有 1,pp？p,(pp？p)(pp？p),e， j1j2l12j12j，， k,j，11,l,n取，有，使 pp？p,e. kk，1l (二)抽屉原理在初等数学(竞赛题)中的应用 初等数学问题的特点是:只涉及一些相关的条件，或者有时虽然给出一些数值条件，但也不能应用这些条件通过通常的数学方法或计算、或代入求值、或列方程、或做图、或证明等方法予以解决，而只能借助给出的相关联的条件给予推理、判断，从而解决问题.下面我们就列举抽屉原理在初等数学(竞赛)中的应用. 例11 某次考试有5道选择题，每题都有4个不同的答案供选择，每人每题恰选1个答案.在2000份答卷中发现存在一个,使得任何份答卷中都存在4份，其中每2份的答nn 案都至多3题相同.的最小可能值.(2000，中国数学奥林匹克) n (g,h,i,j,k)解 将每道题的4种答案分别记为1，2，3，4，每份上的答案记为， ,,,,h,i,j,kg,h,i,j,k,1,2,3,4(1,h,i,j,k),(2,h,i,j,k),(3,h,i,j,k),(4,h,i,j,k)其中，令，=1，2，3，4，共得256个四元组. 由于2000=2567+208，故由抽屉原理知，有8份试卷上的答案属于同一个四元组.， 取出这8份试卷后，余下的1992份试卷中仍有8份属于同一个四元组，再取出这8份试卷，余下的1984份试卷中又有8份属于同一个四元组.又取出这8份试卷.三次共取出24份试卷，在这24份试卷中，任何4份中总有2份的答案属于同一个四元组，当然不满足 n,25题目的要求.所以，. 下面证明可以取到25. n ,,,,SS,(g,h,i,j,k)|g，h，i，j，k,0(mod4),g,h,i,j,k,1,2,3,4.S令则=256，且中去掉6个元素，当余下的250种答案中的每种答案都恰有8人选用时，共得到2000份答案， 第 6 页 共 9 页 ？ 盐城师范学院毕业论文(设计) S其中的25份答案中，总有4份不相同.由于它们都在中，当然满足题目要求.这明，=25n满足题目要求. 综上可知，所求的的最小可能值为25. n 先运用抽屉原理给出的下界，然后用构造法给出例子.这是一道典型的运用构造法解n 题的好题目.在解题中合理构造抽屉往往会收到意想不到的效果. 四、抽屉原理在应用领域中的不足 曹汝成编著的由华南理工大学出版社出版的《组合数学》教科书中指出，应用抽屉原理虽然可以解决许多涉及存在性的组合问题,但对于一些更加复杂的有关存在性的组合问题，抽屉原理显得无能为力，这时我们就需要运用抽屉原理的推广定理Ramsey定理来解决问题，下面我们就来探讨抽屉原理在应用上的不足. Ramsey定理可以视为抽屉原理的推广，1958年6-7月号美国《数学月刊》登载着这样一个有趣的问题:“任何六个人的聚会，总会有3人互相认识或3人互相不认识.”这就是著名的Ramsey问题.以6个顶点分别代表6个人，如果两人相识，则在相应的两点间连一条红边，否则在相应的两点间连一蓝边，则上述的Ramsey问题等价于下面的命题1. K命题1 对6个顶点的完全图任意进行红、蓝两边着色，都存在一个红色三角形或6 蓝色三角形. 命题1和上面的例8是相同的题型，由例8的证明可知，运用抽屉原理可以很容易很简便地对其进行证明.现将命题1推广成下面的命题2. K命题2 对六个顶点的完全图任意进行红、蓝两边着色，都至少有两个同色三角形. 6 由于命题2是要证明至少存在两个同色三角形的问题，而抽屉原理一般只局限在证明至少存在一个或必然存在一个的问题，所以对于上述命题抽屉原理就显得无能为力，这时需要运用Ramsey定理来解决问题. v,v,v,vv,v,KK证明 设是的六个顶点，由上面的命题1可知，对任意进行红、12345666 vvv蓝两边着色都有一个同色三角形，不妨设?是红色三角形.以下分各种情况来讨论 123 vv,vv,vvv,v,vvv(1)若均为蓝边，如图4所示，则若之间有一蓝边，不妨设为，14151645645 vvvvvv则三角形?为蓝色三角形;否则，?为红色三角形. 145456 第 7 页 共 9 页 盐城师范学院毕业论文(设计) 图4 图5 vv,vv,vvvv,vvvv(2)若中有一条红边，不妨设为红边，此时若边中有一条红141516142434 vvvvv边，不妨设是红边，则?是一红色三角形，见图5. 34134 vv,vvv以下就均为蓝边的情况对与相关联的边的颜色进行讨论. 24344 vv,vvvv,vvvv (?)若中有一蓝边，不妨设为蓝边，如图6，此时，若均为红边，4546452535 vvvvvvvvv则?是红色三角形;否则，?或?是蓝色三角形. 235245345 vv,vvv,v,vvv (?)若均为红边，见图7，此时，若之间有一条红边，不妨设为454615615 vvvvvv红边，则?为红色三角形;否则，?为蓝色三角形. 145156 图6 图7 K 由以上对各种情况的讨论知，对的任意红、蓝两边着色均有两个同色三角形. 6 从以上例子可知，抽屉原理在应用上确有不足之处，之上只是个特例，至于在别的领域中的不足之处还需我们进一步的探索. [参考文献] [1]陈景林,阎满富.组合数学与图论.北京:中国铁道出版社出版,2000.4-6 [2]曹汝成.组合数学.广州:华南理工大学出版社,2001.170-173 [3]忘向东,周士藩等.高等代数常用方法.山西:高校联合出版社,1989.64-66 [4]刘否南.华夏文集.太原:高校联合出版社,1995.88-90 第 8 页 共 9 页 盐城师范学院毕业论文(设计) [5]魏鸿增等.抽屉原理在高等数学中的应用.数学通报,1995,2.3-4 [6]严示健.抽屉原则及其它的一些应用.数学通报,1998,4.10-11 The principle of drawer and its application Xu Lijuan [Abstract]The principle of drawer is important in mathematics, which is very useful in solving the problem of mathematics. The principle of drawer with multiform show is often used in higher mathematics and primary mathematics. In this paper, the application of the principle of drawer in higher mathematics and primary mathematics (competition subjects) is emphatically discussed from the construction method of the principle of drawer. At the same time, the deficiency of the principle of drawer in application field is also pointed out in this paper. [Key Words]the principle of drawer, advanced mathematics, primary mathematics 第 9 页 共 9 页