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

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

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

3、：论文本人签名：2012 年 5 月 20 日目录中文摘要. 1英文摘要. 11. 弓 I 言. 22. 抽屉原理的形式. 23. 抽屉原理在高等数学中的应用. 33.1 数论中的应用 .33.2 离散数学中的应用.53.3 高等代数中的应用.83.4 抽象代数中的应用.94. 抽屉原理在生活中的应用 . 105. 抽屉原理的推广定理Ramse 症理 . 12错误！未定义书签。6. 参考文献. 161抽屉原理及其应用XXX摘要：本文简述了抽屉原理普遍使用的简单形式、各种推广形式，着重阐述其在数论和离散数学、高等代数及抽象代数中的应用，及在生活中的应用，可以巧妙地解决一些复杂问题， 并根据抽屉原

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

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

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

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

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

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

10、3，即 为 3 的倍数.例 2.设有两组整数，而且每一组的数都是小于n (nZ )的互不相同的数，这两组数的数目个数三 n,则存在一对分别取自两组的数使这两个数的和为n.证明设这两组数为a1,a2,ap、b1,b2,bq.已知每一组的数都是小于 n (n，Z J 的互不相同的数.不妨设 aia2.ap, bib2 bq.4令 ci=n-ai,i=1,2,k.则有 n-1 三 c1三 c2三三 cp三 1.n-1 三 b1= b2三三 bq= 1.这些未知数只能在 1,2,n-1 中取值，我们可以将 1,2,n-1 这n个数看作n个抽屉.考察数集b1,b2,bq, c , C2，,cp.由于 p

11、+q 三 n,运用抽屉原理可知，至少有两个数在 1,2,n-1 之中的一个 抽屉，也就是至少有两个数取同一个值，且这两个数分别来自C1,C2，Cp、b1，b2，bq.（ 此是因为，根据已知条件，C1，C2，Cp、b1,b2,bq在各 自集合中是互不相同的，假定两个数同时取自G，g，Cp，也就是在这 p 个数当中有两个数被同时放在同一抽屉里，则这两个数相等，而q = n- ai, ai互 不相同，则 Ci互不相同，两者矛盾.）即 b =5 = n_aj,aj$ 二 n.3.2 离散数学中的应用例 3.设有 3 个 7 位的二进制数&1b1b2b3b4b5b6b?C1C2C3C4C5C6C

12、7试证存在整数i和 j , 1 G ：j乞7，使得下列之一必然成立a aj= bi= bj,a aj=C 5由已知条件，在每一个纵列中，含有三个元素，分别都只由两种选择，即 0 或 1，5则根据鸽巢原理，ai=6问=Ci,b中至少一个必然成立.成立的时候取值的不同可以有 C22=6 种情况，而每一横行共有七个元素 再根据鸽巢原理，必有两列是相同的即aaj二b= bj, a：= a=G= 5= bj=G二Cj之一必然成立.例 4.三维空间中 9 个坐标为整数的点，试证在两两相连的线段内，至少存在一 个坐标为整数的内点.解三维空间中，任意两坐标为整数的点，若这两点相连的线段内不存在坐标为 整数的内

13、点，则对于 x,y,z 这三个坐标轴，这两点至少在一个坐标上的差值正好 是 1.那么，在这 9 个坐标为整数的点中，任意取出一点，与这个点的三个坐标中， 存在的差值正好是 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

14、 种情况中的同一个情况，那么，这两点中必存在一个坐标为整数 的内点例 5.把从 1 到 326 的 326 个整数任意分为 5 个部分， 试证其中有一部分至少有 一个数是某两个数之和，或是另一个数的两倍.解(用反证法)假设存在划分RP2P3P4Ps= 1,3261,P(i =1,2,3,4,5)中没有数是两个数之和， 即 R(i =1,2,3,4,5)中没有数是两个数之差.根据鸽巢原理(推论 1)严6_1片=66设 1 到 326 中至少有5-个元素属于R，并设为6A=a1,a2,a66，不妨设a1 Va2a66若 A 中存在一个元素是某两个元素之差，则满足题目要求b1 =a2 a1,b2 =

15、a3 a1,b65 =a66 a1令 B = b1,b2,b65显然 B 中的元素仍然是 1 到 326 之间的数，即 1Wb326,i=1,2,65.根据 假定 B中无一属于R，所以 B 的元素属于P2，巳，P4，P5.1 + 1=17同理，设 B 中至少存在属于 F2 的-4个元素.设为C =C1,C2,c17不妨设 G Vc2 Vc17则根据假设，在 C 中不存在一个元素是某两个元素之差.令d1= C2C1,d2= C3C1,，小花=57 G令 D=d1,d2,d 显然D中的元素仍然是 1 到 326 之间的数,即 1 di: 326,i =1,2,16 .易知存在整数I,m使得dk =

16、Ck7 -C1=（ai- 比）-（am-a1）=ai-am所以，D 中的元素不属于R，也不属于P2，只能属于P3，P4，R.否则，令7根据鸽巢原理（推论 1），设至少存在-16-131=6个元素属于F3.设为f1c f2c f3 Cf4 f5 f6V 326令F = f5,f6则根据假设，在 F 中不存在一个元素是某两个元素之差，令g1g1,g2,g3,g4,g5,显然 G 中的元素不属于P3.且对于gi存在p，q，1，m使得f1= （Cp -C1）一（Cq -C1） = Cp- Cq=（a| -a1） -（am -a1） =a| -am故 G 中的元素也不属于R和P2，贝 U G 中的元素属

17、于P4，F5.5-1对于 G 中的 5 个元素，根据鸽巢原理，设至少存在-21二3个属于P4.设为山 h2vhh V326.令H =0山2山3.令 X =h? -= h3- hT = tt?8显然，T 中的元素不属于P,P2,P3,巳,故 T 的元素属于P5但根据假定打=t2 _ X，令 U =t2 -tl，则 1 X2 X2n适合X2nXi2n ji,2,2n9证明KnjXiX设集合 s=X=彳2：|Xj|兰n, j = i,2,2n令A二aij n2nXiX2则该齐次线性方程组可写成AX =010* 2n送aijXj2n映射f：迂AX是一个满射显然|S=(2n+1)2n,因为引 -1 ,

18、0, 1,所以对 每个 XS,它的 2n 个分量适合2n瓦 a” 闾 aiX#越 x 卅 |+ anxnj牛|彳 x!和|+xjW2n2(i=1,2,n)因此|D|兰(4n2+1 $又2n2n2n(2n1)=4 n24n 1 4n21根据抽屉原理.（映射形式设 A 和 B 是两个有限集，如果 A B 那么对从 A 到 B 的任何满映射 f,至少存在a1,a2,使 f（ a a”=f（ a a2）.）S中至少存在两个不同的元Xi2n “D=AXi - -a2jXj j 42nanjXjj 1，: :XSIJXi 2:,XjXj1Xj2aXj 2n使f X二f Xj,即AXi二AXj,AXi Xj

19、=0.令a1:、=X1X2- Xj1一为2、Xi2nXj 2n .:1ot2a2nJ即是我们所要求的，。1尸2。2是则11不全为零的整数，且满足12Gk =Xik Xjk兰Xik+ Xjk兰2n（k = 1,2，2n）.例 7.设 A 为 n 阶方阵，证明存在 1 n n，使秩（A）=秩（Ai+I）=秩（A，42）= 证明因为n阶方阵的秩只能是0,1,2,-, n这n+1 个数之一.E= A0, A,A2,，An,An, E 的个数多于秩的个数，由抽屉原理可知，存在 k,l 满 足 1 乞 k1，则 R 是除环当且仅当对 R 中任意元素aO,b，方程 ax=b或 ya=b 在R中有解）在 R

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

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

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

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

24、至少存在两个同色三角形的问题， 而抽屉原理一般只局17限在证明至少存在一个或必然存在一个的问题， 所以对于上述命题抽屉原理就显得无能为力，这时需要运用 Ramsey 定理来解决问题.证明 设w,V2,V3,V4,V5,V6是K6的六个顶点，由上面的命题 1 可知，对K6任 意进行红、蓝两边着色都有一个同色三角形，不妨设 V1V2V3是红色三角形.以下 分各种情况来讨论(1)若 V1V4,VM,VIV6均为蓝边，如图 1 所示，则若 V4,V5,V6之间有一蓝边，不 妨设为 V4V5，则三角形 V1V4V5为蓝色三角形；否则， V4V5V6为红色三角形.若 V1V4, VMVM 中有一条红边，不

25、妨设 V1V4为红边，此时若边 V2V4N3V4中 有一条红边，不妨设 V3V4是红边，则 V1V3V4是一红色三角形，见图 2.以下就 V2V4N3V4均为蓝边的情况对与V4相关联的边的颜色进行讨论.(i)若 V4V5N4V6中有一蓝边，不妨设 V4V5为蓝边，如图 3，此时，若 V2V5N3V5均为红边，则 V2V3V5是红色三角形；否则， V2V4V5或厶 V3V4V5是蓝色三角形.VMV6为蓝色三角形图18(ii)若 V4V5N4V6均为红边，见图 4，此时，若 VV5,V6之间有一条红边，不妨 设V1V5为红边，则 V1V4V5为红色三角形；否则，从以上例子可知，抽屉原理在应用上确有

26、不足之处，之上只是个特例，至于 在别的领域中的不足之处还需我们进一步的探索 抽屉原理的应用领域十分广泛，涉及到高等数学的多个学科，并且在生活 中也有广泛的应用，可以巧妙的用于解决一些复杂问题，本文主要梳理总结了它 在数论、离散、高等代数及抽象代数中的应用，其不足之处也由Ramsey 定理进行了补充，使其能够更好的应用与问题解决当中6.参考文献1陈景林，阎满富组合数学与图论北京中国铁道出版社出版，2000.042卢开澄.组合数学（第3版）.北京清华大学出版社，2002.073濮安山.“高等代数中抽屉原理的应用”.哈师大自然科学学报，2001.064王向东，周士藩等.高等代数常用方法M.1989.11.杨子胥.近世代数.北京.高等教育出版社.2003.12严士健.抽屉原则及其它的一些应用J.数学通报,19597曹汝成.组合数学M.华东理工大学出版社,2000.由以上对各种情况的讨论知，对角形19山东师范大学本科毕业论文（设计）选题审批表学院：数学科学学院（章）系别/教研室：数学与应用数学时间：2011 年 10 月 25 日课 题 情况题目名称抽屉原理及其应用课题性质A 基础研究B基础应用研究2C应用研究教师姓名职称 讲师学位硕士课题来源A.科研 B. 生产 C. 教学 D. 其