毕业论文：抽屉原理及其应用

中个整数的和为的倍数证明将整数分为形如及这类形式，，当能整除时当不能整除时则我们可以将这类整数看作是个抽屉，将这个整数看作元素放入这个抽屉中由抽屉原理可知，至少存在个整数在同抽屉中，即它们都是形如的整数或如果有个以上的数在同个抽屉中，则取其中的任意三个数，它们的和是形如的整数，即三者的和为的倍数如果有个整数在同个抽屉中，则由抽屉原理知，在余下的个数中有个数在同个抽屉中，余下的个数在另个抽屉中在个抽屉中各取个数，这个数的形式分别为，则三者的和为，即为的倍数例设有两组整数，而且每组的数都是小于的互不相同的数，这两组数的数目个数≧，则存在对分别取自两组的数使这两个数的和为证明设这两组数为„，„，已知每组的数都是小于的互不相同的数不妨设„，„令，„，则有≧≧≧„≧≧≧≧≧„≧≧这些未知数只能在„，中取值，我们可以将„，这个数看作个抽屉考察数集„„，由于≧，运用抽屉原理可知，至少有两个数在„，之中的个抽屉，也就是至少有两个数取同个值，且这两个数分别来自„，„，此是因为，根据已知条件，„，„，在各自集合中是互不相同的，假定两个数同时取自„也就是在这个数当中有两个数被同时放在同抽屉里，则这两个数相等，而，互不相同，则互不相同，两者矛盾即，离散数学中的应用例设有个位的二进制数试证存在整数和，，使得下列之必然成立，解由已知条件，在每个纵列中，含有三个元素，分别都只由两种选择，即或，则根据鸽巢原理，中至少个必然成立成立的时候取值的不同可以有种情况，而每横行共有七个元素再根据鸽巢原理，必有两列是相同的即之必然成立例三维空间中个坐标为整数的点，试证在两两相连的线段内，至少存在个坐标为整数的内点解三维空间中，任意两坐标为整数的点，若这两点相连的线段内不存在坐标为整数的内点，则对于这三个坐标轴，这两点至少在个坐标上的差值正好是那么，在这个坐标为整数的点中，任意取出点，与这个点的三个坐标中，存在的差值正好是的共有类，即与轴差值正好是，与轴差值正好是，与轴差值正好是，与，轴差值都是，与，轴差值都是，与，轴差值都是，与轴差值都是对于剩下的个点，若存在点不满足这种情况，那么点与这个点相连的线段内必有个坐标为整数的内点若剩下的个点都属于这种情况之，那么，运用鸽巢原理，则至少存在两个点属于这种情况中的同个情况，那么，这两点中必存在个坐标为整数的内点例把从到的个整数任意分为个部分，试证其中有部分至少有个数是两个数之和，或是另个数的两倍解用反证法假设存在划分，，中没有数是两个数之和，即中没有数是两个数之差根据鸽巢原理推论设到中至少有个元素属于，并设为，不妨设若中存在个元素是两个元素之差，则满足题目要求否则，令，，令显然中的元素仍然是到之间的数，即，根据假定中无属于，所以的元素属于，同理，设中至少存在属于的个元素设为，不妨设则根据假设，在中不存在个元素是两个元素之差令，，令，显然中的元素仍然是到之间的数，即，易知存在整数，使得所以，中的元素不属于，也不属于，只能属于根据鸽巢原理推论，设至少存在个元素属于设为六个点由点可以引出五条线段设如果两个人认识，则设这两个人组成的线段为红色如果两个人不认识，则设这两个人组成的线段为蓝色由抽屉原则可知这五条线段中至少有三条是同色的不妨设为红色若或为红色，则结论显然成立若和均为蓝色，则若为红色，则定有三个人相互认识若为蓝色，则定有三个人互相不认识上述的问题等价于下面的命题命题对个顶点的完全图任意进行红蓝两边着色，都存在个红色三角形或蓝色三角形命题运用抽屉原理可以很容易很简便地对其进行证明现将命题推广成下面的命题命题对六个顶点的完全图任意进行红蓝两边着色，都至少有两个同色三角形由于命题是要证明至少存在两个同色三角形的问题，而抽屉原理般只局限在证明至少存在个或必然存在个的问题，所以对于上述命题抽屉原理就显得无能为力，这时需要运用定理来解决问题证明设，是的六个顶点，由上面的命题可知，对任意进行红蓝两边着色都有个同色三角形，不妨设是红色三角形以下分各种情况来讨论若均为蓝边，如图所示，则若之间有蓝边，不妨设为，则三角形为蓝色三角形否则，为红色三角形图图若中有条红边，不妨设为红边，此时若边，中有条红边，不妨设是红边，则是红色三角形，见图以下就，均为蓝边的情况对与相关联的边的颜色进行讨论ⅰ若，中有蓝边，不妨设为蓝边，如图，此时，若，均为红边，则是红色三角形否则，或是蓝色三角形ⅱ若，均为红边，见图，此时，若之间有条红边，不妨设为红边，则为红色三角形否则，为蓝色三角形图图由以上对各种情况的讨论知，对的任意红蓝两边着色均有两个同色三角形从以上例子可知，抽屉原理在应用上确有不足之处，之上只是个特例，至于在别的领域中的不足之处还需我们进步的探索抽屉原理的应用领域十分广泛，涉及到高等数学的多个学科，并且在生活中也有广泛的应用，可以巧妙的用于解决些复杂问题，本文主要梳理总结了它在数论离散高等代数及抽象代数中的应用，其不足之处也由定理进行了补充，使其能够更好的应用与问题解决当中参考文献陈景林，阎满富组合数学与图论北京中国铁道出版社出版，卢开澄组合数学第版北京清华大学出版社，濮安山高等代数中抽屉原理的应用哈师大自然科学学报，王向东，周士藩等高等代数常用方法杨子胥近世代数北京高等教育出版社严士健抽屉原则及其它的些应用数学通报，曹汝成组合数学华东理工大学出版社，山东师范大学本科毕业论文设计选题审批表学院数学科学学院章系别教研室数学与应用数学时间年月日课题情况题目名称抽屉原理及其应用课题性质基础研究基础应用研究应用研究教师姓名职称讲师学位硕士课题来源科研生产教学其它学生自拟成果类别论文设计主要研究内容与研究目标本文简述了抽屉原理普遍使用的简单形式各种推广形式，着重阐述其在数论和离散数学高等代数及抽象代数中的应用，及在生活中的应用，可以巧妙地解决些复杂问题，并根据抽屉原理的不足之处引入抽屉原理的推广定理定理以往抽屉原理的相关文章或集中于中小学数学方面或比较零散片面，本文就本人所学过的高等数学的几门学科中抽屉原理的应用进行比较全面的梳理总结生活中的应用这部分本文区别于其它相关文章中大量的缺乏实际意义的事例，选取与生活贴近的如赛程安排资源分配等问题进行阐述，更好地突出抽屉原理在实际生活中的用处指导教师签字年月日选题学生签字年月日系所或教研室审题意见负责人签字年月日学院审批意见学院学位分委员会主任签字年月日山东师范大学本科毕业论文设计开题报告论文题目抽屉原理及其应用学院名称数学科学学院专业数学与应用数学学生姓名学号指导教师年月日选题的性质基础应用研究二选题的目的和意义研究抽屉原理在高等数学中数论离散数学高等代数抽象代数等多个学科中的运用，对其在高等数学各方面的运用进行较为全面的梳理总结，加深对抽屉原理的理解，使复杂的数学问题能够在抽屉原理的作用下得到灵活巧妙的解决三与本课题相关的国内外研究现状，预计可能有所创新的方面以往抽屉原理的相关文章或集中于中小学数学方面或比较零散片面，本文的主要创新点是就本人所学过的高等数学的几门学科中抽屉原理的应用进行比较全面的梳理总结生活中的应用这部分本文区别于其它相关文章中大量的缺乏实际意义的事例，选取与生活贴近的如赛程安排资源分配等问题进行阐述，更好地突出抽屉原理在实际生活中的用处四课题研究的可行性分析五课题研究的策略方法和步骤六预期成果形式描述七指导教师意见指导教师签字年月日八学院学位分委员会意见学院学位分委员会主任签字年月日山东师范大学本科毕业论文设计教师指导记录表学院数学科学学院系别专业数学与应用数学论文设计题目抽屉原理及其应用学生姓名学号指导教师职称讲师计划完成时间年月日指导情况纪录含指导时间指导内容年月日，指导老师开始指导论文的选题，对选题的角度，选题的高度，所选课题所应该涵盖的范围及研究内容等应该注意的问题都作了个详尽的解释，经过几次的交流，最终在老师的指导下将题目敲定，并且对论文的结构框架也有了大体的安排。

年月日，在指导老师的指导下，依选定的题目开始搜集资料，整理数据资料。

年月日，在老师的指导下，进行论文的撰写，并将初稿上交。

年月日，老师提出第次的论文修改意见，内容包括论文格式标点符号中英文摘要关键词应用数据措辞资料来源等。

年月日，论文第二次修改完成以及开题报告指导修改完成。

指导教师签字学生签字学院学位分委员会主任签字年月日指导教师意见包括选题的意义，资料收集或实验方法数据处理等方面的能力，论证或实验是否合理，主要观点或结果是否正确，有何独到的见解或新的方法，基础理论专业知识的掌握程度及写作水平等，并就该论文是否达到本科毕业论文水平做出评价成绩指导教师签名年月日注成绩按优良中合格不合格五级分制计评阅人意见包括选题的意义，资料收集或实验方法数据处理等方面的能力，论证或实验是否合理，主要观点或结果是否正确，有何独到的见解或新的方法，基础理论专业知识的掌握程度及写作水平等，并就该论文是否达到本科毕业论文水平做出评价成绩评阅人签名年月日注成绩按优良中合格不合格五级分制计答辩委员会意见应根据论文内容和答辩情况，并参考指导教师意见评阅人意见对论文的综合水平做出具体评价成绩答辩委员会主任签名年月日学院学位分委员会意见成绩学位分委员会主任签名公章年月日注成绩按优良中合格不合格五级分制计山东师范大学本科毕业论文设计摘要学院数学科学学院专业数学与应用数学专业班级数班姓名学号指导教师论文设计题目抽屉原理及其应用关键词抽屉原理数论离散高等代数抽象代数定理应用论文设计字数内容摘要本文简述了抽屉原理普遍使用的简单形式各种推广形式，着重阐述其在数论离散数学高等代数及抽象代数中的应用，及其在生活中的应用，通过抽屉原理可以巧妙地解决些复杂问题，并根据抽屉原理的不足之处引入抽屉原理的推广定理定理抽屉原理的形式推广形式简单形式二抽屉原理在高等数学中的应用抽象代数中