大学数学本科毕业论文-鸽笼原理

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

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

3、中的用处. 附：论文本人签名： 2012 年 5 月 20 日 目录中文摘要1英文摘要11.引言22.抽屉原理的形式23.抽屉原理在高等数学中的应用3 3.1 数论中的应用 3 3.2 离散数学中的应用 5 3.3 高等代数中的应用 8 3.4 抽象代数中的应用 94.抽屉原理在生活中的应用 105.抽屉原理的推广定理Ramsey 定理 126.参考文献 16 1 抽屉原理及其应用 XXX摘要：本文简述了抽屉原理普遍使用的简单形式、各种推广形式，着重阐述其在数论和离散数学、高等代数及抽象代数中的应用,及在生活中的应用，可以巧妙地解决一些复杂问题，并根据抽屉原理的不足之处引入抽屉原理的推广定理R

4、amsey 定理.关键词：抽屉原理；数论；离散数学；高等代数；抽象代数；Ramsey 定理；应用 1.1.引言引言 抽屉原理又称鸽巢原理、鞋箱原理或重叠原理，是一个十分简单又十分重要的原理.它是由德国著名数学家狄利克雷(P.G.T.Dirichlet 1805-1855)首先发现的，因此也叫作狄利克雷原理.抽屉原理简单易懂，主要用于证明某些存在性或必然性的问题，不仅在数论、组合论以及集合论等领域中有着广泛应用，在高等数学的其它几门学科领域中也是解决问题的有效方法.本文总结了如何运用抽屉原理解决数论、离散数学、高等代数及抽象代数中的问题，对抽屉原理在高等数学中的应用进行了梳理，将抽屉原理的解题思

5、路拓展到高等数学的其他领域，有助于更好地理解抽屉原理，并举例阐述了抽屉原理在现实生活中的应用，以及根据抽屉原理的不足引出的 Ramsey 定理.2.2.抽屉原理的形式抽屉原理的形式什么是抽屉原理？先举个简单的例子说明，就是将 3 个球放入 2 个篮子里，无论怎么放，必有一个篮子中至少要放入 2 个球，这就是抽屉原理.或者假定一群鸽子飞回巢中，如果鸽子的数目比鸽巢多，那么一定至少有一个鸽笼里有两只或两只以上的鸽子，这也是鸽巢原理这一名称的得来.抽屉原理简单直观，很容易理解.而这个看似简单的原理在高等数学中有着2很大的用处，对于数论、离散数学、高等代数以及抽象代数中的一些复杂问题，可以利用抽屉原理

6、巧妙的解答出来.下面首先从抽屉原理的形式入手，然后再研究它在高等数学中的应用. 我们最常用的抽屉原理只是抽屉原理的简单形式，就是将 n+1 个元素或者更多的元素放入n个抽屉中，则至少有一个抽屉里放有两个或两个以上的元素.除了这种比较普遍的形式外，抽屉原理还经许多学者推广出其他的形式. 陈景林、阎满富在他们编著的组合数学与图论一书中将抽屉原理抽象概括成以下三种形式1:原理 1. 把多于个的元素按任一确定的方式分成个集合，则一定有一个nn集合中含有两个或两个以上的元素.原理 2. 把个元素任意放到个集合里，则至少有一个集合里至mn)(nm 少有个元素，其中k原理 3. 把无穷个元素按任一确定的方式

7、分成有限个集合，则至少有一个集合中仍含无穷个元素.卢开澄在组合数学 （第三版）中将抽屉原理（书中称为鸽巢原理）又进行了推广2.鸽巢原理：设 k 和 n 都是任意正整数，若至少有 kn+1 只鸽子分配在 n 个鸽巢中，则至少存在一个鸽巢中有至少 k+1 只鸽子.推论 1.有 m 只鸽子和 n 个鸽巢，则至少有一个鸽巢中有不少于+1 只nm 1鸽子.推论 2.若将 n(m-1)+1 个球放入 n 个盒子里，则至少有一个盒子有 m 个球.推论 3.若是 n 个正整数，而且 r=，则12,nm mm12nmmmn中至少有一个数不小于 r.12,nm mm1mnmnkmnmn,当能整除时,当不能整除时.

8、3另外，抽屉原理还可以用映射的形式来表示，即:设和是两个有限集，AB如果，那么对从到的任何满射，至少存在,使ABABf1a2a. 12f af a3.3.抽屉原理在高等数学中的应用抽屉原理在高等数学中的应用 以上的几种形式就是我们解题时常用到的抽屉原理的表示形式，接下来，在了解了抽屉原理的基本形式以及多位学者所发展的推广形式的基础上，我们通过一些比较典型的实例来说明抽屉原理在高等数学中数论、离散数学、高等代数以及抽象代数这五个方面的应用.3.13.1 数论问题中的应用数论问题中的应用 例例 1 1.任意 5 个整数中，有其中 3 个整数的和为 3 的倍数.证明证明 将整数分为形如 3k、3k+

9、1 及 3k+2 这 3 类形式， 则我们可以将这 3 类整数看作是 3 个抽屉，将这 5 个整数看作元素放入这3 个抽屉中. 由抽屉原理可知，至少存在 2=+1 个整数在同一抽屉中，即它们都是315形如（3k+m）的整数，m=0,1 或 2. 如果有 3 个以上的数在同一个抽屉中，则取其中的任意三个数，它们的和是形如 3（3k+m）的整数，即三者的和为 3 的倍数.如果有 2 个整数在同一个抽屉中，则由抽屉原理知，在余下的 3 个数中有2 个数在同一个抽屉中，余下的 1 个数在另一个抽屉中.在 3 个抽屉中各取一个数，这 3 个数的形式分别为 3k ,3k +1,3k +2,则三者的和为 3

10、（k +k +k ）123123+3，即为 3 的倍数.例例 2 2.设有两组整数，而且每一组的数都是小于 n（nZ ）的互不相同的数，这两组数的数目个数n，则存在一对分别取自两组的数使这两个数的和为 n.证明证明 设这两组数为a ,a ,a、b ,b ,b.12p12q 已知每一组的数都是小于 n（nZ ）的互不相同的数.4 不妨设 a a a,那么对从 A 到 B 的任何满映AB射 f，至少存在,使 f()=f().）1a2a1a2aS 中至少存在两个不同的元 njjjjniiiixxxXxxxX221221,使,即,. jixfxfjiAXAX 0jiXXA9令，则即是我们所要求的，是n

11、jnijijinxxxxxx222211221n221n2, 21,不全为零的整数，且满足.nknxxxxjkikjkikk2 , 2 , 12例例 7.7. 设为阶方阵，证明存在 1，使秩()=秩()=秩Anni iA1iA)(2iA证明证明 因为阶方阵的秩只能是这+1 个数之一.nn, 2, 1, 0n,的个数多于秩的个数，由抽屉原理可知，存在,E120,nnAAAAAEk满足 1使lkln秩()= 秩(),kAlA但秩()秩()秩(),kA1kAlA所以秩()=秩(),kA1kA利用此式与秩的性质得秩()秩()+秩()-秩(),ABCABBCB这里的是任意三个可乘矩阵，用数学归纳法可证C

12、BA,秩()=秩().mkA1mkA其中为非负整数，故命题的结论成立. 秩()=秩()=秩. miA1iA)(2iA3.43.4 抽象代数中的应用抽象代数中的应用例例 8.8.证明:有限群中的每个元素的阶均有限证明证明 设 G 为 n 阶有限群，任取 aG，则由抽屉原理可知中必231,nna aaaa有相等的不妨设于是有，从而 a 的阶有限,11staatsn s tae例例 9.9.证明只含有限个理想的非零整环 R 必是域.证明证明 根据魏得邦定理，只需证明 R 是除环即可.10(设是环且，则 R 是除环当且仅当对 R 中任意元素，方程R1Rba, 0ax=b 或 ya=b 在中有解)R 在

13、 R 中任取元素.ba, 0 考虑, 2 , 1,1iRaRyyaNtt 易知，都是的理想.,32RaRaRaR 但由于整环 R 只有有限个理想，根据抽屉原理. 必存在正整数 s 与 t 满足 s2,则存在最小正整数 R(p,q),使得当nR(p,q)时，用红蓝两色涂的边，则或存在一个蓝色的,或存在一个红色nKpK的.pK13Ramsey 定理（狭义）的内容任意六个人中要么至少三个人认识，要么至少三个不认识. Ramsey 定理可以视为抽屉原理的推广，1947 年，匈牙利数学家把这一原理引进到中学生数学竞赛中，当年匈牙利全国数学竞赛有一道这样的试题：“证明：任何六个人中，一定可以找到三个互相认

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

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

16、可知这五条线段中至少有三条是同色的.不妨设 AB、AC、AD 为红色.若 BC 或 CD 为红色，则结论显然成立.若 BC 和 CD 均为蓝色，则若 BD 为红色，则一定有三个人相互认识；若 BD为蓝色，则一定有三个人互相不认识.上述的 Ramsey 问题等价于下面的命题 1.命题 1.对 6 个顶点的完全图任意进行红、蓝两边着色，都存在一个红6K14色三角形或蓝色三角形.命题 1 运用抽屉原理可以很容易很简便地对其进行证明.现将命题 1 推广成下面的命题 2.命题 2.对六个顶点的完全图任意进行红、蓝两边着色，都至少有两个6K同色三角形.由于命题 2 是要证明至少存在两个同色三角形的问题，而

17、抽屉原理一般只局限在证明至少存在一个或必然存在一个的问题，所以对于上述命题抽屉原理就显得无能为力，这时需要运用 Ramsey 定理来解决问题. 证明 设是的六个顶点，由上面的命题 1 可知，对,21vv6543,vvvv6K任意进行红、蓝两边着色都有一个同色三角形，不妨设是红色三角6K321vvv形.以下分各种情况来讨论(1)若均为蓝边，如图 1 所示，则若之间有一蓝边，615141,vvvvvv654,vvv不妨设为，则三角形为蓝色三角形；否则，为红色三角形.54vv541vvv654vvv 图 1 图 2(2)若中有一条红边，不妨设为红边，此时若边615141,vvvvvv41vv中有一条

18、红边，不妨设是红边，则是一红色三角形，见图4342,vvvv43vv431vvv2.以下就均为蓝边的情况对与相关联的边的颜色进行讨论.4342,vvvv4v ()若中有一蓝边，不妨设为蓝边，如图 3，此时，若6454,vvvv54vv均为红边，则是红色三角形；否则，或是蓝5352,vvvv532vvv542vvv543vvv色三角形. ()若均为红边，见图 4，此时，若之间有一条红边，不6454,vvvv651,vvv妨设为红边，则为红色三角形；否则，为蓝色三角形.51vv541vvv651vvv15 图 3 图 4 由以上对各种情况的讨论知，对的任意红、蓝两边着色均有两个同色三6K角形.从以

19、上例子可知，抽屉原理在应用上确有不足之处，之上只是个特例，至于在别的领域中的不足之处还需我们进一步的探索. 抽屉原理的应用领域十分广泛，涉及到高等数学的多个学科，并且在生活中也有广泛的应用，可以巧妙的用于解决一些复杂问题，本文主要梳理总结了它在数论、离散、高等代数及抽象代数中的应用，其不足之处也由 Ramsey 定理进行了补充，使其能够更好的应用与问题解决当中.6.6.参考文献参考文献1陈景林,阎满富.组合数学与图论.北京中国铁道出版社出版,2000.042卢开澄.组合数学（第 3 版）.北京清华大学出版社，2002.073濮安山.“高等代数中抽屉原理的应用”.哈师大自然科学学报 ，2001.

20、064王向东,周士藩等.高等代数常用方法M.1989.11.5杨子胥.近世代数.北京.高等教育出版社.2003.126严士健.抽屉原则及其它的一些应用J.数学通报,19597曹汝成.组合数学M.华东理工大学出版社,2000.山山东师东师范大学本科范大学本科毕业论毕业论文（文（设计设计） ）选题审选题审批表批表学院：数学科学学院(章)系别/教研室：数学与应用数学时间：2011 年 10 月 25 16日题目名称抽屉原理及其应用课题性质A 基础研究 B 基础应用研究 C 应用研究教师姓名 职称讲师学位硕士课题来源A.科研 B.生产 C.教学 D.其它 E.学生自拟课题情况成果类别A.论文 B.设计主要研究内容与研究目标 本文简述了抽屉原理普遍使用的简单形式、各种推广形式，着重阐述其在数论和离散数学、高等代数及抽象代数中的应用,及在生活中的应用，可以巧妙地解决一些复杂问题，并根据抽屉原理的不足之处引入抽屉原理的推广定理 Ramsey 定理.以往抽屉原理的相关文章或集中于中小学数学方面或比较零散片面，本文就本人所学过的高等数学的几门学科中抽屉原理的应用进行比较全面的梳理总结.生活中的应用这一部分本文区别于其它相关文章中大量的缺乏实际意义的事例，选取与生活贴近的如赛