鸽笼原理毕业论文经典

材料清单一、毕业论文二、毕业设计任务书三、毕业设计开题申请表四、毕业设计开题报告正文声明本人丰海娟，学号10505039，系数学与应用数学学院数学与应用数学专业1001班学生。所做论文内容主体均为原创，无任何抄袭、剽窃他人劳动成果的行为。如有发现此类行为，本人愿意为此承担一切道义及法律责任，特此声明。学生签名：年月日抽屉原理及其应用姓名：专业：数学与应用数学学号：指导老师：摘要：抽屉原理是数学中的重要原理,在解决数学问题时有非常重要的作用.各种形式的抽屉原理在高等数学和初等数学中经常被采用.本文着重从抽屉的1构造方法：等分区间、分割图形、利用“对称性”、用整数性质、利用染色和根据问题的需要阐述抽屉原理在高等数学和初等数学（竞赛题）中的应用,同时指出了它在应用领域中的不足之处:抽屉的构造有一定的难度,这就要求我们必须要求有一定的数学功底,甚至复杂的需要大量的演算,因此抽屉原理不能充分的运用到我们日常生活中去.关键词：抽屉原理;高等数学;初等数学TheprincipleofdraweranditsapplicationAbstract：Drawerprincipleistheimportantprincipleofmathematicsinsolvingmathematicalproblems,hasaveryimportantrole.AllformsofdrawerprincipleinHigherMathematicsandelementarymathematicsisoftenused.Thisarticleemphaticallyfromthedrawerconstructionmethods:equalinterval,segmentationgraph,usingthesymmetry,withpropertiesoftheintegers,usingstainingandaccordingtoproblemsonthedrawerprincipleinHigherMathematicsandElementaryMathematics(contest)application,andpointsoutthatitisinthefieldofapplicationofthedeficiencies:drawerstructurehascertaindifficulty,thisaskswemusthavesomemathskills,evencomplexrequiresalargeamountofcalculation,thereforethedrawerprinciplecannotfulluseofourdailylife.KeyWords：theprincipleofdrawer;advancedmathematics;primarymathematics2目录1．抽屉原理……………………………………………………….....................11.1抽屉原理的简单形式……………………………………………………….............11.2抽屉原理的加强形式……………………………………………………….............22．抽屉原理的应用………………………………………………………...............42.1抽屉的构造……………………………………………………….....................42.2抽屉原理在数学解题中的应用………………………………………………….103.抽屉原理在生活中的应用………………………………………………………143.1月黑穿袜子………………………………………………………...................143.2手指纹和头发………………………………………………………...................143.3电脑算命………………………………………………………..........................154．总结………………………………………………………..........................15参考文献………………………………………………………..........................16致谢………………………………………………………................................17前言抽屉原理又叫做鸽巢原理，指的是一件简单明了的事实：为数众多的鸽子飞进为数不多的巢穴里，则至少有一个巢穴飞进了两只或者更多的鸽子。其实有关于抽屉原理（鸽巢原理）的阐释，粗略的说就3是如果有许多物体放进不足够多的盒子内，那么至少有一个盒子被两个或多个盒子占据。抽屉原理在我们日常生活中已经运用的比较广泛了,它往往和我们数学结合在一起为我们日常生活带来了不小的便利。我将主要叙述一下抽屉原理的具体的形式、构造方法以及他在我们生活中的一些具体的应用。希望大家能对抽屉原理有一个更加清晰的了解并能运用到我们的日常生活中去。1.1.抽屉原理的简单形式抽屉原理的最简单的形式如下．定理1．鸽巢原理(组合数学,)如果1n个物体放进n个盒子，那么至少有一个盒子包含两个或更多的物体．证明：（用反证法）如果n个盒子中每个盒子至多放一个物体，则放入n个盒子中的物体总数至多为n个．这与假设有1n个物体矛盾．从而定理得证．注意，无论是抽屉原理还是它的证明，对于找出含有两个或更多物体的盒子都没有任何帮助．我们只是简单断言，如果人们检查每一个盒子，那么他们会发现有的盒子，里面放有多于一个的物体．抽屉原理只是保证这样的盒子存在．因此，无论何时抽屉原理被用来证明一个排列或某种现象的存在性，除了考察所有的可能性外，它都不能对任何构造排列或寻找现象的例证给出任何指示．还要注意，抽屉原理的结论不能被推广到只存在n个（或更少）物体的情形．这是因为我们可以把不同的物体放到n个盒子的每一个中去．当然，在这些盒子中可以这样分发物体：一个盒子放入两个物体，但对任意分发这是没有保证的．抽屉原理只是断言，在n个盒子中去论如何分发1n个物体，总不能避免把两个物体放进同一个盒子中去．还存在一些与抽屉原理相关的其它原理，有必要正式叙述如下．(1)如果将n个物体放入n个盒子并且没有一个盒子是空的，那么每个盒子恰好包含一个物体．(2)如果将n个物体放入n个盒子并且没有盒子被放入多于一个的物体，那么每个盒子里有一个物体．现在把所阐明的这三个原理更抽象的表述为：令X和Y是两个有限集，并令:fXY是一个从X到Y得函数．4（1）如果X的元素多于Y的元素，那么f就不是一对一的．（2）如果X和Y含有相同个数的元素，并且f是映上的，那么f就是一对一的．（3）如果X和Y含有相同个数的元素，并且f是一对一的，那么f就是映上的．1.2.抽屉原理的加强形式下列定理包含定理2.作为它的特殊情形．定理2.鸽巢原理(组合数学)设12,,,nqqq为正整数．如果将121nqqqn个物体放入n个盒子内，那么，或者第一个盒子至少含有1q个物体，或者第二个盒子至少含有2q个物体，…，或者第n个盒子至少含有nq个物体．证明：设将121nqqqn个物体分放到n个盒子中．如果对于每个12,in，，，第i个盒子含有少于iq个物体，那么所有盒子中的物体总数不超过1212111nnqqqqqqn（）（）（）该数比所分发的物体总数少1，因此我们断言，对于某一个12,in，，，第i个盒子至少包含iq个物体．注意，能够将12nqqqn个物体用下面的方法分到n个盒子中，对所有的12,in，，第i个盒子都不能含有iq个或更多的物体，我们可以通过将11q个物体放入第一个盒子，将21q个物体放入第二个盒子等来实现，抽屉原理的简单形式是由其强化形式的通过使12...2nqqq得到的，由此有121211nqqqnnnn．在初等数学中抽屉原理的加强形式最常用于12,,,nqqq都等于同一个整数r的特殊情况．在这种情况下，该定理叙述如下：推论1．如果11nr个物体放入n个盒子中，那么至少有一5个盒子含有r个或更多的物体．等价的，推论2．如果n个非负整数12,,...,nmmm的平均数大于1r：12...1nmmmrn那么至少有一个整数大于或等于r．这两种表述之间的联系可以通过取11nr个物体并放入n个盒子中得到．对于12,in，，，令im是第i个盒子中的物体个数．于是这m个数12,,...,nmmm的平均数为12...(1)11(1)nmmmnrrnnn由于这个平均数大于1r，故而有一个整数im至少是r．换句话说，这些盒子中有一个盒子至少含有r个物体．推论3.如果n个非负整数12,,...,nmmm的平均数小于1r：12...1nmmmrn那么至少有一个整数小于1r．推论4．如果n个非负整数12,,...,nmmm的平均数至少等于r，那么这n个整数12,,...,nmmm至少有一个满足imr．推论5．m个物体放入n个盒子中，则至少有一个盒子中有不少于11mn个物体．注：符号x表示不超过实数x的最大整数．证明：（反证法）若不然，则每一个集合中最多有1mn个物体，这时，n个盒子中就最多有1mnn个物体．6因为11mmnn，所以111mmnnmmnn，这与已知条件m个物体放入n个盒子中矛盾，故上述推论成立．抽屉原理的形式比较多变，在具体的应用中也会有不同的变化，但本质上都是一样的．上述定理及推论的证明均采用反证法，这种证明方法对于证明元素个数多于抽屉个数的问题时有其普遍意义，平均重叠原则［３］：把一个量S任意分成n份，则其中至少有一份不大于Sn，也至少有一份不少于Sn．不等式重叠原则［３］：若,,,abcdR，且acbd，则ab，cd至少有一个成立．面积重叠原则［３］：在平面上有n个面积分别是1A，2A，…nA的图形，把这n个图形按任何方式一一搬到某一个面积为A的固定图形上去，（1）如果12...nAAAA，则至少有两个有公共点；（2）如果12...nAAAA，则固定图形中至少有一个点未被盖住．2．抽屉原理的应用应用抽屉原理的基本思想是根据不同问题自身特点，洞察问题本质，先弄清对哪些元素进行分类，再找出分类的规律，即所谓的构造抽屉，构造抽屉是应用抽屉原理的关键．在介绍抽屉原理的应用之前，本文先用几个具体的例子来介绍几种常用的构造抽屉的方法．2.1抽屉的构造．2.1.1等分区间制造抽屉当问题的结论与区间有关时，可等分某个区间，设计出若干个抽屉．例1［２］求证：对于任给的正无理数及任意大的自然数n，存在．．一个有理7数km，使得1kmmn．证明：把区间（0，1）进行n等分，得n个小区间1122310,,,,,,...,,1nnnnnnn．由抽屉原理知，这些区间内的1n个数中，必有两个数落在某一个区间，从而这两个数的差的绝对值小于1n．设(1,2,...,1)ipNin，则由是正无理数得01iipp所以这1n个数(1,2,...,1)iippin中，必有2个数，不妨设为11pp和22pp，它们的差的绝对值小于1n，即12121()()ppppn设1212,ppmppk，则1mkn，即1kmmn上述例子涉及区间问题，把区间（0，1）进行n等分，得n个小区间，自然就得到了n个抽屉，而1n个数可以作为1n个物体，此处可以利用抽屉原理解决问题．2.1.2分割图形构造抽屉在一个几何图形内有若干已知点，我们可以根据问题的要求把图形进行适当的分割，用这些分割成的图形作为抽屉，再对已知