抽屉原理及其应用数学毕业论文

北京航空航天大学软件学院组合数学论文论文题目抽屉原理及其应用姓名学号专业集成电路与物联网工程北航软件学院1目录摘要2ABSTRACT31引言42抽屉原理的形式43抽屉原理的构造531分割图形构造抽屉532利用划分数组来构造抽屉633利用划分集合来构造抽屉634利用等分区间构造抽屉735利用奇偶性分类构造抽屉836利用状态制构造抽屉84抽屉原理的应用941抽屉原理在数学中的应用9411解决代数问题9412解决数论问题10413解决几何问题1142抽屉原理在生活中的应用11421手指纹和头发11422电脑算命12423招生录取125总结13参考文献13北航软件学院2摘要抽屉原理是组合数学中研究存在性问题的基本原理之一,也是非常规解题方法的重要类型之一，在数论和组合论中有着广泛的应用。本文简单介绍了抽屉原理的几种形式，本文主要研究抽屉原理的抽屉构造和原理的应用。构造主要研究抽屉原理经常使用的几种构造方式分割图形构造法，整数性质构造法（同余类构造法、划分数组构造法），间接转换构造法（染色体构造法）。应用主要从数学领域的应用和现实生活中的应用两大方面进行研究，数学领域方面主要应用于代数、数论、几何等几方面的解题，现实生活中大多数用于电脑算命，预测某些存在性的结果等等。关键词抽屉原理；“抽屉”的构造；抽屉原理的应用北航软件学院3ABSTRACTDRAWERPRINCIPLEISAMATHEMATICALCOMBINATIONOFPROBLEMOFTHEEXISTENCEOFONEOFTHEBASICPRINCIPLESOFNONCONVENTIONALPROBLEMSOLVINGMETHOD,ISALSOONEOFTHEIMPORTANTTYPESINNUMBERTHEORYANDCOMBINATORICS,HASAWIDERANGEOFAPPLICATIONSTHISPAPERBRIEFLYINTRODUCESTHEPRINCIPLEOFDRAWERINSEVERALFORMS,THISPAPERMAINLYSTUDIESTHEPRINCIPLEOFDRAWERDRAWERSTRUCTUREANDTHEAPPLICATIONOFTHEPRINCIPLETECTONICRESEARCHDRAWERPRINCIPLEOFTENUSESEVERALCONSTRUCTIONMETHODSSEGMENTATIONGRAPHCONSTRUCTIONMETHOD,CONSTRUCTIONMETHODOFINTEGERPROPERTIESCONGRUENCECLASSCONSTRUCTIONMETHOD,CONSTRUCTIONMETHODOFDIVIDINGTHEARRAY,INDIRECTCONVERSIONMETHODOFCONSTRUCTIONCHROMOSOMECONSTRUCTIONMETHODAPPLICATIONMAINLYFROMTHEMATHEMATICALFIELDOFAPPLICATIONANDTHEREALITYOFLIFEINTHEAPPLICATIONOFTHETWOMAJORASPECTSOFRESEARCH,MATHEMATICALFIELDSMAINLYUSEDINNUMBERTHEORY,ALGEBRA,GEOMETRYANDSOONSEVERALASPECTSOFTHEPROBLEMSOLVING,INREALLIFE,MOSTUSEDCOMPUTERFORTUNETELLING,PREDICTSOMEEXISTENCERESULTSETCKEYWORDSDRAWERPRINCIPLE；“DRAWER“TECTONICDRAWER；PRINCIPLEAPPLICATION北航软件学院41引言抽屉原理又称鸽巢原理、鞋箱原理或重叠原理，抽屉原理是离散数学中的一个重要原理，它是由德国著名数学家狄利克雷PGTDIRICHLET18051855首先发现的，因此也叫作狄利克雷原理。抽屉原理简单易懂，主要用于证明某些存在性或必然性的问题，不仅在数论、组合论以及集合论等领域中有着广泛应用，在高等数学的其它几门学科领域中也是解决问题的有效方法。本文将抽屉原理的解题思路拓展到高等数学的其他领域，有助于更好地理解抽屉原理，并举例阐述了抽屉原理在现实生活中的应用。2抽屉原理的形式什么是抽屉原理先举个简单的例子说明，就是将3个球放入2个篮子里，无论怎么放，必有一个篮子中至少要放入2个球，这就是抽屉原理或者假定一群鸽子飞回巢中，如果鸽子的数目比鸽巢多，那么一定至少有一个鸽笼里有两只或两只以上的鸽子，这也是鸽巢原理这一名称的得来。抽屉原理简单直观，很容易理解。而这个看似简单的原理在高等数学中有着很大的用处，对于数论、离散数学、高等代数以及抽象代数中的一些复杂问题，可以利用抽屉原理巧妙的解答出来。下面首先从抽屉原理的形式入手，然后再研究它在高等数学中的应用。我们最常用的抽屉原理只是抽屉原理的简单形式，就是将N1个元素或者更多的元素放入N个抽屉中，则至少有一个抽屉里放有两个或两个以上的元素。除了这种比较普遍的形式外，抽屉原理还经许多学者推广出其他的形式。陈景林、阎满富在他们编著的组合数学与图论一书中将抽屉原理抽象概括成以下三种形式1原理1把多于个的元素按任一确定的方式分成个集合，则一定有一个NN集合中含有两个或两个以上的元素。原理2把个元素任意放到个集合里，则至少有一个集合里至MNM少有个元素，其中K1KNMN,当能整除时,当不能整除时北航软件学院5原理3把无穷个元素按任一确定的方式分成有限个集合，则至少有一个集合中仍含无穷个元素。卢开澄在组合数学（第三版）中将抽屉原理（书中称为鸽巢原理）又进行了推广2。鸽巢原理设K和N都是任意正整数，若至少有KN1只鸽子分配在N个鸽巢中，则至少存在一个鸽巢中有至少K1只鸽子。推论1有M只鸽子和N个鸽巢，则至少有一个鸽巢中有不少于1只NM1鸽子。推论2若将NM11个球放入N个盒子里，则至少有一个盒子有M个球。推论3若是N个正整数，而且R，则12,12NM中至少有一个数不小于R。12,NM另外，抽屉原理还可以用映射的形式来表示，即设和是两个有限集，AB如果，那么对从到的任何满射，至少存在,使ABABF1A2。12FAF3抽屉原理的构造通过了解抽屉原理的形式，我们可以利用它的特殊形式来解决不同的问题。首先，必须明确题目中应该以什么为抽屉，什么为物品。其次，构造合适的抽屉，需要注意的是抽屉的数量一定要少于物品的数量。最后，运用抽屉原理解决问题。其中，最重要最有难度的就是如何构造抽屉，构造抽屉是运用抽屉原理解题的关键，下面介绍几种常用的构造抽屉的方法。31分割图形构造抽屉在一个几何图形内有若干已知点，我们可以根据问题的要求把图形进行适当的分割，用这些分割成的图形作为抽屉，再对已知点进行分类，集中对某一北航软件学院6个或几个抽屉进行进行讨论，使问题得到解决。例1在边长为2米的正方形内，任意放入13个点求证必有4个点，以它们为顶点的四边形的面积不超过1平方米。12证明把边长为2米的正方形分割成面积为1平方米的4个小正方形，如图1因为13341，所以由抽屉原理知，至少有4个点落在同一个面积为1平方米的小正方形内（或边上），以这4个点为顶点的四边形的面积总小于或等于小正方形的面积，即以这4个点为顶点的四边形的面积不超过1平方米。32利用划分数组来构造抽屉利用此方法解题的关键是要明确分组的“对象”,然后将这些对象分成适当的数组,再应用抽屉原理,问题便得以解决。例2任意给定7个不同的整数,求证其中必有两数之和或差是10的倍数。证明设这7个不同的整数分别为,它们分别除以10后,得到的余721,TT数是从0到9中的一个数。1若这7个余数中有两个数相同设,为整数、QPKTKPTJI10,则即存在两数之差是的倍数。的倍数，是即0,1JIJITQPT2若这7个余数中任何两个都不同,由抽屉原理知,至少有一数被10除余数为6、7、8、9四个数中的一个。将余数为6的数与余数为4的数划为一组,余数为7的数与余数为3的数划为一组,余数为8的数与余数为2的数划为一组,余数为9的数与余数为1的数划为一组。于是便有,这7个不同的余数,除0,5外,其余的必有一组数它们做和是10的倍数。北航软件学院733利用划分集合来构造抽屉例3在1,4,7,10,13，100中任选出20个数，其中至少有不同两组数，其和都等于104，试证明之。证明给定的数共有34个，其相邻两数的差均为3，我们把这些数分成如下18个不相交的集合且把它们看作是1524,07,94,5，个抽屉，从已知的34个数中任选个数，即使把前两个抽屉中的数1和5218都取出，则剩下的个数在后面的个抽屉中至少有不同的两个抽屉中的数全86部被取出，这两个抽屉中的数互不相同，每个抽屉中的两个数的和都是104。34利用等分区间构造抽屉所谓等分区间简单的说即是如果在长度为1的区间内有多于个的点，N可考虑把区间等分成个子区间，这样由抽屉原理可知，一定有两点落在同N一子区间，它们之间的距离不大于这种构造法常用于处理一些不等式的证明。N1例4已知11个数,全满足,证明必有两121,X12,0IXI个满足。JIX,JIX0证明如图1，将实数轴上介于0与1那段连同端点等分为10小段这10个小段也就是10个等分区间，即10个抽屉，每一小段长为由抽屉原理，1011个点数中至少有12个点落在同一条小线段上，这两点相应的数之10差的绝对值。图1例5任给7个实数，证明必存在两个实数满足01A,B3BA证明设七个实数为，作,显然7321,AIQIRCTG7,21，把等分成六个区间，IQ2,2601北航软件学院8，由抽屉原理，必有两个属0,6,3,62,721,Q于同一区间，不妨设为,而不论属于哪个小区间都有IQJIJQ,，由正切函数的单调性可知，60JIQ3160TGTGJI不妨记，则,而由知0，又JITGBTA,JITAB1AB因为有,1,从而有01。0JIQAB3对于给定了一定的长度或区间并要证明不等式的问题，我们常常采用等分区间的构造方法来构造抽屉，正如上面的两个例子，在等分区间的基础上我们便很方便的构造了抽屉，从而寻找到了证明不等式的一种非常特殊而又简易的方法，与通常的不等式的证明方法构造函数法，移位相减法相比，等分区间构造抽屉更简易，更容易被人接受。35利用奇偶性分类构造抽屉例6平面上至少应给出几个格点也称整点，即横坐标、纵坐标都是整数的点，才能使得其中至少有两个点的连线的中点仍是一格点。证明设两个格点的坐标为,则连线的中点坐标1X,Y2,21X,。易见，为保证中点坐标为整数，当且仅当与,与同奇偶；21Y1X21Y2因此，可按奇偶性将所有格点的坐标分类，共有奇,奇，奇,偶，偶,奇，偶,偶四种情况，把这四种情况看作抽屉，由抽屉原理，至少应给出5个格点，才能保证至少有两点属于同一类，从而才有两点连线的中点是格点结果是显然的，证明从略。36利用状态制构造抽屉例7设有六点，任意三点不共线，四点不共面，如果把这六个点两两用直线联系起来，并把这些直线涂以红色或者蓝色求证不论如何涂色，总可以找到三点，做成以它们为顶点的三角形，而这三角形三边涂有相同的颜色。北航软件学院9分析设已知六点为由于任三点不共线，所以任三点均,654321AA可作为某三角形的三个顶点。证明从六个点中任取一点，将与其余五点相连得到五条线段，线段11如下所示这五条线段只有两种颜色即红色或者蓝,6541321色，由抽屉原理知，至少有三条涂有同一种颜色颜色为抽屉，线段为元素，不妨设涂有红色，这时我们考察。,41321A432A1若中有一条红色边，如，则为三边同红的三角321形。2若中无一条红色边，则就是三边均为蓝色的三角形432432抽屉构造之巧妙，常令人惊叹不已，拍案叫绝，抽屉的构造方法也不胜枚举，在这里我们旨在做到举一反三抽屉原理是组合数学中貌似平凡却透着不平凡应用定理之一，是RAMSEY定理的基础，下面我们就来探讨抽屉原理在高等数学和初等数学竞赛题中的应用。4抽屉原理的应用41抽屉原理在数学中的应用接下来，在了解了抽屉原理的基本形式以及多位学者所发展的推广形式的基础上，我们通过一些比较典型的实例来说明抽屉原理在高等数学中代数、数论、几何这三个方面的应用。411解决代数问题用集合的语言抽屉原理可以叙述如下（1）设个元素按任意确定方式分成有限个集合，那么至少有一个集合含N有两个元素。（2）设有无穷多个元素按任意确定方式分成有限个集合，那么至少有一个集合含有无穷多个元素。例1证明有限群中的每个元素的阶均有限。证明设G为阶有限群，任取AG，则由抽屉原理可知N中必有相等的不妨设于是有231,AA,11STASN北航软件学院10，从而A的阶有限。STAE例2设A为阶方阵，证明存在N11,AKKKN使秩（）秩（）证明因为阶方阵的秩只能是这个数之一，而01,23N，的个数大于秩，从而，由抽屉原理知在0121,NAA中，存在满足,KL使1LN秩（）秩（）KAL但秩（）秩（）秩（）K1LA所以秩（）秩（），得证KK412解决数论问题在初等数论中，很多问题都可以看作存在性问题，所以可以考虑利用抽屉原理进行解决。例3令和为两个互素的正整数，并令和为整数，且MNAB以及，则存在一个正整数，使得除以的余01A01BXM数是，并且除以的余数为，即可以写成的同时又可以XXP写成的形式，这里和是整数。QNPQ证明为了证明这个结论考虑个整数，N,2,1AMANA，这些整数中的每一个除以都余设其中的两个除以有相同的余数令MR这两个数为和，其中因此，存在两整数和，IAJ01IJIQJ使得及，这两个方程相减可得。IIMQNRJQNRJIJMN于是是的一个因子由于和没有除1之外的公因子，因此JIM是的因子然而，意味着，也就是说不可NJI01IJN0JINN北航软件学院11能是的因子该矛盾产生于我们的假设个整数JIN,2,1AMAMA，中的两个除以有相同的余数因此这个数中的每一个数除以N都有不同的N余数根据抽屉原理，个数中的每一个作为余数都要出现，特别01N，地，数也是如此令为整数，满足，且使数，除以BP1PXPA余数为则对于某个适当的，有。NQXB因此且，从而具有所要求的性质。XMAXNB413解决几何问题抽屉原理在几何问题中可以变形如下如果长度为的线段上放置若干条A长度大于之和大于的线段，则放置的线段中必有公共点。A例4在边长为1的正方形内部，放置若干个圆，这些圆的周长之和等于10证明可以作出一条直线，至少与其中四个圆有交点。证明将所有的已知圆投影到正方形的一条边AB上注意，周长为的圆L周，其投影长为的线段因此所有已知圆的投影长度之和等于，由于L10，所以由抽屉原理知，线段AB上必有一点X，至少被四条投影线103AB段所覆盖即至少有四条投影线段有公共点因此，过点X且垂直于AB的直线，至少与四个已知圆有交点。42抽屉原理在生活中的应用抽屉原理在日常生活中的应用其实也非常广泛，比如前面提到的例5，再如一组多余366个人中一定有2个人的生日相同，80个人中至少有7个人生在同一个月等等，这样的例子很多，下面介绍几个有意思的例子。421手指纹和头发据说世界上没有两个人的手指纹是一样的，因此警方在处理犯罪问题时很北航软件学院12重视手指纹，希望通过手指纹来破案或检定犯人可是在13亿中国人当中，最少有两个人头发是一样多的。这是因为，人的头发数目是不会超过13亿这么大的数目，假定人最多有N根头发现在我们编上号码其中表示由根头发的那些1234,NAIAI人现在假定每个都有一个人，那么还剩下“13亿减N”个人，这数目不会I等于零，我们现在随便挑一个放进和他头发相同的小组就行，他就会在里面遇到和他有相同头发数目的人了。422电脑算命“电脑算命”看起来挺玄乎，只要你报出自己出生的年、月、日和性别一按按键，屏幕上就会出现所谓性格、命运的句子，据说这就是你的“命”这是科学的吗如果以70年算，按出生的年、月、日、性别的不同组合数应为，我们把它作为抽屉数我国现有人口13亿，我们把它作70365210为物体由于，由抽屉原理，存在25441个以上的人，931254尽管他们的出身、经历、天资、机遇各不相同，但他们却有完全相同的“命”，这真是荒谬绝伦。所谓“电脑算命”不过是把人为编好的算命语句像中药柜那样事先分别一一存放在各自的柜子里，谁要算命，即根据出生的年、月、日、性别的不同的组合按不同的编码机械地到电脑上的各个“柜子”里取出所谓命运的句子其实这充其量不过是一种电脑游戏而已。抽屉原理应用其实非常广泛，除了之前介绍的几个例子之外，抽屉原理在计算机上也有一定的应用，由于涉及一些计算机专业问题，本文不再详细介绍。423招生录取其实，抽屉原理不仅在数学中有用，在现实生活中也到处在起作用，如招北航软件学