抽屉原理及其应用-数学与应用数学专业毕业设计-毕业论文.doc

本科毕业论文论文题目： 抽屉原理及其应用 学生姓名： 学号： 专业： 数学与应用数学 指导教师： 学 院： 数学科学学院 1 2012年 5 月 20 日毕业论文内容介绍论文题目抽屉原理及其应用选题时间2011.10.25完成时间2012.5.18论文（设计）字数12750关 键 词抽屉原理；数论；离散数学；高等代数；抽象代数；Ramsey定理；应用论文题目的来源、理论和实践意义：题目来源：学生自拟研究意义：研究抽屉原理在高等数学中数论、离散数学、高等代数、抽象代数等多个学科中的运用，对其在高等数学各方面的运用进行较为全面的梳理总结，加深对抽屉原理的理解，使复杂的数学问题能够在抽屉原理的作用下得到灵活巧妙的解决.论文（设计）的主要内容及创新点：主要内容： 本文简述了抽屉原理普遍使用的简单形式、各种推广形式，着重阐述其在数论和离散数学、高等代数及抽象代数中的应用,及在生活中的应用，可以巧妙地解决一些复杂问题，并根据抽屉原理的不足之处引入抽屉原理的推广定理Ramsey定理.创新点：以往抽屉原理的相关文章或集中于中小学数学方面或比较零散片面，本文的主要创新点是就本人所学过的高等数学的几门学科中抽屉原理的应用进行比较全面的梳理总结.生活中的应用这一部分本文区别于其它相关文章中大量的缺乏实际意义的事例，选取与生活贴近的如赛程安排、资源分配等问题进行阐述，更好地突出抽屉原理在实际生活中的用处. 附：论文本人签名： 2012 年 5 月 20 日 目录中文摘要1英文摘要11.引言22.抽屉原理的形式23. 抽屉原理在高等数学中的应用3 3.1 数论中的应用 3 3.2 离散数学中的应用 5 3.3 高等代数中的应用 8 3.4 抽象代数中的应用 94.抽屉原理在生活中的应用 105.抽屉原理的推广定理Ramsey定理 126.参考文献 16 抽屉原理及其应用 XXX摘要：本文简述了抽屉原理普遍使用的简单形式、各种推广形式，着重阐述其在数论和离散数学、高等代数及抽象代数中的应用,及在生活中的应用，可以巧妙地解决一些复杂问题，并根据抽屉原理的不足之处引入抽屉原理的推广定理Ramsey定理.关键词：抽屉原理；数论；离散数学；高等代数；抽象代数；Ramsey定理；应用 Dirichlet drawer principle and the application of it XXXAbstract:This paper introduces the widespread use of simple forms and all kinds of extended forms of Dirichlet drawer principle,focusing on the application of Dirichlet drawer principle in the number theory ,discrete mathematics, hight algebra and abstract algebra ,and also the real life. It can solve ably some complicated problems,and according to the principle of drawer the shortcomings of the principle of introducing the drawer theorem Ramsey theorem. Keywords:Dirichlet drawer principle; Number theory; Discrete mathematics; Higher algebra; Abstract algebra; Ramsey theorem; Application.1.引言 抽屉原理又称鸽巢原理、鞋箱原理或重叠原理，是一个十分简单又十分重要的原理.它是由德国著名数学家狄利克雷(P.G.T.Dirichlet 1805-1855)首先发现的，因此也叫作狄利克雷原理.抽屉原理简单易懂，主要用于证明某些存在性或必然性的问题，不仅在数论、组合论以及集合论等领域中有着广泛应用，在高等数学的其它几门学科领域中也是解决问题的有效方法.本文总结了如何运用抽屉原理解决数论、离散数学、高等代数及抽象代数中的问题，对抽屉原理在高等数学中的应用进行了梳理，将抽屉原理的解题思路拓展到高等数学的其他领域，有助于更好地理解抽屉原理，并举例阐述了抽屉原理在现实生活中的应用，以及根据抽屉原理的不足引出的Ramsey定理.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.另外，抽屉原理还可以用映射的形式来表示，即:设和是两个有限集，如果，那么对从到的任何满射，至少存在,使.3.抽屉原理在高等数学中的应用 以上的几种形式就是我们解题时常用到的抽屉原理的表示形式，接下来，在了解了抽屉原理的基本形式以及多位学者所发展的推广形式的基础上，我们通过一些比较典型的实例来说明抽屉原理在高等数学中数论、离散数学、高等代数以及抽象代数这五个方面的应用.3.1 数论问题中的应用 例1.任意5个整数中，有其中3个整数的和为3的倍数.证明 将整数分为形如3k、3k+1及3k+2这3类形式， 则我们可以将这3类整数看作是3个抽屉，将这5个整数看作元素放入这3个抽屉中. 由抽屉原理可知，至少存在2=+1个整数在同一抽屉中，即它们都是形如（3k+m）的整数，m=0,1或2. 如果有3个以上的数在同一个抽屉中，则取其中的任意三个数，它们的和是形如3（3k+m）的整数，即三者的和为3的倍数.如果有2个整数在同一个抽屉中，则由抽屉原理知，在余下的3个数中有2个数在同一个抽屉中，余下的1个数在另一个抽屉中.在3个抽屉中各取一个数，这3个数的形式分别为3k,3k+1,3k+2,则三者的和为3（k+k+k）+3，即为3的倍数.例2.设有两组整数，而且每一组的数都是小于n（nZ）的互不相同的数，这两组数的数目个数n，则存在一对分别取自两组的数使这两个数的和为n.证明 设这两组数为a,a,a、b,b,b. 已知每一组的数都是小于n（nZ）的互不相同的数. 不妨设aaa,那么对从A到B的任何满映射f，至少存在,使f()=f().）S中至少存在两个不同的元 使,即,.令，则即是我们所要求的，是不全为零的整数，且满足.例7. 设为阶方阵，证明存在1，使秩()=秩()=秩证明 因为阶方阵的秩只能是这+1个数之一.,的个数多于秩的个数，由抽屉原理可知，存在,满足1使秩()= 秩(),但秩()秩()秩(),所以秩()=秩(),利用此式与秩的性质得秩()秩()+秩()-秩(),这里的是任意三个可乘矩阵，用数学归纳法可证秩()=秩().其中为非负整数，故命题的结论成立. 秩()=秩()=秩. 3.4 抽象代数中的应用例8.证明:有限群中的每个元素的阶均有限证明 设G为n阶有限群，任取aG，则由抽屉原理可知中必有相等的不妨设于是有，从而a的阶有限例9.证明只含有限个理想的非零整环R必是域.证明 根据魏得邦定理，只需证明R是除环即可.(设是环且，则R是除环当且仅当对R中任意元素，方程ax=b或ya=b在中有解) 在R中任取元素. 考虑 易知，都是的理想. 但由于整环R只有有限个理想，根据抽屉原理. 必存在正整数s与t满足s2,则存在最小正整数R(p,q),使得当nR(p,q)时，用红蓝两色涂的边，则或存在一个蓝色的,或存在一个红色的.Ramsey定理（狭义）的内容任意六个人中要么至少三个人认识，要么至少三个不认识. Ramsey定理可以视为抽屉原理的推广，1947年，匈牙利数学家把这一原理引进到中学生数学竞赛中，当年匈牙利全国数学竞赛有一道这样的试题：“证明：任何六个人中，一定可以找到三个互相认识的人，或者三个互不认识的人.” 在1958年6-7月号美国数学月刊同样也登载着这样一个有趣的问题“任何六个人的聚会，总会有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就是三个互相认识的人.不管哪种情况，本题的结论都是成立的.或者我们可以用染色的方法.以6个顶点分别代表6个人，如果两人相识，则在相应的两点间连一条红边，否则在相应的两点间连一蓝边.命题1.对6个顶点的完全图任意进行红、蓝两边着色，都存在一个红色三角形或蓝色三角形.证明如下首先，把这6个人设为A、B、C、D、E、F六个点.由A点可以引出AB、AC、AD、AE、AF五条线段.设如果两个人认识，则设这两个人组成的线段为红色；如果两个人不认识，则设这两个人组成的线段为蓝色.由抽屉原则可知这五条线段中至少有三条是同色的.不妨设AB、AC、AD为红色.若BC或CD为红色，则结论显然成立.若BC和CD均为蓝色，则若BD为红色，则一定有三个人相互认识；若BD为蓝色，则一定有三个人互相不认识.上述的Ramsey问题等价于下面的命题1.命题1.对6个顶点的完全图任意进行红、蓝两边着色，都存在一个红色三角形或蓝色三角形.命题1运用抽屉原理可以很容易很简便地对其进行证明.现将命题1推广成下面的命题2.命题2.对六个顶点的完全图任意进行红、蓝两边着色，都至少有两个同色三角形.由于命题2是要证明至少存在两个同色三角形的问题，而抽屉原理一般只局限在证明至少存在一个或必然存在一个的问题，所以对于上述命题抽屉原理就显得无能为力，这时需要运用Ramsey定理来解决问题. 证明 设是的六个顶点，由上面的命题1可知，对任意进行红、蓝两边着色都有一个同色三角形，不妨设是红色三角形.以下分各种情况来讨论(1)若均为蓝边，如图1所示，则若之间有一蓝边，不妨设为，则三角形为蓝色三角形；否则，为红色三角形. 图1 图2(2)若中有一条红边，不妨设为红边，此时若边中有一条红边，不妨设是红边，则是一红色三角形，见图2.以下就均为蓝边的情况对与相关联的边的颜色进行讨论. ()若中有一蓝边，不妨设为蓝边，如图3，此时，若均为红边，则是红色三角形；否则，或是蓝色三角形. ()若均为红边，见图4，此时，若之间有一条红边，不妨设为红边，则为红色三角形；否则，为蓝色三角形. 图3 图4 由以上对各种情况的讨论知，对的任意红、蓝两边着色均有两个同色三角形.从以上例子可知，抽屉原理在应用上确有不足之处，之上只是个特例，至于在别的领域中的不足之处还需我们进一步的探索. 抽屉原理的应用领域十分广泛，涉及到高等数学的多个学科，并且在生活中也有广泛的应用，可以巧妙的用于解决一些复杂问题，本文主要梳理总结了它在数论、离散、高等代数及抽象代数中的应用，其不足之处也由Ramsey定理进行了补充，使其能够更好的应用与问题解决当中.6.参考文献1陈景林,阎满富.组合数学与图论.北京中国铁道出版社出版,2000.042卢开澄.组合数学（第3版）.北京清华大学出版社，2002.073濮安山.“高等代数中抽屉原理的应用”.哈师大自然科学学报，2001.064王向东,周士藩等.高等代数常用方法M.1989.11.5杨子胥.近世代数.北京.高等教育出版社.2003.126严士健.抽屉原则及其它的一些应用J.数学通报,19597曹汝成.组合数学M.华东理工大学出版社,2000.山东师范大学本科毕业论文（设计）选题审批表学院：数学科学学院(章)系别/教研室：数学与应用数学时间：2011年10月25 日课题情况题目名称抽屉原理及其应用课题性质A基础研究 B基础应用研究 C应用研究教师姓名 职称讲师学位硕士课题来源A.科研 B.生产 C.教学 D.其它 E.学生自拟成果类别A.论文 B.设计主要研究内容与研究目标 本文简述了抽屉原理普遍使用的简单形式、各种推广形式，着重阐述其在数论和离散数学、高等代数及抽象代数中的应用,及在生活中的应用，可以巧妙地解决一些复杂问题，并根据抽屉原理的不足之处引入抽屉原理的推广定理Ramsey定理.以往抽屉原理的相关文章或集中于中小学数学方面或比较零散片面，本文就本人所学过的高等数学的几门学科中抽屉原理的应用进行比较全面的梳理总结.生活中的应用这一部分本文区别于其它相关文章中大量的缺乏实际意义的事例，选取与生活贴近的如赛程安排、资源分配等问题进行阐述，更好地突出抽屉原理在实际生活中的用处. 指导教师签字： 年 月 日 选题学生签字： 年 月 日系所或教研室审题意见负责人签字: 年 月 日学院审批意见学院学位分委员会主任签字: 年 月 日山东师范大学本科毕业论文（设计）开题报告 论文题目： 抽屉原理及其应用 学院名称： 数学科学学院 专 业： 数学与应用数学 学生姓名： 学 号： 指导教师： 2011年 11 月 16 日一、选题的性质 基础应用研究二、 选题的目的和意义研究抽屉原理在高等数学中数论、离散数学、高等代数、抽象代数等多个学科中的运用，对其在高等数学各方面的运用进行较为全面的梳理总结，加深对抽屉原理的理解，使复杂的数学问题能够在抽屉原理的作用下得到灵活巧妙的解决.三、与本课题相关的国内外研究现状，预计可能有所创新的方面以往抽屉原理的相关文章或集中于中小学数学方面或比较零散片面，本文的主要创新点是就本人所学过的高等数学的几门学科中抽屉原理的应用进行比较全面的梳理总结.生活中的应用这一部分本文区别于其它相关文章中大量的缺乏实际意义的事例，选取与生活贴近的如赛程安排、资源分配等问题进行阐述，更好地突出抽屉原理在实际生活中的用处.四、 课题研究的可行性分析五、课题研究的策略、方法和步骤六、预期成果形式描述七、指导教师意见指导教师签字：年 月 日八、学院学位分委员会意见 学院学位分委员会主任签字： 年 月 日 山东师范大学本科毕业论文（设计）教师指导记录表学院：数学科学学院 系别：_ 专业：数学与应用数学论文（设计）题目： 抽屉原理及其应用学生姓名 学号指导教师 职称讲师计划完成时间：2012年5月18日指导情况纪录（含指导时间、指导内容）1、2011年11月20日，指导老师开始指导论文的选题，对选题的角度，选题的高度，所选课题所应该涵盖的范围及研究内容等应该注意的问题都作了一个详尽的解释，经过几次的交流，最终在老师的指导下将题目敲定，并且对论文的结构框架也有了大体的安排。2、2012年4月16日，在指导老师的指导下，依选定的题目开始搜集资料，整理数据资料。3、2012年5月5日，在老师的指导下，进行论文的撰写，并将初稿上交。4、2012年5月7日，老师提出第一次的论文修改意见，内容包括：论文格式、标点符号、中英文摘要、关键词、应用数据、措辞、资料来源等。5、2012年5月16日，论文第二次修改完成以及开题报告指导修改完成。 指导教师签字： 学生签字：学院学位分委员会主任签字： 年 月 日指导教师意见（包括选题的意义，资料收集或实验方法、数据处理等方面的能力，论证或实验是否合理，主要观点或结果是否正确，有何独到的见解或新的方法，基础理论、专业知识的掌握程度及写作水平等，并就该论文是否达到本科毕业论文水平做出评价）成绩： 指导教师（签名）： 年 月 日注：成绩按优、良、中、合格、不合格五级分制计.评阅人意见（包括选题的意义，资料收集或实验方法、数据处理等方面的能力，论证或实验是否合理，主要观点或结果是否正确，有何独到的见解或新的方法，基础理论、专业知识的掌握程度及写作水平等，并就该论文是否达到本科毕业论文水平做出评价） 成绩： 评阅人（签名）： 年 月 日注：成绩按优、良、中、合格、不合格五级分制计.答辩委员会意见（应根据论文内容和答辩情况，并参考指导教师意见、评阅人意见对论文的综合水平做出具体评价）成绩： 答辩委员会主任（签名）： 年 月 日学院学位分委员会意见 成绩： 学位分委员会主任（签名）： （公章） 年 月 日注：成绩按优、良、中、合格、不合格五级分制计.山东师范大学本科毕业论文（设计）摘要学院： 数学科学学院 专业：数学与应用数学专业 班级：数（2）班姓名 学号 指导教师 论文（设计）题 目抽屉原理及其应用关键词抽屉原理；数论；离散；高等代数；抽象代数；Ramsey定理；应用论文（设计）字数12750内容摘要：本文简述了抽屉原理普遍使用的简单形式、各种推广形式，着重阐述其在数论、离散数学、高等代数及抽象代数中的应用,及其在生活中的应用，通过抽屉原理可以巧妙地解决一些复杂问题，并根据抽屉原理的不足之处引入抽屉原理的推广定理Ramsey定理.一、抽屉原理的形式二、抽屉原理在高等数学中的应用三、抽屉原理在生活中的应用四、抽屉原理的推广定理Ramsey定理 成绩学院负责人（签名）2012年 5 月 20日山东师范大学本科毕业论文（设计）摘要学院： 数学科学学院 专业：数学与应用数学专业 班级：数（2）班姓名 学号指导教师 论文（设计）题 目抽屉原理及其应用关键词抽屉原理；数论；离散；高等代数；抽象代数；Ramsey定理；应用论文（设计）字数12750内容摘要：本文简述了抽屉原理普遍使用的简单形式、各种推广形式，着重阐述其在数论、离散数学、高等代数及抽象代数中的应用,及其在生活中的应用，通过抽屉原理可以巧妙地解决一些复杂问题，并根据抽屉原理的不足之处引入抽屉原理的推广定理Ramsey定理.一、抽屉原理的形式二、抽屉原理在高等数学中的应用三、抽屉原理在生活中的应用四、抽屉原理的推广定理Ramsey定理成绩学院负责人（签名）2012年 5 月 20日1. 基于C8051F单片机直流电动机反馈控制系统的设计与研究2. 基于单片机的嵌入式Web服务器的研究 3. MOTOROLA单片机MC68HC（8）05PV8/A内嵌EEPROM的工艺和制程方法及对良率的影响研究 4. 基于模糊控制的电阻钎焊单片机温度控制系统的研制 5. 基于MCS-51系列