抽屉原理及其应用.doc

1、本科毕业论文论文题目抽屉原理及其应用学生姓名学号专业数学与应用数学指导教师学院数学科学学院12014年5月20日毕业论文内容介绍论文题目抽屉原理及其应用选题时间20111025完成时间2012518论文（设计）字数12750关键词抽屉原理；数论；离散数学；高等代数；抽象代数；RAMSEY定理；应用论文题目的来源、理论和实践意义题目来源学生自拟研究意义研究抽屉原理在高等数学中数论、离散数学、高等代数、抽象代数等多个学科中的运用，对其在高等数学各方面的运用进行较为全面的梳理总结，加深对抽屉原理的理解，使复杂的数学问题能够在抽屉原理的作用下得到灵活巧妙的解决论文（设计）的主要内容及创新点主要内容本文

2、简述了抽屉原理普遍使用的简单形式、各种推广形式，着重阐述其在数论和离散数学、高等代数及抽象代数中的应用,及在生活中的应用，可以巧妙地解决一些复杂问题，并根据抽屉原理的不足之处引入抽屉原理的推广定理RAMSEY定理创新点以往抽屉原理的相关文章或集中于中小学数学方面或比较零散片面，本文的主要创新点是就本人所学过的高等数学的几门学科中抽屉原理的应用进行比较全面的梳理总结生活中的应用这一部分本文区别于其它相关文章中大量的缺乏实际意义的事例，选取与生活贴近的如赛程安排、资源分配等问题进行阐述，更好地突出抽屉原理在实际生活中的用处附论文本人签名2012年5月20日目录中文摘要1英文摘要11引言22抽屉原理

3、的形式23抽屉原理在高等数学中的应用331数论中的应用332离散数学中的应用533高等代数中的应用834抽象代数中的应用94抽屉原理在生活中的应用105抽屉原理的推广定理RAMSEY定理12错误未定义书签。6参考文献16抽屉原理及其应用XXX摘要本文简述了抽屉原理普遍使用的简单形式、各种推广形式，着重阐述其在数论和离散数学、高等代数及抽象代数中的应用,及在生活中的应用，可以巧妙地解决一些复杂问题，并根据抽屉原理的不足之处引入抽屉原理的推广定理RAMSEY定理关键词抽屉原理；数论；离散数学；高等代数；抽象代数；RAMSEY定理；应用1引言抽屉原理又称鸽巢原理、鞋箱原理或重叠原理，是一个十分简单又

4、十分重要的原理它是由德国著名数学家狄利克雷PGTDIRICHLET18051855首先发现的，因此也叫作狄利克雷原理抽屉原理简单易懂，主要用于证明某些存在性或必然性的问题，不仅在数论、组合论以及集合论等领域中有着广泛应用，在高等数学的其它几门学科领域中也是解决问题的有效方法本文总结了如何运用抽屉原理解决数论、离散数学、高等代数及抽象代数中的问题，对抽屉原理在高等数学中的应用进行了梳理，将抽屉原理的解题思路拓展到高等数学的其他领域，有助于更好地理解抽屉原理，并举例阐述了抽屉原理在现实生活中的应用，以及根据抽屉原理的不足引出的RAMSEY定理2抽屉原理的形式什么是抽屉原理先举个简单的例子说明，就是

5、将3个球放入2个篮子里，无论怎么放，必有一个篮子中至少要放入2个球，这就是抽屉原理或者假定一群鸽子飞回巢中，如果鸽子的数目比鸽巢多，那么一定至少有一个鸽笼里有两只或两只以上的鸽子，这也是鸽巢原理这一名称的得来抽屉原理简单直观，很容易理解而这个看似简单的原理在高等数学中有着很大的用处，对于数论、离散数学、高等代数以及抽象代数中的一些复杂问题，可以利用抽屉原理巧妙的解答出来下面首先从抽屉原理的形式入手，然后再研究它在高等数学中的应用我们最常用的抽屉原理只是抽屉原理的简单形式，就是将N1个元素或者更多的元素放入N个抽屉中，则至少有一个抽屉里放有两个或两个以上的元素除了这种比较普遍的形式外，抽屉原理还

6、经许多学者推广出其他的形式陈景林、阎满富在他们编著的组合数学与图论一书中将抽屉原理抽象概括成以下三种形式1原理1把多于N个的元素按任一确定的方式分成N个集合，则一定有一个集合中含有两个或两个以上的元素原理2把M个元素任意放到NNM个集合里，则至少有一个集合里至少有K个元素，其中原理3把无穷个元素按任一确定的方式分成有限个集合，则至少有一个集合中仍含无穷个元素卢开澄在组合数学（第三版）中将抽屉原理（书中称为鸽巢原理）又进行了推广2鸽巢原理设K和N都是任意正整数，若至少有KN1只鸽子分配在N个鸽巢中，则至少存在一个鸽巢中有至少K1只鸽子推论1有M只鸽子和N个鸽巢，则至少有一个鸽巢中有不少于NM11

7、只鸽子推论2若将NM11个球放入N个盒子里，则至少有一个盒子有M个球推论3若12,NMMM是N个正整数，而且R12NMMMN，则1MNMNKMNMN,当能整除时,当不能整除时12,NMMM中至少有一个数不小于R另外，抽屉原理还可以用映射的形式来表示，即设A和B是两个有限集，如果AB，那么对从A到B的任何满射F，至少存在1A,2A,使12FAFA3抽屉原理在高等数学中的应用以上的几种形式就是我们解题时常用到的抽屉原理的表示形式，接下来，在了解了抽屉原理的基本形式以及多位学者所发展的推广形式的基础上，我们通过一些比较典型的实例来说明抽屉原理在高等数学中数论、离散数学、高等代数以及抽象代数这五个方面

8、的应用31数论问题中的应用例1任意5个整数中，有其中3个整数的和为3的倍数证明将整数分为形如3K、3K1及3K2这3类形式，则我们可以将这3类整数看作是3个抽屉，将这5个整数看作元素放入这3个抽屉中由抽屉原理可知，至少存在23151个整数在同一抽屉中，即它们都是形如（3KM）的整数，M0,1或2如果有3个以上的数在同一个抽屉中，则取其中的任意三个数，它们的和是形如3（3KM）的整数，即三者的和为3的倍数如果有2个整数在同一个抽屉中，则由抽屉原理知，在余下的3个数中有2个数在同一个抽屉中，余下的1个数在另一个抽屉中在3个抽屉中各取一个数，这3个数的形式分别为3K1,3K21,3K32,则三者的和

9、为3（K1K2K3）3，即为3的倍数例2设有两组整数，而且每一组的数都是小于N（NZ）的互不相同的数，这两组数的数目个数N，则存在一对分别取自两组的数使这两个数的和为N证明设这两组数为A1,A2,AP、B1,B2,BQ已知每一组的数都是小于N（NZ）的互不相同的数不妨设A1B那么对从A到B的任何满映射F，至少存在1A,2A,使F1AF2A）S中至少存在两个不同的元NJJJJNIIIIXXXXXXXX221221,使JIXFXF,即JIAXAX,0JIXXA令NJNIJIJINXXXXXX222211221，则N221即是我们所要求的，N2,21,是不全为零的整数，且满足NKNXXXXJKIKJ

10、KIKK2,2,12例7设A为N阶方阵，证明存在1NI，使秩IA秩1IA秩2IA证明因为N阶方阵的秩只能是N,2,1,0这N1个数之一E120,NNAAAAA,E的个数多于秩的个数，由抽屉原理可知，存在K,L满足1K2,则存在最小正整数RP,Q,使得当NRP,Q时，用红蓝两色涂NK的边，则或存在一个蓝色的PK,或存在一个红色的PKRAMSEY定理（狭义）的内容任意六个人中要么至少三个人认识，要么至少三个不认识RAMSEY定理可以视为抽屉原理的推广，1947年，匈牙利数学家把这一原理引进到中学生数学竞赛中，当年匈牙利全国数学竞赛有一道这样的试题“证明任何六个人中，一定可以找到三个互相认识的人，或

11、者三个互不认识的人”在1958年67月号美国数学月刊同样也登载着这样一个有趣的问题“任何六个人的聚会，总会有3人互相认识或3人互相不认识”这就是著名的RAMSEY问题这个问题乍看起来，似乎令人匪夷所思但如果懂得抽屉原理，要证明这个问题是十分简单的我们用A、B、C、D、E、F代表六个人，从中随便找一个，例如A吧，把其余五个人放到“与A认识”和“与A不认识”两个“抽屉”里去，根据抽屉原理，至少有一个抽屉里有三个人不妨假定在“与A认识”的抽屉里有三个人，他们是B、C、D如果B、C、D三人互不认识，那么我们就找到了三个互不认识的人；如果B、C、D三人中有两个互相认识，例如B与C认识，那么，A、B、C就

12、是三个互相认识的人不管哪种情况，本题的结论都是成立的或者我们可以用染色的方法以6个顶点分别代表6个人，如果两人相识，则在相应的两点间连一条红边，否则在相应的两点间连一蓝边命题1对6个顶点的完全图6K任意进行红、蓝两边着色，都存在一个红色三角形或蓝色三角形证明如下首先，把这6个人设为A、B、C、D、E、F六个点由A点可以引出AB、AC、AD、AE、AF五条线段设如果两个人认识，则设这两个人组成的线段为红色；如果两个人不认识，则设这两个人组成的线段为蓝色由抽屉原则可知这五条线段中至少有三条是同色的不妨设AB、AC、AD为红色若BC或CD为红色，则结论显然成立若BC和CD均为蓝色，则若BD为红色，则

13、一定有三个人相互认识；若BD为蓝色，则一定有三个人互相不认识上述的RAMSEY问题等价于下面的命题1命题1对6个顶点的完全图6K任意进行红、蓝两边着色，都存在一个红色三角形或蓝色三角形命题1运用抽屉原理可以很容易很简便地对其进行证明现将命题1推广成下面的命题2命题2对六个顶点的完全图6K任意进行红、蓝两边着色，都至少有两个同色三角形由于命题2是要证明至少存在两个同色三角形的问题，而抽屉原理一般只局限在证明至少存在一个或必然存在一个的问题，所以对于上述命题抽屉原理就显得无能为力，这时需要运用RAMSEY定理来解决问题证明设,21VV6543,VVVV是6K的六个顶点，由上面的命题1可知，对6K任

14、意进行红、蓝两边着色都有一个同色三角形，不妨设321VVV是红色三角形以下分各种情况来讨论1若615141,VVVVVV均为蓝边，如图1所示，则若654,VVV之间有一蓝边，不妨设为54VV，则三角形541VVV为蓝色三角形；否则，654VVV为红色三角形图1图22若615141,VVVVVV中有一条红边，不妨设41VV为红边，此时若边4342,VVVV中有一条红边，不妨设43VV是红边，则431VVV是一红色三角形，见图2以下就4342,VVVV均为蓝边的情况对与4V相关联的边的颜色进行讨论若6454,VVVV中有一蓝边，不妨设54VV为蓝边，如图3，此时，若5352,VVVV均为红边，则5

15、32VVV是红色三角形；否则，542VVV或543VVV是蓝色三角形若6454,VVVV均为红边，见图4，此时，若651,VVV之间有一条红边，不妨设51VV为红边，则541VVV为红色三角形；否则，651VVV为蓝色三角形图3图4由以上对各种情况的讨论知，对6K的任意红、蓝两边着色均有两个同色三角形从以上例子可知，抽屉原理在应用上确有不足之处，之上只是个特例，至于在别的领域中的不足之处还需我们进一步的探索抽屉原理的应用领域十分广泛，涉及到高等数学的多个学科，并且在生活中也有广泛的应用，可以巧妙的用于解决一些复杂问题，本文主要梳理总结了它在数论、离散、高等代数及抽象代数中的应用，其不足之处也由

16、RAMSEY定理进行了补充，使其能够更好的应用与问题解决当中6参考文献1陈景林,阎满富组合数学与图论北京中国铁道出版社出版,2000042卢开澄组合数学（第3版）北京清华大学出版社，2002073濮安山“高等代数中抽屉原理的应用”哈师大自然科学学报，2001064王向东,周士藩等高等代数常用方法M1989115杨子胥近世代数北京高等教育出版社2003126严士健抽屉原则及其它的一些应用J数学通报,19597曹汝成组合数学M华东理工大学出版社,2000山东师范大学本科毕业论文（设计）选题审批表学院数学科学学院章系别/教研室数学与应用数学时间2011年10月25日课题情况题目名称抽屉原理及其应用课

17、题性质A基础研究B基础应用研究C应用研究教师姓名职称讲师学位硕士课题来源A科研B生产C教学D其它E学生自拟成果类别A论文B设计主要研究内容与研究目标本文简述了抽屉原理普遍使用的简单形式、各种推广形式，着重阐述其在数论和离散数学、高等代数及抽象代数中的应用,及在生活中的应用，可以巧妙地解决一些复杂问题，并根据抽屉原理的不足之处引入抽屉原理的推广定理RAMSEY定理以往抽屉原理的相关文章或集中于中小学数学方面或比较零散片面，本文就本人所学过的高等数学的几门学科中抽屉原理的应用进行比较全面的梳理总结生活中的应用这一部分本文区别于其它相关文章中大量的缺乏实际意义的事例，选取与生活贴近的如赛程安排、资源

18、分配等问题进行阐述，更好地突出抽屉原理在实际生活中的用处指导教师签字年月日选题学生签字年月日系所或教研室审题意见负责人签字年月日学院审批意见学院学位分委员会主任签字年月日论文题目抽屉原理及其应用学院名称数学科学学院专业数学与应用数学学生姓名学号指导教师2011年11月16日一、选题的性质基础应用研究二、选题的目的和意义研究抽屉原理在高等数学中数论、离散数学、高等代数、抽象代数等多个学科中的运用，对其在高等数学各方面的运用进行较为全面的梳理总结，加深对抽屉原理的理解，使复杂的数学问题能够在抽屉原理的作用下得到灵活巧妙的解决三、与本课题相关的国内外研究现状，预计可能有所创新的方面以往抽屉原理的相关文章或集中于中小学数学方面或比较零散片面，本文的主要创新点是就本人所学过的高等数学的几门学科中抽屉原理的应用进行比较全面的梳理总结生活中的应用这一部分本文区别于其它相关文章中大量的缺乏实际意义的事例，选取与生活贴近的如赛程安排、资源分配等问题进行阐述，更好地突出抽屉原理在实际生活中的用处四、课题研究的可行性分析五、课题研究的策略、方法和步骤六、预期成果形式描述七、指导教师意见指导教师签字年月日八、学院学位分委员会意见学院学位分委员会主任签字年月日