大学数学本科毕业论文--抽屉原理

本科毕业论文论文题目：抽屉原理及其应用学生姓名：学号：专业：数学与应用数学指导教师：学院：数学科学学院12012年5月20日毕业论文内容介绍论文题目抽屉原理及其应用选题时间2011.10.25完成时间2012.5.18论文（设计）字数12750关键词抽屉原理；数论；离散数学；高等代数；抽象代数；Ramsey定理；应用论文题目的来源、理论和实践意义：题目来源：学生自拟研究意义：研究抽屉原理在高等数学中数论、离散数学、高等代数、抽象代数等多个学科中的运用，对其在高等数学各方面的运用进行较为全面的梳理总结，加深对抽屉原理的理解，使复杂的数学问题能够在抽屉原理的作用下得到灵活巧妙的解决.论文（设计）的主要内容及创新点：主要内容：本文简述了抽屉原理普遍使用的简单形式、各种推广形式，着重阐述其在数论和离散数学、高等代数及抽象代数中的应用,及在生活中的应用，可以巧妙地解决一些复杂问题，并根据抽屉原理的不足之处引入抽屉原理的推广定理Ramsey定理.创新点：以往抽屉原理的相关文章或集中于中小学数学方面或比较零散片面，本文的主要创新点是就本人所学过的高等数学的几门学科中抽屉原理的应用进行比较全面的梳理总结.生活中的应用这一部分本文区别于其它相关文章中大量的缺乏实际意义的事例，选取与生活贴近的如赛程安排、资源分配等问题进行阐述，更好地突出抽屉原理在实际生活中的用处.附：论文本人签名：2012年5月20日目录中文摘要…………………………………………………………………1英文摘要…………………………………………………………………11.引言……………………………………………………………………22.抽屉原理的形式………………………………………………………23.抽屉原理在高等数学中的应用………………………………………33.1数论中的应用……………………………………………………33.2离散数学中的应用………………………………………………53.3高等代数中的应用………………………………………………83.4抽象代数中的应用………………………………………………94.抽屉原理在生活中的应用…………………………………………105.抽屉原理的推广定理－Ramsey定理………………………………12错误!未定义书签。6.参考文献……………………………………………………………161抽屉原理及其应用XXX摘要：本文简述了抽屉原理普遍使用的简单形式、各种推广形式，着重阐述其在数论和离散数学、高等代数及抽象代数中的应用,及在生活中的应用，可以巧妙地解决一些复杂问题，并根据抽屉原理的不足之处引入抽屉原理的推广定理Ramsey定理.关键词：抽屉原理；数论；离散数学；高等代数；抽象代数；Ramsey定理；应用DirichletdrawerprincipleandtheapplicationofitXXXAbstract:ThispaperintroducesthewidespreaduseofsimpleformsandallkindsofextendedformsofDirichletdrawerprinciple,focusingontheapplicationofDirichletdrawerprincipleinthenumbertheory,discretemathematics,hightalgebraandabstractalgebra,andalsothereallife.Itcansolveablysomecomplicatedproblems,andaccordingtotheprincipleofdrawertheshortcomingsoftheprincipleofintroducingthedrawertheoremRamseytheorem.Keywords:Dirichletdrawerprinciple;Numbertheory;Discretemathematics;Higheralgebra;Abstractalgebra;Ramseytheorem;Application.21.引言抽屉原理又称鸽巢原理、鞋箱原理或重叠原理，是一个十分简单又十分重要的原理.它是由德国著名数学家狄利克雷(P.G.T.Dirichlet1805-1855)首先发现的，因此也叫作狄利克雷原理.抽屉原理简单易懂，主要用于证明某些存在性或必然性的问题，不仅在数论、组合论以及集合论等领域中有着广泛应用，在高等数学的其它几门学科领域中也是解决问题的有效方法.本文总结了如何运用抽屉原理解决数论、离散数学、高等代数及抽象代数中的问题，对抽屉原理在高等数学中的应用进行了梳理，将抽屉原理的解题思路拓展到高等数学的其他领域，有助于更好地理解抽屉原理，并举例阐述了抽屉原理在现实生活中的应用，以及根据抽屉原理的不足引出的Ramsey定理.2.抽屉原理的形式什么是抽屉原理？先举个简单的例子说明，就是将3个球放入2个篮子里，无论怎么放，必有一个篮子中至少要放入2个球，这就是抽屉原理.或者假定一群鸽子飞回巢中，如果鸽子的数目比鸽巢多，那么一定至少有一个鸽笼里有两只或两只以上的鸽子，这也是鸽巢原理这一名称的得来.抽屉原理简单直观，很容易理解.而这个看似简单的原理在高等数学中有着很大的用处，对于数论、离散数学、高等代数以及抽象代数中的一些复杂问题，可以利用抽屉原理巧妙的解答出来.下面首先从抽屉原理的形式入手，然后再研究它在高等数学中的应用.我们最常用的抽屉原理只是抽屉原理的简单形式，就是将n+1个元素或者更多的元素放入n个抽屉中，则至少有一个抽屉里放有两个或两个以上的元素.除了这种比较普遍的形式外，抽屉原理还经许多学者推广出其他的形式.陈景林、阎满富在他们编著的《组合数学与图论》一书中将抽屉原理抽象概括成以下三种形式[1]:原理1.把多于n个的元素按任一确定的方式分成n个集合，则一定有一个集合中含有两个或两个以上的元素.原理2.把m个元素任意放到n)(nm个集合里，则至少有一个集合里至少有k个元素，其中3原理3.把无穷个元素按任一确定的方式分成有限个集合，则至少有一个集合中仍含无穷个元素.卢开澄在《组合数学》（第三版）中将抽屉原理（书中称为鸽巢原理）又进行了推广[2].鸽巢原理：设k和n都是任意正整数，若至少有kn+1只鸽子分配在n个鸽巢中，则至少存在一个鸽巢中有至少k+1只鸽子.推论1.有m只鸽子和n个鸽巢，则至少有一个鸽巢中有不少于nm1+1只鸽子.推论2.若将n(m-1)+1个球放入n个盒子里，则至少有一个盒子有m个球.推论3.若12,,nmmm是n个正整数，而且r=12nmmmn，则12,,nmmm中至少有一个数不小于r.另外，抽屉原理还可以用映射的形式来表示，即:设A和B是两个有限集，如果AB，那么对从A到B的任何满射f，至少存在1a,2a,使12fafa.3.抽屉原理在高等数学中的应用以上的几种形式就是我们解题时常用到的抽屉原理的表示形式，接下来，在了解了抽屉原理的基本形式以及多位学者所发展的推广形式的基础上，我们通过一些比较典型的实例来说明抽屉原理在高等数学中数论、离散数学、高等代数以及抽象代数这五个方面的应用.3.1数论问题中的应用例1.任意5个整数中，有其中3个整数的和为3的倍数.证明将整数分为形如3k、3k+1及3k+2这3类形式，1mnmnkmnmn　　　,　　当能整除时,　　　,　　当不能整除时.　　4则我们可以将这3类整数看作是3个抽屉，将这5个整数看作元素放入这3个抽屉中.由抽屉原理可知，至少存在2=[315]+1个整数在同一抽屉中，即它们都是形如（3k+m）的整数，m=0,1或2.如果有3个以上的数在同一个抽屉中，则取其中的任意三个数，它们的和是形如3（3k+m）的整数，即三者的和为3的倍数.如果有2个整数在同一个抽屉中，则由抽屉原理知，在余下的3个数中有2个数在同一个抽屉中，余下的1个数在另一个抽屉中.在3个抽屉中各取一个数，这3个数的形式分别为3k1,3k2+1,3k3+2,则三者的和为3（k1+k2+k3）+3，即为3的倍数.例2.设有两组整数，而且每一组的数都是小于n（nZ）的互不相同的数，这两组数的数目个数≧n，则存在一对分别取自两组的数使这两个数的和为n.证明设这两组数为{a1,a2,…,ap}、{b1,b2,…,bq}.已知每一组的数都是小于n（nZ）的互不相同的数.不妨设a1a2…ap,1b2b…qb.令ci=n-ai,i=1,2,…,k.则有n-1≧c1≧c2≧…≧cp≧1.n-1≧b1≧b2≧…≧bq≧1.这些未知数只能在1,2,…,n-1中取值，我们可以将1,2,…,n-1这n个数看作n个抽屉.考察数集{b1,b2,…,bq，c1，c2，…，cp}.由于p+q≧n,运用抽屉原理可知,至少有两个数在1,2,…,n-1之中的一个抽屉，也就是至少有两个数取同一个值，且这两个数分别来自{1c，2c，…，pc}、{b1，b2，…，bq}.5(此是因为，根据已知条件，{c1，c2，…，cp}、{b1,b2,…,bq}在各自集合中是互不相同的，假定两个数同时取自{1c，2c，…，pc}，也就是在这p个数当中有两个数被同时放在同一抽屉里，则这两个数相等，而iianc,ia互不相同，则ic互不相同，两者矛盾.)即jjiancb,nbaij.3.2离散数学中的应用例3.设有3个7位的二进制数765432176543217654321cccccccbbbbbbbaaaaaaa试证存在整数i和j,17ij，使得下列之一必然成立jijijijijijiccbbccaabbaa,解由已知条件，在每一个纵列中，含有三个元素，分别都只由两种选择，即0或1，则根据鸽巢原理，iiiiiicbcaba,,中至少一个必然成立.成立的时候取值的不同可以有232C=6种情况，而每一横行共有七个元素再根据鸽巢原理，必有两列是相同的.即jijijijijijiccbbccaabbaa,,之一必然成立.例4.三维空间中9个坐标为整数的点，试证在两两相连的线段内，至少存在一个坐标为整数的内点.解三维空间中，任意两坐标为整数的点，若这两点相连的线段内不存在坐标为整数的内点，则对于x,y,z这三个坐标轴，这两点至少在一个坐标上的差值正好是1.那么，在这9个坐标为整数的点中，任意取出一点，与这个点的三个坐标中，6存在的差值正好是1的共有7类，即与x轴差值正好是1，与y轴差值正好是1，与z轴差值正好是1，与x,y轴差值都是1，与x,z轴差值都是1，与y,z轴差值都是1，与x,y,z轴差值都是1.对于剩下的8个点，若存在一点a不满足这7种情况，那么a点与这个点相连的线段内必有一个坐标为整数的内点.若剩下的8个点都属于这7种情况之一，那么，运用鸽巢原理，则至少存在两个点属于这7种情况中的同一个情况，那么，这两点中必存在一个坐标为整数的内点.例5.把从1到326的326个整数任意分为5个部分，试证其中有一部分至少有一个数是某两个数之和，或是另一个数的两倍.解（用反证法）假设存在划分326,154321PPPPP，iP)5,4,3,2,1(i中没有数是两个数之和，即iP)5,4,3,2,1(i中没有数是两个数之差.根据鸽巢原理（推论1）设1到326中至少有66151326个元素属于1P，并设为},,{6621aaaA，不妨设6621aaa.若A中存在一个元素是某两个元素之差，则满足题目要求.否则，令16665132121,,,aabaabaab，令},,{6521bbbB.显然B中的元素仍然是1到326之间的数，即65,2,1,3261ibi.根据假定B中无一属于1P，所以B的元素属于2P，3P，4P，5P.同理，设B中至少存在属于P2的1714165个元素.设为}