《抽屉原理及其应用数学论文.doc》由会员分享，可在线阅读，更多相关《抽屉原理及其应用数学论文.doc（32页珍藏版）》请在金锄头文库上搜索。
1、 本科毕业论文论文题目： 抽屉原理及其应用 学生姓名： 学号： 专业： 数学与应用数学 指导教师： 学 院： 数学科学学院 1 2012年 5 月 20 日 目 录中文摘要1英文摘要11.引言22.抽屉原理的形式23. 抽屉原理在高等数学中的应用3 3.1 数论中的应用 3 3.2 离散数学中的应用 5 3.3 高等代数中的应用 8 3.4 抽象代数中的应用 94.抽屉原理在生活中的应用 105.抽屉原理的推广定理Ramsey定理 126.参考文献 16 抽屉原理及其应用 摘要：本文简述了抽屉原理普遍使用的简单形式、各种推广形式，着重阐述其在数论和离散数学、高等代数及抽象代数中的应用,及在生活
2、中的应用，可以巧妙地解决一些复杂问题，并根据抽屉原理的不足之处引入抽屉原理的推广定理Ramsey定理.关键词：抽屉原理；数论；离散数学；高等代数；抽象代数；Ramsey定理；应用 Dirichlet drawer principle and the application of itAbstractThis paper introduces the widespread use of simple forms and all kinds of extended forms of Dirichlet drawer principle,focusing on the application of
3、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.
4、Keywords:Dirichlet drawer principle; Number theory; Discrete mathematics; Higher algebra; Abstract algebra; Ramsey theorem; Application.1.引 言抽屉原理又称鸽巢原理、鞋箱原理或重叠原理，是一个十分简单又十分重要的原理.它是由德国著名数学家狄利克雷(P.G.T.Dirichlet 1805-1855)首先发现的，因此也叫作狄利克雷原理.抽屉原理简单易懂，主要用于证明某些存在性或必然性的问题，不仅在数论、组合论以及集合论等领域中有着广泛应用，在高等数学的其它几门
5、学科领域中也是解决问题的有效方法.本文总结了如何运用抽屉原理解决数论、离散数学、高等代数及抽象代数中的问题，对抽屉原理在高等数学中的应用进行了梳理，将抽屉原理的解题思路拓展到高等数学的其他领域，有助于更好地理解抽屉原理，并举例阐述了抽屉原理在现实生活中的应用，以及根据抽屉原理的不足引出的Ramsey定理.2.抽屉原理的形式什么是抽屉原理？先举个简单的例子说明，就是将3个球放入2个篮子里，无论怎么放，必有一个篮子中至少要放入2个球，这就是抽屉原理.或者假定一群鸽子飞回巢中，如果鸽子的数目比鸽巢多，那么一定至少有一个鸽笼里有两只或两只以上的鸽子，这也是鸽巢原理这一名称的得来.抽屉原理简单直观，很容
6、易理解.而这个看似简单的原理在高等数学中有着很大的用处，对于数论、离散数学、高等代数以及抽象代数中的一些复杂问题，可以利用抽屉原理巧妙的解答出来.下面首先从抽屉原理的形式入手，然后再研究它在高等数学中的应用. 我们最常用的抽屉原理只是抽屉原理的简单形式，就是将n+1个元素或者更多的元素放入n个抽屉中，则至少有一个抽屉里放有两个或两个以上的元素.除了这种比较普遍的形式外，抽屉原理还经许多学者推广出其他的形式. 陈景林、阎满富在他们编著的组合数学与图论一书中将抽屉原理抽象概括成以下三种形式1:原理1. 把多于个的元素按任一确定的方式分成个集合，则一定有一个集合中含有两个或两个以上的元素.原理2.
7、把个元素任意放到个集合里，则至少有一个集合里至少有个元素，其中原理3. 把无穷个元素按任一确定的方式分成有限个集合，则至少有一个集合中仍含无穷个元素.卢开澄在组合数学（第三版）中将抽屉原理（书中称为鸽巢原理）又进行了推广2.鸽巢原理：设k和n都是任意正整数，若至少有kn+1只鸽子分配在n个鸽巢中，则至少存在一个鸽巢中有至少k+1只鸽子.推论1.有m只鸽子和n个鸽巢，则至少有一个鸽巢中有不少于+1只鸽子.推论2.若将n(m-1)+1个球放入n个盒子里，则至少有一个盒子有m个球.推论3.若是n个正整数，而且r=，则中至少有一个数不小于r.另外，抽屉原理还可以用映射的形式来表示，即:设和是两个有限集
8、，如果，那么对从到的任何满射，至少存在,使.3.抽屉原理在高等数学中的应用 以上的几种形式就是我们解题时常用到的抽屉原理的表示形式，接下来，在了解了抽屉原理的基本形式以及多位学者所发展的推广形式的基础上，我们通过一些比较典型的实例来说明抽屉原理在高等数学中数论、离散数学、高等代数以及抽象代数这五个方面的应用.3.1 数论问题中的应用 例1.任意5个整数中，有其中3个整数的和为3的倍数.证明 将整数分为形如3k、3k+1及3k+2这3类形式， 则我们可以将这3类整数看作是3个抽屉，将这5个整数看作元素放入这3个抽屉中. 由抽屉原理可知，至少存在2=+1个整数在同一抽屉中，即它们都是形如（3k+m
9、）的整数，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）的互不相同的数
10、. 不妨设aaa,. 令c=n-a,i=1,2,k. 则有n-1ccc1. n-1bbb1. 这些未知数只能在1,2,n-1中取值，我们可以将1,2,n-1这n个数看作n个抽屉. 考察数集b,b,b，c，c，c. 由于p+qn,运用抽屉原理可知,至少有两个数在1,2,n-1之中的一个抽屉，也就是至少有两个数取同一个值，且这两个数分别来自 ，、b，b，b. (此是因为，根据已知条件，c，c，c、b,b,b在各自集合中是互不相同的，假定两个数同时取自，也就是在这p个数当中有两个数被同时放在同一抽屉里，则这两个数相等，而,互不相同，则互不相同，两者矛盾.) 即, .3.2 离散数学中的应用 例3.设
11、有3个7位的二进制数 试证存在整数和,，使得下列之一必然成立 解 由已知条件，在每一个纵列中，含有三个元素，分别都只由两种选择，即0或1，则根据鸽巢原理，中至少一个必然成立. 成立的时候取值的不同可以有=6种情况，而每一横行共有七个元素再根据鸽巢原理，必有两列是相同的. 即之一必然成立.例4.三维空间中9个坐标为整数的点，试证在两两相连的线段内，至少存在一个坐标为整数的内点.解 三维空间中，任意两坐标为整数的点，若这两点相连的线段内不存在坐标为整数的内点，则对于x,y,z这三个坐标轴，这两点至少在一个坐标上的差值正好是1. 那么，在这9个坐标为整数的点中，任意取出一点，与这个点的三个坐标中，存
12、在的差值正好是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个部分，试证其中有一部分至少有一个数是某两个数之和，或是另一个数的两倍.解（用反证法） 假设存在划分 ，中没有数是两个数之和
13、， 即中没有数是两个数之差.根据鸽巢原理（推论1）设1到326中至少有个元素属于，并设为，不妨设.若A中存在一个元素是某两个元素之差，则满足题目要求.否则，令，令.显然B中的元素仍然是1到326之间的数，即.根据假定B中无一属于，所以B的元素属于 ， ， ，.同理，设B中至少存在属于P2的个元素.设为,不妨设.则根据假设，在C中不存在一个元素是某两个元素之差.令，令，显然D中的元素仍然是1到326之间的数,即.易知存在整数,使得.所以，D中的元素不属于，也不属于，只能属于 ， ，. 根据鸽巢原理（推论1），设至少存在个元素属于.设为.令.则根据假设，在F中不存在一个元素是某两个元素之差， 令.令,显然G中的元素不属于.且对于存在使得. 故G中的元素也不属于和，则G中的元素属于 ，.对于G中的5个元素，根据鸽巢原理，设至少存在个属于 .设为
