《抽屉原理及其应用》由会员分享，可在线阅读，更多相关《抽屉原理及其应用（9页珍藏版）》请在金锄头文库上搜索。
1、盐城师范学院毕业论文(设计)第 1 页 共 9 页抽屉原理及其应用许许莉娟莉娟(数学科学学院，2003（4）班，03213123 号)摘 要抽屉原理是数学中的重要原理,在解决数学问题时有非常重要的作用.各种形式的抽屉原理在高等数学和初等数学中经常被采用.本文着重从抽屉的构造方法阐述抽屉原理在高等数学和初等数学（竞赛题）中的应用,同时指出了它在应用领域中的不足之处.关键词抽屉原理 高等数学 初等数学抽屉原理也称为鸽笼原理或鞋箱原理，它是组合数学中的一个最基本的原理.抽屉原理主要用于证明某些存在性问题及必然性题目，如几何问题、涂色问题等.抽屉原理的简单形式可以描述为：“如果把个球或者更多的球放进个
2、抽屉，必有一个抽屉至少有1nn两个球.”它的正确性十分明显，很容易被并不具备多少数学知识的人所接受，如果将其灵活地运用，则可得到一些意想不到的效果.各种形式的抽屉原理在高等数学和初等数学中经常被采用，使用该原理的关键在于如何巧妙地构造抽屉，即如何找出合乎问题条件的分类原则，抽屉构造得好，可得出非常巧妙的结论，下面我们着重从抽屉的构造途径去介绍抽屉原理在高等数学和初等数学(竞赛题)中的应用，同时指出它在应用领域中的不足之处.一、抽屉原理陈景林、阎满富编著的中国铁道出版社出版的组合数学与图论一书中对抽屉原理给出了比较具体的定义，概括起来主要有下面几种形式:原理 把多于个的元素按任一确定的方式分成个
3、集合，则一定有一个集合中含nn有两个或两个以上的元素.原理 把个元素任意放到个集合里，则至少有一个集合里至少有个元mn)(nm k素，其中原理 把无穷个元素按任一确定的方式分成有穷个集合，则至少有一个集合中仍含无穷个元素.1mnmnkmnmn , 当能整除时, 当不能整除时. 盐城师范学院毕业论文(设计)第 2 页 共 9 页原理、是对原理的进一步深入阐述，把抽屉原理推入了更深更广的层次.并且我们很容易对其进行证明，可见它们都是非常简单的原理，可是，正是这样一些简单的原则，在初等数学乃至高等数学中，有着许多应用.巧妙地运用这些原则，可以很顺利地解决一些看上去相当复杂，甚至觉得简直无法下手的数学
4、题目.二、抽屉的构造途径在利用抽屉原理解题时，首先要明确哪些是“球” ，哪些是“抽屉” ，而这两者通常不会现成存在于题目中，尤其是“抽屉” ，往往需要我们用一些巧妙的方法去构造.下面举例说明几种常见的抽屉构造法.（一）利用等分区间构造抽屉所谓等分区间简单的说即是：如果在长度为 1 的区间内有多于个的点，可考虑把区n间等分成个子区间，这样由抽屉原理可知，一定有两点落在同一子区间，它们之间的nn距离不大于.这种构造法常用于处理一些不等式的证明.n1例 1 已知 11 个数,全满足,证明必有两个(1121,xxxL11,2, 1, 10 Lixijixx ,)满足.ji jixx 101证明 如图
5、1，将实数轴上介于 0 与 1 那段(连同端点)等分为 10 小段(这 10 个小段也就是 10 个等分区间，即 10 个抽屉)，每一小段长为.由抽屉原理，11 个点(数)中至少101有+1=2 个点落在同一条小线段上，这两点相应的数之差的绝对值. 1011 101图 1 例 2 任给 7 个实数，证明必存在两个实数满足 01+.a,b3)(ba ab证明 设七个实数为，作=(),显然()，7321,aaaaLiQiarctga7 , 2, 1 LiiQ2,2把()等分成六个区间：()，()，()，()，()，(2,23,26,30 ,66, 0 3,6)，由抽屉原理，必有两个属于同一区间，不
6、妨设为,而不论2,3721,QQQLiQjQ,iQ属于哪个小区间都有，由正切函数的单调性可知，jQ,60jiQQ，不妨记，则=,而由)(31 6)(0tgQQtgjijitgQbtgQa,)(jiQQtgabba 10 1盐城师范学院毕业论文(设计)第 3 页 共 9 页知 0，又因为有 (),1+, 从而有 01+)(abba 1310bajiQQ 0ab3)(ba .ab对于给定了一定的长度或区间并要证明不等式的问题，我们常常采用等分区间的构造方法来构造抽屉，正如上面的两个例子，在等分区间的基础上我们便很方便的构造了抽屉，从而寻找到了证明不等式的一种非常特殊而又简易的方法，与通常的不等式的
7、证明方法(构造函数法，移位相减法)相比，等分区间构造抽屉更简易，更容易被人接受.（二）利用几何图形构造抽屉在涉及到一个几何图形内有若干点时，常常是把图形巧妙地分割成适当的部分，然后用分割所得的小图形作抽屉.这种分割一般符合一个“分划”的定义，即抽屉间的元素既互不重复，也无遗漏；但有时根据解题需要，分割也可使得抽屉之间含有公共元素.例 3 如果直径为 5 的圆内有 10 个点，求证其中有某两点的距离小于 2.证明 先将圆分成八个全等的扇形，再在中间作一个直径=1.8 的圆(如图 2)，这就d把已知的圆分成了 9 个区域(抽屉).由抽屉原理，圆内的 10 个点(球)，必有两点落在同一区域内，只须证
8、明每个区域中的两点的距离都小于 2.显然，小圆内任两点间的距离小于 2，又曲边扇形中，2，2，2，而任两点距离最大者，有ABCDABADCDAC=ACo45cos222OCOAOCOA=29 . 05 . 29 . 05 . 222=.88. 32图 2（三）利用整数分组制构造抽屉例 4 对于个不同的自然数，若每一数都小于,那么可以从中选取三个数，使1mm2盐城师范学院毕业论文(设计)第 4 页 共 9 页其中两个数之和等于第三个数.证明 把这个自然数按单调递增顺序排列：，作， 1mmaaaL100aabii=,则，考察这个小于im, 2, 1 Lmabbbmm2021Lmmbbbaaa,21
9、21LLm2的自然数，显然有( =)，则必有=,即=.m2iiab im, 2, 1 Ljiba 0aajiaa 0ja例 5 证明：从任意给出的 5 个整数中必能选出 3 个数，它们的和能被 3 整除.证明 设这 5 个整数为，这些整数被 3 除的余数无非是 0、1、2，把这些余521,tttL数看作 3 个抽屉.若每个抽屉都有数，则各取一个，由 0+1+2=3 能被 3 整除知，这 3 个数之和也能被 3 整除；若不然，5 个数至多落入 2 个抽屉，由抽屉原理知，至少有一个抽屉落入+1=3 个数，这 3 个数同余，其和能被 3 整除. 25（四）利用奇偶性分类构造抽屉例 6 平面上至少应给
10、出几个格点(也称整点，即横坐标、纵坐标都是整数的点)，才能使得其中至少有两个点的连线的中点仍是一格点.分析 设两个格点的坐标为(),(),则连线的中点坐标().1x ,1y2x,2y221xx ,221yy 易见，为保证中点坐标为整数，当且仅当与,与同奇偶；因此，可按奇偶性将1x2x1y2y所有格点的坐标分类，共有(奇,奇)，(奇,偶)，(偶,奇)，(偶,偶)四种情况，把这四种情况看作抽屉，由抽屉原理，至少应给出 5 个格点，才能保证至少有两点属于同一类，从而才有两点连线的中点是格点(结果是显然的，证明从略).（五）利用分组构造抽屉利用这种构造法解题，确定分组的“对象”很关键.确定了“对象”之
11、后，其个数相对于“球”的个数而言，又往往显得太多.只有把这些“对象”分成适当数量的组(即抽屉)后，才能应用抽屉原理.例 7 由小于 100 的 27 个不同的奇数组成的集合中，必有两个数，其和为 102.分析 小于 100 的奇数有共 50 个数，现在要用它做成 26 个抽屉，而且至99, 5, 3, 1 L少有一抽屉不少于两个数，这两个数之和恰为 102 就解决了.证明 将小于 100 的所有奇数分成 26 个组(抽屉)：=1,=3,99,=5,971A2A3A,LkA=2-1,103-2=49,53,=51.因为有 27 个奇数，+1=2，所以由抽屉kk,L25A26A 2627原理，必有
12、两个奇数落在同一抽屉，这两个数之和恰好等于 102.例 7 的分组对象较为明显，而有的题目的分组对象没有直接给出，要先把它们找出盐城师范学院毕业论文(设计)第 5 页 共 9 页来，再分组.有时，虽然明确了分组对象，但抽屉(组)的构造不是很直观，须用递推方法进行分类.（六）利用状态制构造抽屉例 8 设有六点，任意三点不共线，四点不共面，如果把这六个点两两用直线联系起来，并把这些直线涂以红色或者蓝色.求证：不论如何涂色，总可以找到三点，做成以它们为顶点的三角形，而这三角形三边涂有相同的颜色.分析 设已知六点为由于任三点不共线，所以任三点均可作为某,654321AAAAAA三角形的三个顶点.证明
13、从六个点中任取一点，将与其余五点相连得到五条线段，线段如下所示： 1A1A这五条线段只有两种颜色即红色或者蓝色，由抽屉原理知，,6151413121AAAAAAAAAA至少有三条涂有同一种颜色.(颜色为抽屉，线段为元素)，不妨设涂有红,413121AAAAAA色，这时我们考察.432AAA(1)若中有一条红色边，如，则为三边同红的三角形；432AAA32AA321AAA(2)若中无一条红色边，则就是三边均为蓝色的三角形.432AAA432AAA综合所述，抽屉的构造方法大致可归结为两大类：一类是分割图形构造抽屉；一类是用分类的概念构造抽屉.抽屉构造之巧妙，常令人惊叹不已，拍案叫绝，抽屉的构造方法
14、也不胜枚举，在这里我们旨在做到举一反三. 抽屉原理是组合数学中貌似平凡却透着不平凡应用定理之一，是 Ramsey 定理的基础，下面我们就来探讨抽屉原理在高等数学和初等数学(竞赛题)中的应用.三、抽屉原理的应用（一）抽屉原理在高等数学中的应用高等数学中一些问题抽象，复杂，解答比较困难，如果一些问题巧妙地运用抽屉原理会收到很好的效果，下列举例介绍抽屉原理在高等数学中的巧妙应用.例 9 设为阶方阵，证明：存在 1，使秩()=秩()=秩Anni iA1iAL)(2iA证明 因为阶方阵的秩只能是这+1 个一,nn, 2, 1, 0 LnE120,nnAAAAAL的个数多于秩的个数，由抽屉原理可知，存在,
15、 满足 1使Eklkln秩()= 秩(),kAlA但秩()秩()秩(),kA1kAlA所以秩()=秩(),kA1kA盐城师范学院毕业论文(设计)第 6 页 共 9 页利用此式与秩的性质得秩()秩()+秩()-秩(),ABCABBCB这里的是任意三个可乘矩阵，用数学归纳法可证CBA,秩()=秩().mkA1mkA其中为非负整数，故命题的结论成立.m例 10 从阶群中任取个元素，证明存在,使nPnnppp,21L)1 (,nlklkL1kkpp(单位元).Lepl证明 ，用所取元素的积及 作序列：,那么它的nP |enppppppeLL21211,项都是中的元素，根据抽屉原理，上述序列中必有两项相等.如果，1nPepppjL21此时，符合要求；否则有jlk , 1()，ljjjppppppppLLL121211 jl于是有，epppppppppjjljj )()(211 2121LLL取，有，使1 jknl 1.eppplkkL1 (二）抽屉原理在初等数学(竞赛题)中的应用初等数学问题的特点是：只涉及一些相关的条件，或者有时虽然给出一些数值条件，但也不能应用这些条件通过通常的数
