抽屉原理及其应用数学毕业设计

北航软件学院北京航空航天大学软件学院组合数学论文论文题目：抽屉原理及其应用姓名：学号：专业：集成电路与物联网工程目录摘要 2Abstract 31.引言 42.抽屉原理的形式 43.抽屉原理的构造 53.1分割图形构造抽屉 53.2利用划分数组来构造抽屉 63.3利用划分集合来构造抽屉 63.4利用等分区间构造抽屉 73.5利用奇偶性分类构造抽屉 83.6利用状态制构造抽屉 84.抽屉原理的应用 94.1抽屉原理在数学中的应用 94.1.1解决代数问题 94.1.2解决数论问题 104.1.3解决几何问题 114.2抽屉原理在生活中的应用 114.2.1手指纹和头发 114.2.2电脑算命 124.2.3招生录取 125.总结 13参考文献 13摘要抽屉原理是组合数学中研究存在性问题的基本原理之一,也是非常规解题方法的重要类型之一，在数论和组合论中有着广泛的应用。本文简单介绍了抽屉原理的几种形式，本文主要研究抽屉原理的抽屉构造和原理的应用。构造主要研究抽屉原理经常使用的几种构造方式：分割图形构造法，整数性质构造法（同余类构造法、划分数组构造法），间接转换构造法（染色体构造法）。应用主要从数学领域的应用和现实生活中的应用两大方面进行研究，数学领域方面主要应用于代数、数论、几何等几方面的解题，现实生活中大多数用于电脑算命，预测某些存在性的结果等等。关键词：抽屉原理；“抽屉”的构造；抽屉原理的应用

AbstractDrawerprincipleisamathematicalcombinationofproblemoftheexistenceofoneofthebasicprinciplesofnonconventionalproblemsolvingmethod,isalsooneoftheimportanttypesinnumbertheoryandcombinatorics,hasawiderangeofapplications.Thispaperbrieflyintroducestheprincipleofdrawerinseveralforms,Thispapermainlystudiestheprincipleofdrawerdrawerstructureandtheapplicationoftheprinciple.Tectonicresearchdrawerprincipleoftenuseseveralconstructionmethods:segmentationgraphconstructionmethod,constructionmethodofintegerproperties(congruenceclassconstructionmethod,constructionmethodofdividingthearray),indirectconversionmethodofconstruction(chromosomeconstructionmethod).Applicationmainlyfromthemathematicalfieldofapplicationandtherealityoflifeintheapplicationofthetwomajoraspectsofresearch,mathematicalfieldsmainlyusedinnumbertheory,algebra,geometryandsoonseveralaspectsoftheproblemsolving,inreallife,mostusedcomputerfortune-telling,predictsomeexistenceresultsetc.Keywords：DrawerPrinciple；"drawer"tectonicdrawer；principleapplication

1.引言抽屉原理又称鸽巢原理、鞋箱原理或重叠原理，抽屉原理是离散数学中的一个重要原理，它是由德国著名数学家狄利克雷(P.G.T.Dirichlet1805-1855)首先发现的，因此也叫作狄利克雷原理。抽屉原理简单易懂，主要用于证明某些存在性或必然性的问题，不仅在数论、组合论以及集合论等领域中有着广泛应用，在高等数学的其它几门学科领域中也是解决问题的有效方法。本文将抽屉原理的解题思路拓展到高等数学的其他领域，有助于更好地理解抽屉原理，并举例阐述了抽屉原理在现实生活中的应用。2.抽屉原理的形式什么是抽屉原理？先举个简单的例子说明，就是将3个球放入2个篮子里，无论怎么放，必有一个篮子中至少要放入2个球，这就是抽屉原理.或者假定一群鸽子飞回巢中，如果鸽子的数目比鸽巢多，那么一定至少有一个鸽笼里有两只或两只以上的鸽子，这也是鸽巢原理这一名称的得来。抽屉原理简单直观，很容易理解。而这个看似简单的原理在高等数学中有着很大的用处，对于数论、离散数学、高等代数以及抽象代数中的一些复杂问题，可以利用抽屉原理巧妙的解答出来。下面首先从抽屉原理的形式入手，然后再研究它在高等数学中的应用。我们最常用的抽屉原理只是抽屉原理的简单形式，就是将n+1个元素或者更多的元素放入n个抽屉中，则至少有一个抽屉里放有两个或两个以上的元素。除了这种比较普遍的形式外，抽屉原理还经许多学者推广出其他的形式。陈景林、阎满富在他们编著的《组合数学与图论》一书中将抽屉原理抽象概括成以下三种形式[1]:原理1.把多于个的元素按任一确定的方式分成个集合，则一定有一个集合中含有两个或两个以上的元素。原理2.把个元素任意放到个集合里，则至少有一个集合里至少有个元素，其中原理3.把无穷个元素按任一确定的方式分成有限个集合，则至少有一个集合中仍含无穷个元素。卢开澄在《组合数学》（第三版）中将抽屉原理（书中称为鸽巢原理）又进行了推广[2]。鸽巢原理：设k和n都是任意正整数，若至少有kn+1只鸽子分配在n个鸽巢中，则至少存在一个鸽巢中有至少k+1只鸽子。推论1.有m只鸽子和n个鸽巢，则至少有一个鸽巢中有不少于+1只鸽子。推论2.若将n(m-1)+1个球放入n个盒子里，则至少有一个盒子有m个球。推论3.若是n个正整数，而且r=，则中至少有一个数不小于r。另外，抽屉原理还可以用映射的形式来表示，即:设和是两个有限集，如果>，那么对从到的任何满射，至少存在,,使。3.抽屉原理的构造通过了解抽屉原理的形式，我们可以利用它的特殊形式来解决不同的问题。首先，必须明确题目中应该以什么为抽屉，什么为物品。其次，构造合适的抽屉，需要注意的是抽屉的数量一定要少于物品的数量。最后，运用抽屉原理解决问题。其中，最重要最有难度的就是如何构造抽屉，构造抽屉是运用抽屉原理解题的关键，下面介绍几种常用的构造抽屉的方法。3.1分割图形构造抽屉在一个几何图形内有若干已知点，我们可以根据问题的要求把图形进行适当的分割，用这些分割成的图形作为抽屉，再对已知点进行分类，集中对某一个或几个抽屉进行进行讨论，使问题得到解决。例1：在边长为2米的正方形内，任意放入13个点．求证：必有4个点，以它们为顶点的四边形的面积不超过1平方米。(1)(2)证明：把边长为2米的正方形分割成面积为1平方米的4个小正方形，如图1．因为13=3×4+1，所以由抽屉原理知，至少有4个点落在同一个面积为1平方米的小正方形内（或边上），以这4个点为顶点的四边形的面积总小于或等于小正方形的面积，即以这4个点为顶点的四边形的面积不超过1平方米。3.2利用划分数组来构造抽屉利用此方法解题的关键是要明确分组的“对象”,然后将这些对象分成适当的数组,再应用抽屉原理,问题便得以解决。例2：任意给定7个不同的整数,求证:其中必有两数之和或差是10的倍数。证明：设这7个不同的整数分别为,它们分别除以10后,得到的余数是从0到9中的一个数。(1)若这7个余数中有两个数相同:设,则即存在两数之差是的倍数。(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个数，其中至少有不同两组数，其和都等于104，试证明之。证明给定的数共有34个，其相邻两数的差均为3，我们把这些数分成如下18个不相交的集合且把它们看作是个抽屉，从已知的34个数中任选个数，即使把前两个抽屉中的数1和52都取出，则剩下的个数在后面的个抽屉中至少有不同的两个抽屉中的数全部被取出，这两个抽屉中的数互不相同，每个抽屉中的两个数的和都是104。3.4利用等分区间构造抽屉所谓等分区间简单的说即是：如果在长度为1的区间内有多于个的点，可考虑把区间等分成个子区间，这样由抽屉原理可知，一定有两点落在同一子区间，它们之间的距离不大于.这种构造法常用于处理一些不等式的证明。例4：已知11个数,全满足,证明必有两个()满足。证明如图1，将实数轴上介于0与1那段(连同端点)等分为10小段(这10个小段也就是10个等分区间，即10个抽屉)，每一小段长为.由抽屉原理，11个点(数)中至少有+1=2个点落在同一条小线段上，这两点相应的数之差的绝对值。001图1例5：任给7个实数，证明必存在两个实数满足01+.证明设七个实数为，作=(),显然∈()，把()等分成六个区间：()，()，()，()，()，()，由抽屉原理，必有两个属于同一区间，不妨设为,而不论属于哪个小区间都有，由正切函数的单调性可知，，不妨记，则=,而由知0，又因为有(),1+,从而有01+。对于给定了一定的长度或区间并要证明不等式的问题，我们常常采用等分区间的构造方法来构造抽屉，正如上面的两个例子，在等分区间的基础上我们便很方便的构造了抽屉，从而寻找到了证明不等式的一种非常特殊而又简易的方法，与通常的不等式的证明方法(构造函数法，移位相减法)相比，等分区间构造抽屉更简易，更容易被人接受。3.5利用奇偶性分类构造抽屉例6：平面上至少应给出几个格点(也称整点，即横坐标、纵坐标都是整数的点)，才能使得其中至少有两个点的连线的中点仍是一格点。证明设两个格点的坐标为(),(),则连线的中点坐标()。易见，为保证中点坐标为整数，当且仅当与,与同奇偶；因此，可按奇偶性将所有格点的坐标分类，共有(奇,奇)，(奇,偶)，(偶,奇)，(偶,偶)四种情况，把这四种情况看作抽屉，由抽屉原理，至少应给出5个格点，才能保证至少有两点属于同一类，从而才有两点连线的中点是格点(结果是显然的，证明从略)。3.6利用状态制构造抽屉例7：设有六点，任意三点不共线，四点不共面，如果把这六个点两两用直线联系起来，并把这些直线涂以红色或者蓝色.求证：不论如何涂色，总可以找到三点，做成以它们为顶点的三角形，而这三角形三边涂有相同的颜色。分析设已知六点为由于任三点不共线，所以任三点均可作为某三角形的三个顶点。证明从六个点中任取一点，将与其余五点相连得到五条线段，线段如下所示：这五条线段只有两种颜色即红色或者蓝色，由抽屉原理知，至少有三条涂有同一种颜色.(颜色为抽屉，线段为元素)，不妨设涂有红色，这时我们考察△。(1)若△中有一条红色边，如，则△为三边同红的三角形。(2)若△中无一条红色边，则△就是三边均为蓝色的三角形.抽屉构造之巧妙，常令人惊叹不已，拍案叫绝，抽屉的构造方法也不胜枚举，在这里我们旨在做到举一反三.抽屉原理是组合数学中貌似平凡却透着不平凡应用定理之一，是Ramsey定理的基础，下面我们就来探讨抽屉原理在高等数学和初等数学(竞赛题)中的应用。4.抽屉原理的应用4.1抽屉原理在数学中的应用接下来，在了解了抽屉原理的基本形式以及多位学者所发展的推广形式的基础上，我们通过一些比较典型的实例来说明抽屉原理在高等数学中代数、数论、几何这三个方面的应用。4.1.1解决代数问题用集合的语言抽屉原理可以叙述如下：（1）设个元素按任意确定方式分成有限个集合，那么至少有一个集合含有两个元素。（2）设有无穷多个元素按任意确定方式分成有限个集合，那么至少有一个集合含有无穷多个元素。例1证明:有限群中的每个元素的阶均有限。证明：设G为阶有限群，任取a∈G，则由抽屉原理可知中必有相等的．不妨设于是有，从而a的阶有限。例2：设A为阶方阵，证明：存在证明：因为阶方阵的秩只能是这个数之一，而的个数大于秩，从而，由抽屉原理知在中，存在满足使秩（）=秩（）但秩（）秩（）…秩（）所以秩（）=秩（），得证4.1.2解决数论问题在初等数论中，很多问题都可以看作存在性问题，所以可以考虑利用抽屉原理进行解决。例3：令和为两个互素的正整数，并令和为整数，且以及，则存在一个正整数，使得除以的余数是，并且除以的余数为，即可以写成的同时又可以写成的形式，这里和是整数。证明：为了证明这个结论考虑个整数，这些整数中的每一个除以都余．设其中的两个除以有相同的余数．令这两个数为和，其中．因此，存在两整数和，使得及，这两个方程相减可得。于是是的一个因子．由于和没有除1之外的公因子，因此是的因子．然而，意味着，也就是说不可能是的因子．该矛盾产生于我们的假设：个整数中的两个除以有相同的余数．因此这个数中的每一个数除以n都有不同的余数．根据抽屉原理，个数中的每一个作为余数都要出现，特别地，数也是如此．令为整数，满足，且使数，除以余数为．则对于某个适当的，有。因此且，从而具有所要求的性质。4.1.3解决几何问题抽屉原理在几何问题中可以变形如下：如果长度为的线段上放置若干条长度大于之和大于的线段，则放置的线段中必有公共点。例4在边长为1的正方形内部，放置若干个圆，这些圆的周长之和等于10．证明：可以作出一条直线，至少与其中四个圆有交点。证明：将所有的已知圆投影到正方形的一条边AB上．注意，周长为的圆周，其投影长为的线段．因此所有已知圆的投影长度之和等于，由于，所以由抽屉原理知，线段AB上必有一点X，至少被四条投影线段所覆盖．即至少有四条投影线段有公共点．因此，过点X且垂直于AB的直线，至少与四个已知圆有交点。4.2抽屉原理在生活中的应用抽屉原理在日常生活中的应用其实也非常广泛，比如前面提到的例5，再如一组多余366个人中一定有2个人的生日相同，80个人中至少有7个人生在同一个月等等，这样的例子很多，下面介绍几个有意思的例子。4.2.1手指纹和头发据说世界上没有两个人的手指纹是一样的，因此警方在处理犯罪问题时很重视手指纹，希望通过手指纹来破案或检定犯人．可是在13亿中国人当中，最少有两个人头发是一样多的。这是因为，人的头发数目是不会超过13亿这么大的数目，假定人最多有N根头发．现在我们编上号码．其中表示由根头发的那些人．现在假定每个都有一个人，那么还剩下“13亿减N”个人，这数目不会等于零，我们现在随便挑一个放进和他头发相同的小组就行，他就会在里面遇到和他有相同头发数目的人了。4.2.2电脑算命“电脑算命”看起来挺玄乎，只要你报出自己出生的年、月、日和性别．一按按键，屏幕上就会出现所谓性格、命运的句子，据说这就是你的“命”．这是科学的吗？如果以70年算，按出生的年、月、日、性别的不同组合数应为，我们把它作为抽屉数．我国现有人口13亿，我们把它作为物体．由于，由抽屉原理，存在25441个以上的人，尽管他们的出身、经历、天资、机遇各不相同，但他们却有完全相同的“命”，这真是荒谬绝伦。所谓“电脑算命”不过是把人为编好的算命语句像中药柜那样事先分别一一存放在各自的柜子里，谁要算命，即根据出生的年、月、日、性别的不同的组合按不同的编码机械地到电脑上的各个“柜子”里取出所谓命运的句子．其实这充其量不过是一种电脑游戏而已。抽屉原理应用其实非常广泛，除了之前介绍的几个例子之外，抽屉原理在计算机上也有一定的应用，由于涉及一些计算机专业问题，本文不再详细介绍。4.2.3招生录取其实，抽屉原理不仅在数学中有用，在现实生活中也到处在起作用，如招生录取、就业安排、资源分配、职称评定等等，都不难看到抽屉原理的作用。下面简单的举几个例子：370个同学中必有至少2个人的生日是同一天；4双不同颜色的筷子中必须取出5枝筷子才能保证其中至少有一双筷子是同颜色的；13个人中必有两个人的生肖是一样的等等。5.总结抽屉原理叙述起来比较简单，因此本文将重点放在了抽屉原理的应用，尤其是构造抽屉的几种方法，这是灵活应用抽屉原理的关键．从上面的例子中，我们可以看到应用抽屉原理时一般分为三个步骤：构成分类的对象有个元素；找出分类的规则，将个元素分成个抽屉，并证明每个抽屉中的元素符合题意；应用抽屉原理证明结论成立．应用抽屉原理解题要注意以下几点：(1)题目中给出的元素(物品)具有任意性，分类也是任意的，所以不能用元素的一种特殊布局来代替元素的任意放置．(2)题目中给出的元素可能是实物，也可能是数、图形、符号、方式或方法等，构造抽屉，就是对这些元素有目的地进行分类、分组、分割等．(3)用抽屉原理解决的只是存在性问题，至于存在地点、存在多少，这都无关紧要．(4)应用抽屉原理解题的关键在于构造抽屉．因为只有把抽屉确定了，才能明确元素的放置情况，从而才能进行应有的讨论．构造抽屉主要依赖于自身的经验和技巧，充分体现了个人解题思维的灵活性。参考文献[1]曹汝成著.组合数学[M].华南理工大学出版社,2003:175[2]陈传理，张同君.竞赛数学教程（第二版）[M].高等教育出版社,2004[3]许胤龙，孙淑玲著.组合数学引论[M].第二版北京:中国科技大学出版社,2010:9[4]吕松涛．抽屉原理在数学解题中的应用[J].商丘职业技术学院报.2010.25[5]卢开澄,卢华明.组合数学(第三版)[M].北京:清华大学出版社,2002[6]王向东,周士藩等.高等代数常用方法[M].1989(11)[7]陈景林.抽屉原理及其应用[J].唐山师专学报,1999(9)[8]潘可为.抽屉原理及其应用[J].湖州师专学报,1993(5)基于C8051F单片机直流电动机反馈控制系统的设计与研究基于单片机的嵌入式Web服务器的研究MOTOROLA单片机MC68HC（8）05PV8/A内嵌EEPROM的工艺和制程方法及对良率的影响研究基于模糊控制的电阻钎焊单片机温度控制系统的研制基于MCS-51系列单片机的通用控制模块的研究基于单片机实现的供暖系统最佳启停自校正（STR）调节器单片机控制的二级倒立摆系统的研究基于增强型51系列单片机的TCP/IP协议栈的实现基于单片机的蓄电池自动监测系统基于32位嵌入式单片机系统的图像采集与处理技术的研究基于单片机的作物营养诊断专家系统的研究基于单片机的交流伺服电机运动控制系统研究与开发基于单片机的泵管内壁硬度测试仪的研制基于单片机的自动找平控制系统研究基于C8051F040单片机的嵌入式系统开发基于单片机的液压动力系统状态监测仪开发模糊Smith智能控制方法的研究及其单片机实现一种基于单片机的轴快流CO〈,2〉激光器的手持控制面板的研制基于双单片机冲床数控系统的研究基于CYGNAL单片机的在线间歇式浊度仪的研制基于单片机的喷油泵试验台控制器的研制基于单片机的软起动器的研究和设计基于单片机控制的高速快走丝电火花线切割机床短循环走丝方式研究基于单片机的机电产品控制系统开发基于PIC单片机的智能手机充电器基于单片机的实时内核设计及其应用研究基于单片机的远程抄表系统的设计与研究基于单片机的烟气二氧化硫浓度检测仪的研制基于微型光谱仪的单片机系统单片机系统软件构件开发的技术研究基于单片机的液体点滴速度自动检测仪的研制基于单片机系统的多功能温度测量仪的研制基于PIC单片机的电能采集终端的设计和应用基于单片机的光纤光栅解调仪的研制气压式线性摩擦焊机单片机控制系统的研制基于单片机的数字磁通门传感器基于单片机的旋转变压器-数字转换器的研究基于单片机的光纤Bragg光栅解调系统的研究单片机控制的便携式多功能乳腺治疗仪的研制基于C8051F020单片机的多生理信号检测仪基于单片机的电机运动控制系统设计Pico专用单片机核的可测性设计研究基于MCS-51单片机的热量计基于双单片机的智能遥测微型气象站MCS-51单片机构建机器人的实践研究基于单片机的轮轨力检测基于单片机的GPS定位仪的研究与实现基于单片机的电液伺服控制系统用于单片机系统的MMC卡文件系统研制基于单片机的时控和计数系统性能优化的研究基于单片机和CPLD的粗光栅位移测量系统研究单片机控制的后备式方波UPS提升高职学生单片机应用能力的探究基于单片机控制的自动低频减载装置研究基于单片机控制的水下焊接电源的研究基于单片机的多通道数据采集系统基于uPSD3234单片机的氚表面污染测量仪的研制基于单片机的红外测油仪的研究96系列单片机仿真器研究与设计基于单片机的单晶金刚石刀具刃磨设备的数控改造基于单片机的温度智能控制系统的设计与实现基于MSP430单片机的电梯门机控制器的研制基于单片机的气体测漏仪的研究基于三菱M16C/6N系列单片机的CAN/USB协议转换器基于单片机和DSP的变压器油色谱在线监测技术研究基于单片机的膛壁温度报警系统设计基于AVR单片机的低压无功补偿控制器的设计基于单片机船舶电力推进电机监测系统基于单片机网络的振动信号的采集系统基于单片机的大容量数据存储技术的应用研究基于单片机的叠图机研究与教学方法实践基于单片机嵌入式Web服务器技术的研究及实现基于AT89S52单片机的通用数据采集系统基于单片机的多道脉冲幅度分析仪研究机器人旋转电弧传感角焊缝跟踪单片机控制系统基于单片机的控制系统在PLC虚拟教学实验中的应用研究基于单片机系统的网络通信研究与应用基于PIC16F877单片机的莫尔斯码自动译码系统设计与研究基于单片机的模糊控制器在工业电阻炉上的应用研究基于双单片机冲床数控系统的研究与开发基于Cygnal单片机的μC/OS-Ⅱ的研究基于单片机的一体化智能差示扫描量热仪系统研究基于TCP/IP协议的单片机与Internet互联的研究与实现变频调速液压电梯单片机控制器的研究基于单片机γ-免疫计数器自动换样功能的研究与实现基于单片机的倒立摆控制系统设计与实现单片机嵌入式以太网防盗报警系统基于51单片机的嵌入式Internet系统的设计与实现单片机监测系统在挤压机上的应用MSP430单片机在智能水表系统上的研究与应用基于单片机的嵌入式系统中TCP/IP协议栈的实现与应用单片机在高楼恒压供水系统中的应用HYPERLINK"/detail.htm?