鸽巢原理及其应用毕业论文.doc

《鸽巢原理及其应用毕业论文.doc》由会员分享，可在线阅读，更多相关《鸽巢原理及其应用毕业论文.doc（27页珍藏版）》请在沃文网上搜索。

1、毕业论文（设计）鸽巢原理及其应用院（系）： 专 业： 学 生： 导 师： 不要删除分节符，此行不会被打印。鸽巢原理及其应用摘要鸽巢原理又称抽屉原理或重叠原理，是组合数学中两大基本原理之一。鸽巢原理要解决的是存在性问题，即在具体的组合数学问题中，要计算某些特定问题求解的方案数，其前提就是要知道这些方案的存在性。本文主要介绍鸽巢原理的各种表现形式，并更具这些形式解决实际问题。文中主要讲了鸽巢原理应用于整除关系问题，几何问题，人的相识问题，连续时间问题等比较常见的问题。用鸽巢原理解决问题，关键在于如何构造适当的鸽巢。对于同一个问题有不同的构造方式，而对于同一个问题也有不同的方法。所以，故在鸽巢时没有

2、固定的模式，应该因题而论，灵活运用鸽巢解题。另外，本文还简单介绍了鸽巢原理的广义模式，即Ramsey定理。文中指简单叙述了Ramsey定理在染色问题方面的应用。关键词：组合数学，鸽巢原理，构建鸽巢，瑞姆赛定理， Pigeonhole principle and applicationAbstractPigeonhole principle, also known as the principle or drawer superposition principle, is a combination of two basic principles of mathematics. Pigeonho

3、le principle to solve the existence problem is, that the specific combination of mathematical problems, to calculate the specific number of problem-solving program, its premise is to know the existence of these programs. This paper describes the pigeonhole principle in all its manifestations, and mo

4、re of these forms to solve practical problems. Major topics of the text used in the pigeonhole principle divisible by relationship problems, geometric problems, who met the problem, continuous-time problems of the more common problems. With the pigeonhole principle to solve the problem, the key is h

5、ow to construct an appropriate pigeonholes. For the same problem with different construction methods, and for the same problem with different methods. Therefore, it is in the pigeonhole without a fixed pattern, it should be because of problems in terms of the flexible use of pigeonhole problem-solvi

6、ng. In addition, the paper also briefly describes the pigeonhole principle generalized model, that Ramsey theorem. They pointed out brief description of the Ramsey theorem in coloring of the application. 将英文摘要设置了两端对齐，注意有没有文字间距被拉伸的变形了，此行不会被打印。Key Words: Combinatorial mathematics，pigeonhole principle，

7、to build pigeon nest，Ramsey principle,目 录摘要IAbstractII第1章绪论1第2章鸽巢原理及其应用22.1鸽巢原理22.1.1鸽巢原理的基本形式22.1.2鸽巢原理的推广形式(一)322.1.3鸽巢原理的推广形式(二)32.2鸽巢原理的应用32.2.1鸽巢原理应用于“整除关系”问题242.2.2鸽巢原理应用于“几何图形”问题382.2.3鸽巢原理应用于“人的相识”问题2112.2.4鸽巢原理应用于“连续时间”问题4122.2.5鸽巢原理的其他应用113第3章Ramsey问题2183.1Ramsey问题183.2Ramsey问题的一般化19结论21参考

8、文献22致谢23输入完毕请右击目录主体，选择更新域，并在Abstract行末和“结论”前一行行末加回车。此行不会被打印。23鸽巢原理及其应用第1章 绪论鸽巢原理又称抽屉原理或重叠原理，是组合数学中两大基本原理之一，是一个极其初等而又应用广泛的数学原理。其道理并无深奥之处，且正确性也很明显。但是若能灵活应用，便可能得到一些意想不到的结果。鸽巢原理要解决的是存在性问题，即在具体的组合数学问题中，要计算某些特定问题求解的方案数，其前提就是要知道这些方案的存在性。 在19世纪时一个名叫狄利克雷（Dirichlet 18051859）的德国数学家，在研究数论的问题时最早很巧妙运用鸽笼原理去解决问题。后来

9、德国数学家敏古斯基（Minkowski 18641909）也运用这原理得到一些结果。 到了20世纪初期杜尔（AThue 18631922）在不知道狄利克雷和敏古斯基的工作情况下，很机巧地利用鸽笼原理来解决不定方程的有理数解的问题，有12篇论文是用到这个原理。 后来西根（CLSiegel，1896？）利用杜尔的结果发现了现在称为西根引理的东西，这引理（Lemma）是在研究超越数时是最基本必用的工具。 1930年，英国逻辑学家F. P. Ramsey将这个简单原理作了深刻推广，即瑞姆赛（Ramsey）定理，也称为广义抽屉原理。它是一个重要的组合定理，并且在数论和密码学中也有着广泛的应用。使用鸽巢原

10、理解题的关键是巧妙构造鸽巢或抽屉，即如何找出合乎问题条件的分类原则。第2章 鸽巢原理及其应用2.1 鸽巢原理所谓鸽巢原理即如：1 （1）抽屉只有10双手套散开放着，从中任取出11只，其中至少有一双是成双的。（2）某次会议又为代表列席，每位代表认识其中某些人，则至少有两人认识的人数相等。（3）给定5个不同的正整数，其中至少有5个数的和被3整除 2.1.1 鸽巢原理的基本形式 只鸽子，只有只笼子，则至少有一支笼子里有两支鸽子。证明：如果这个笼子中的每一个都至多含有一个鸽子，那么鸽子的总数最多是，矛盾。所以，既然我们有个鸽子，于是某个笼子就必然包含至少两个鸽子。例2.1.1.1 366个人中必然至少

11、存在两人有相同的生日。其道理很简单，一年有365天，则366人中至少有一天是其中两人的生日。例2.1.1.2 5双随意摆放的袜子，从中任意抽取6只，则至少有两只是完整配对的。2.1.2 鸽巢原理的推广形式(一)3令，为正整数，如果将+-+1个物体放入个盒子内，那么，或者第一个盒子至少含有个物体，或者第二个盒子至少含有个物体，或者第个盒子至少含有个物体。证明：设将+-+1个物体分放到个盒子中，如果对于每个=1，2，第个盒子含有少于个物体，那么所有盒子中的物体总数不超过 (-1)+(-1)+ +(-1)+1=+-,该数比所分发的物体总数少1，所以我们断定，对于某一个=1，2，第个盒子至少包含个物体

12、。 2.1.3 鸽巢原理的推广形式(二)由上面的原理可得如下推论：推论2.1.3.1：只鸽子放入个笼子中，则至少有一个笼子中有不少于+1只鸽子。 如若不然，笼子里的个子不超过只，则个笼子的鸽子树不超过与假设矛盾。 推论2.1.3.2：(-1)+1只鸽子放入个鸽笼，则至少有一个鸽笼中有只鸽子。 推论2.1.1.3：设，均为正整数，且满足，则，申至少有一个数不小于。 例2.1.3.1 任意一群人中，必有两个人有相同数目的朋友。证明：设有个人，分3种情形讨论：（1）每个人都有朋友，由上面的举例可知结论成立；（2）只有一人无朋友，余下的-1人都有朋友，由（1）知此-1人中必有两人有相同数目的朋友；（3

13、）有两人或两人以上的人无朋友，则朋友数为0的人已经有两个，结论同样成立。2.2 鸽巢原理的应用鸽巢原理应用广泛，本文主要列举以下几类2.2.1 鸽巢原理应用于“整除关系”问题2例2211 在前12个自然数中任取7个数，一定存在两个数，其中的一个数是另一个数的整数倍。 分析：若能把前12个自然数划分成6个集合，即构成6个抽屉，使每个抽屉内的数或只有一个，或有任意的两个数，其中的一个是另一个的整数倍，这样就可以由抽屉原理推出结论。那么如何对这12个自然数进行分组。我们知道，一个自然数，它要么是奇数，要么是偶数。若是偶数，我们总能把它表达为奇数与(=1，2，3，)的乘积的形式。这样，如果允许上述乘积

14、中的因子2k的指数可以等于零，则每一个自然数都可表达成“奇数(=0，1，2，)的形式，于是，把这12个自然数用上述表达式进行表达，并把式中“奇数”部分相同的自然数作为一组，构成一个抽屉。 证明：把前12个自然数划分为如下六个抽屉： =l，l，l，1 ，=3，3，3 ，=5，5 ，=7 ，=9 ，=11 ，显然，上述六个抽屉内的任意两个抽屉无公共元素，且+=1，2，3，12。由鸽巢原理，对于前12个自然数不论以何种方式从其中取出7个数，必定存在两个数同在A1或A2或A3抽屉里，那么这两个数之间存在倍数关系。即一个数是另一个数的整数倍。 归纳：从1到2的正整数中任取+1个数，则这+1个数中至少有两

15、个数，其中一个数是另一个数的倍数。 证明：设这+1个数为，我们对其中的每一个数都进行如下的处理：去掉一切2的因子，直到剩下奇数为止。例如，20=5，去掉2留下奇数5，结果可得到+1个奇数，。显然1，2，而1到2中只有个奇数，由抽屉原理知，上面+1个奇数中至少有两个数是相同的，设这两个数为=()，它们分别代表的整数为和,不论它们谁大谁小，和也之间总存在倍数关系，即一个数是另一个数的整数倍。 例2212证明对任意给定的52个整数，存在其中的两个整数，要么两者的和能被100整除，要么两者的差能被100整除。 证明：任意一个整数除以100产生的余数不外乎为0，1，2，99。题目中的52个整数除以100

16、则产生52个余数(=1，2，52)。 如果这52个余数中有两个余数相等，即=()，那么一定能被100整除。即存在两个数，它们的差能被100整除。 如果这52个余数均不相等，我们现在对0，1，2，99这100个数来构造抽屉，将相加之和为100的两个数放在同一个抽屉里。 构造出来的51个抽屉如下：1，99，2，98，3，97,，49，51，0，50由于有52个不同的余数，根据鸽巢原理，必有两个余数来自同一个抽屉，这只能从前49个抽屉中取出。而不论从哪个抽屉取出，同一个抽屉里的两个余数之和为100，那么一定有产生这两个余数的两个整数之和能被100整除。 例2213 证明对任意+1个正整数a1，a2，

17、an + 1，（1）存在两个正整数和()，使得能够被整除；（2）至少存在整数和，使得和是倍数4。 证明：（1）一个整数除以的余数不外乎为0，1，2，-1。+1个整数a1，a2，an + 1除以则产生+1个余数，由于一个整数除以最多只能产生个不同的余数(即个抽屉)，故根据鸽巢原理，这+1个余数中，一定有两个相等。那么，产生相等余数的两个整数相减，其差一定能被整除。 (2) 构造一个数列， ， 则有两种情形：（1若有一个是的倍数，得证。（2设在上面的序列中没有任何一个元素是的倍数。令，其中=1，2，。假定上面的序列中所有的项都非的倍数，故其中，无一位0，而且所有的均小于。不超过的-1的正整数只有-

18、1个。根据鸽巢原理，其中至少存在一对，满足=。即和满足不妨设。， 得证。例2214 证明： 1200这200个整数，取出100个，如果其中一个小于16，则100个数中必有一个可以被其中的另一个除尽。6 证：（1）将1200的数=,为奇数。 则=1，3，5，199，有100个数。 有=|=,|。 （2）从1200这200个整数，取出100个， 。 （3）若中有=， 由（1）| 。 （4）若=1，3，5，199， 若=1，3，5，7，9，11，13，15 有，使=3 | =3。 （5）若=1，3，5，199， 若=8， 有，使=3， 有，使=9， 有，使=27， 有，使=81， ， |。 ，同理若

19、 ，或，或， 则命题成立。 而，或，或，或， 至少有一个成立，这时命题成立。 同理若=1，3，5，199， 若=2，4，6，10，12，14时命题成立2.2.2 鸽巢原理应用于“几何图形”问题3例2221 在边长为1的等边三角形内任意选择5个点，存在2个点，其间距离至多为1/2。 证明：由题意，可以构造出4个抽屉，每个抽屉满足在其问的距离至多为1/2(见图1)。根据鸽巢原理，在4个抽屉里分别放置4个点，不论第5个点如何放置，都满足两点之间的距离最多为1/2。 图（1） 图（2） 图（3）例1222证明在边长为1的等边三角形内任意选择10个点，存在两个点，其间距离至多为1/3。 证明：按照图（2

20、）的构造可以证明该题。归纳：在边长为1的等边三角形内任意选择+1个点，存在2个点，其间距离为在边长为1的等边三角形内任意选择5个点，存在2个点，其间距离至多为1/2。例2222证明在边长为1的等边三角形内任意选择10个点，存在两个点，其间距离至多为1/3。 证明：按照图（2）的构造可以证明该题。归纳：在边长为1的等边三角形内任意选择+1个点，存在2个点，其间距离为。 例2223 在单位正方形内任意给定51个点，求证至少有三个点落在一个半径为1/7的圆内。 证明：将单位正方形的各边五等分，以此把它分成25个边长为l/5的小正方形，作为25个抽屉。根据抽屉原理可知，其中至少有一个小正方形中含有+1

21、=3个点，而这样的小正方形外接圆半径是。又由=得1/7，所以至少有三个点在半径为1/7的一个圆内。 例2224 在直径为5的圆内任意给定10个点，证明存在两个点，它们之间的距离小于2。 证明：根据题意，我们最先考虑到把圆等分成9个扇形而构造出9个抽屉，但是虽然必有两个点在某一扇形内，但不能确认它们之间的距离小于2。于是我们考虑先用一个与已知圆同心，半径为1的不包含边界的小圆作为一个抽屉，然后再把圆环部分等分成八个部分，(如图4所示)这样就构成了9个抽屉。 图（4）根据抽屉原理可知，存在两个点在同一个抽屉(包括边界)中，若这两个点在小圆(不包含边界)中，显然它们之间的距离小于2。若这两个点在圆环

22、部分的八个等分中的某一图形里，不妨设在图形中。由于 由此可知，这时两个点之间的距离也小于2，从而命题得证。 2.2.3 鸽巢原理应用于“人的相识”问题2例2231证明任意六个人中至少存在三个人或是互相认识，或是互相不认识。证明：在这六个人中任意取定一个人，则其余五个人可分为两类：=与认识的人，=与不认识的人。根据抽屉原理，和中至少有一个集合有3个人，不妨设此集合为，且对于集合中的3个人，来说，若他们彼此不认识，则问题得证。否则若，中有两个人互相认识，不妨假设这两个人是和，则，三个人互相认识。 若集合中至少有三个人，用类似的方法也可得到证明。 例2232在一个100人的聚会中，每个人都有偶数个(

23、有可能是0个)熟人，证明，在这次聚会上存在3个人有相同个数的熟人。 证明：根据题意，每个人所能认识的人数可能为：0，2，4，96，98。 在这个100人的聚会中，若这50种情况0，2，4，.，96，98都出现，我们假设第1个人认识。个人，第2个人认识2个人，第3个人认识4个人，依此类推，第50个人认识98个人，那么，在余下的50个人中，如果已知有两个人有相同个数的熟人，那么可以得到有3个人认识相同个数的人，问题得证。如果不知道是否还有两个人有相同、个数的熟人，我们来做下面的假设：剩下的50个人也是依次认识0，2，4，98个人，那么我们无法证出结论。现在我们来分析假设是否成立。根据以上推导和假设

24、，我们可以得到有两个人认识0个人，有两个人认识98个人，对于这两个认识0个人的人来说，他们自然也不认识那两个认识98个人的人，而对于那两个认识98个人的人来说，只能有一个人他们不认识，这就与有两个人都不认识他们矛盾，所以不可能出现两个认识0个人的人和两个认识98个人的人同时存在的情况，故假设不成立。 所以剩下的50个人中，最多只能出现认识0，2，4，98个人这50种情况的49种，根据鸽巢原理，必然有一种情况要重复。所以一共存在3个人有相同个数的熟人。 若在这l00个人的聚会中，只出现49种或更少的情况，那么根据鸽巢原理同样可以得到一定有3个人有相同个数的熟人。2.2.4 鸽巢原理应用于“连续时

25、间”问题4例2241某厂在五年期间的每一个月里至少试制一种新产品，每年最多试制19种新产品。试证明：一定存在连续的几个月，恰好试制24种新产品。 证明：设五年期间该厂各个月试制的新产品个数分别为，按题意，构造出数列的前项和的数列， ，则有：1=s60195=95，而序列+24，+24，+24，+24也是一个严格递增序列：25+24+24+24+2495+24=119于是，这120个自然数，和+24，+24，+24， +24都在区间内。在内，只有119个自然数，根据抽屉原理，必定存在两个数相等。 上述两个数列又分别是严格单调的，因此必然存在一个和，使得=+24。从而，该厂在从第+1个月起到第个月

26、的这几个月时间里，恰好试制了24种新产品。 例2242一个孩子每天至少看一个小时电视，总共看7周，但是每周看电视时间从不超过11小时。证明，存在连续若干天在此期间这个孩子恰好看电视20个小时。(假设这个孩子每天看电视时间为整数个小时)证明：设这个孩子7周内每天看电视的时间分别为，现在构造出数列的前项和的数列， ，则有：1=117=77，而序列+20，+20，+20也是一个严格递增序列：21+20+20+2077+20=97于是，这98个自然数， 和+20，+20，+20都在区间1，97内。而在1，97内，只有97个自然数，根据抽屉原理，必定存在两个数相等。而上述两个数列又分别是严格单调的，因此

27、必然存在一和，使得=+20。从而，这个孩子在第+1天起到第天的时间里，恰好看电视20个小时。 总结：凡遇此类问题都可按照上述方法进行证明。从上面两题的题目我们可以看出，问题中需要证明的数字(如上面的24和20)加上“在给定时间内能完成任务的最大数字”(如上面的95和77)恰好比“给定时间”的2倍少l。(如：(24+95)+1=602，(20+77)+1=492)。 这是该类问题最重要的特征，因为前两个数字之和恰好可以看成是抽屉数，而“给定时间”2可以看成是要被放人抽屉的元素数，抽屉数刚好比元素数少1，则有两个元素一定会放人同一个抽屉，通过鸽巢原理从而完成对问题的证明。如何构造“鸽巢”是解决此类

28、问题的关键所在。 2.2.5 鸽巢原理的其他应用1例2.251将1到67的正整数任意分成4部分，其中必有一部分至少有一个元素是某两个元素之差分析：设将1到67的整数任意分成4部分，分别为，。若这4部分中无一具有问题所指的性质，即其中至少有一元素是其中两个元素之差，结果导出矛盾，从而证明了问题的结论是正确的。（1）设1到67的整数中至少有个元素属于，并设这17个元素为。令，若中存在一个元素是某两个元素之差，则满足问题的要求。否则令，。令。显然，即的元素仍然是1到67之间的数。根据假定中无一属于，否则与假定中不存在一个元素等于某两个元素之差矛盾。所以的元素属于，或。（2） 与（1）的讨论项类似，设

29、中至少存在属于的个元素，设为。令。根据假定，中没有一个元素为某两个元素之差，令，。，所有的，。存在整数，使得故的元素不属于，同时不属于，只能属于或。（3）综上所述，中5个元素只能属于， 故根据鸽巢原理，设至少存在个元素属于，设为。令。根据假定，中不存在一个元素为某两个元素之差，令，显然，的元素不属于，而且。还可以证明对的元素，存在和及和，使得，这就证明了和既不属于也不属于，即的元素不属于，。故的元素属于。（4）但根据假定，令，则不属于，但，还可以证明不属于，即存在一个整数，不属于中任何一个，。这又和1到67之间任意分成4部分的假定相矛盾。例2.252 若序列的个元素是不相等的实数，则从中至少可

30、选出一组由个元素组合的或为单调增或为单调减的子序列。证明1 从序列中的每一个元素向后可选出若干个单调增子序列，其中有一个元素最多的单调子序列，设其元素个数为，。于是得一序列 若序列中有一个元素，则以符合问题要求。若不然，设不存在元素个数超过的单调增子序列，即， 这相当于把个球放到个盒子里。由于，根据鸽巢原理，存在个和，使得。不失一般性，不妨令，由于所有的是不同的实数，故对应的必须满足 如若不然，设，有，则可把元素加到从开始的长度为的单调增子序列的前面，构成从开始的长度为的单调增序列，这和是的最长增序列的假设矛盾。但序列本身第一个单调减子序列。这就证明了若不存在个元素的单调增子序列，便存在一个由

31、个元素的单调减子序列。同样的办法可证，若不存在元素个数为的单调减子序列，则必然努乃一个元素个数为的单调增子序列。证明2 对于序列中的每一个元素对应有一个数偶，是从开始自向后选出的单调增子序列中元素个数最多的子序列长度，是从开始自向后选出的单调减子序列中元素个数最多的子序列长度。于是对应于序列有 其中， 满足条件的数偶最多只有个，根据鸽巢原理，中至少有一对数偶，完全满足。即 ，或 由于序列的元素为不相等的实数，不妨设。若，则将导出，与相矛盾；若，则，与相矛盾。例2.253 某俱乐部有名成员。对每一个人，其余的人中恰好有个愿与他打网球，个愿与他自下象棋，个愿与他打乒乓球。证明该俱乐部至少有三个人，

32、它们之间玩的游戏三种俱全。3分析：将每个人作为平面上一点，且任何3点不共线。由每一点引出条红边、条蓝边、条黑边，分别代表打网球、下象棋、打乒乓球。问题等价于要证明图中至少有一个三边颜色全部相同的三角形。证明：考虑由这个点的所有连边构成的异边角（即两条异色的边构成的角）的综述。每个顶点处有个异色角，所以平均每个三角形有个异色角。因此，至少有一个三角形有3个异色角，那么，这个三角形的三条边当然互不同色。第3章 Ramsey问题2Ramsey理论起始于20世纪20年代末、30年代初，最初由英国数学家F.P.Ramsey提出。其思想已日益被人们理解、接受并得到了一定的完善。Ramsey定理的原始形式已

33、经在许多方向上得到了延伸，并最终形成了Ramsey理论：一个揭示深层数学原理的理论，它从很大程度上推广了鸽笼原理（也叫做广义鸽巢原理）,并告诉我们无论以什么方式将一个庞大的体系分解成一些小的部分，其中必定存在一个小的子体系。尽管Dirichlet的鸽笼原理已经保证了无论物体之间的关系如何，我们都能够得到许多类型相同的物体，然而我们在Ramsey理论中寻找的是相同类型的子结构：我们不仅想要得到无穷多的红边，而且我们还想得到与这个红的无穷集相关联的点双方组成的结构。下面只是简单介绍一下Ramsey的有关问题。3.1 Ramsey问题设平面上有个点，任意三点都不共线，将这些点两两之间连一线段，构成的

34、图形称为完全图，记为。提法一：经观察，在6个或6个以上的人群中，必有3人互相认识，或有3人彼此不认识。而将人数降到5个或更少时，此有趣的现象就可能消失。于是6成为具有这一特性的最小人数。提法二：当时，若对的每一条边随意涂以红、蓝两色之一，那么，上至少可以找到一个同色。而当时，至少可以给出一种涂法，使得上不存在同色。如图（5）所示，当时，按图中的涂法，是不存在同色的（其中实现表示蓝色，虚线表示红色）。 图（5）提法三：设集合，令（即上所有二元子集类），再用表示的一个二分拆（即，可空）。那么，当时，对集合中的元素，下面结论至少有一个成立：（1） 存在3个元素，其全部二元子集都属于；（2） 存在3个

35、元素，其全部二元子集都属于。而当时，结论未必成立。三种提法各有利弊，提法一比较直观，提法二便于分析，提法三有益于理论推广。 证明：在完全图中任取一个顶点记为，由鸽巢原理，以为端点的5条边至少有3条是同色的。不妨设边，都为红色，先考虑连接，的3条边，若这条边全为蓝色，则就是一个蓝色三角形。否则，3条边中至少有一个为红色（假设为），则就是一个红色三角形。命题得证。3.2 Ramsey问题的一般化将顶点数扩大，例如，用红蓝两色对的边着色，则必出现同色的或同色的，但对着色则不能保证有上述结果；对而言，存在同色的或；对的边涂以红蓝两色，则存在同色的，那么，对，能否存在同色呢？引理321 若将涂以红蓝两色

36、，则必存在一个顶点，从此点引出的8条线段中，同色的线段或多于3条，或少于3条。证明（反证法）：假如不存在这样的顶点，记从每一顶点发出的线段中，红色（蓝色）线段都是3条，现在对9个顶点逐点 统计有它们发出的红色（蓝色）线段的条数，应为27条。另一方面，设中实有红色（蓝色）线段共条，现在对这条边的每个断电逐点统计有它们发出的红色（蓝色）线段的条数，由于每条线段有两个端点，故应为。于是得出，与为整数矛盾。引理得证。定理321若将涂以红蓝两色，则必出现同色的或同色的。证明：（1）从引出的8条线段中，红色线段多于3条，即至少有4条，不妨设为，再看出这4个顶点构成的，若其中有一条红边，则它的两个端点与便构

37、成一个红色的，否则，该的所有的边全为蓝色，既存在同色。（2）若红色线段少于3条，那么，从引出的蓝色线段至少有6条，不妨设为，再看由，这6个顶点构成的，由前述结论，中必有一个同色，若是红色的，结论已真；若为蓝色，则该的3个顶点与一起便构成一个蓝色，结论亦真。当时，可以给出一种涂法，使得染色后的中既无实线，由无虚线。如图（6）所示： 图（6）结论通过近四个月的努力，论文终于完成了。在过去的几个月里，我独立的找寻资料，分析、整理资料，并对有用的部分加以概括。然后根据资料确定写作方向，并列了论文提纲。在大纲的指导下，如期完成了论文。通过写论文的过程，我对鸽巢原理有了更深的认识。以前我一直鸽巢原理单纯只

38、是一个规律，没有任何作用。通过学习，我知道是组合数学中两大基本原理之一，是一个简单而又应用广泛的数学原理。其道理并无深奥之处，且正确性也很明显。但是若能灵活应用，便可能得到一些意想不到的结果。但由于时间有限，论文地层次不高，有很大的提升空间。望老师批评指正。参考文献1 卢开澄、卢华明，组合数学，第四版，北京：清华大学出版社，2007，(09)。2 姜建国、越建国，组合数学，西安：电子科技大学出版社，2003，（09）。3 李乔，组合数学基础，北京：高等教育出版社，1993，（03）。4 杨振生，组合数学，合肥：中国科技技术大学出版社，2003，（04）。5 何春，万琳，任雅莉， 鸽巢原理及其应

39、用，计算机与数字工程，2007，(08)。6 储一民， 鸽巢原理的妙用，科技信息，2008， (33)。7 蒋洪， 关于鸽巢原理和Ramsey定理的几个结论，科教文汇(中旬刊)，2008， (11) 。8 石立叶，于娜，刘文菡，抽屉原理及其应用， 今日科苑， 2009，(17)。9 唐善刚， 广义容斥原理的应用， 佳木斯大学学报(自然科学版)， 2010，(04)。10 邬毅，于静静，容斥原理的应用， 西安文理学院学报(自然科学版)， 2010，(02)。11 李申艳，叶权波， 容斥原理在数论中的应用，魅力中国， 2010， (13) 。12 崔军， 容斥原理及其简单应用，新疆广播电视大学学报

40、，2006，(04) 。13 许康华，黄庆学，Ramsey定理的一种推广，浙江大学学报(理学版)，2002，(06)。14 兰社云，高喜梅，浅谈抽屉原理及抽屉构造， 河南教育学院学报(自然科学版)，2003，（02）。15 M. Garden, Mathematical Games, Scientific American, February (1973), pp. 108-11216 E. Mead, A Rose, C, Huang, The Game of SIM: A Winning Strategy for the Second Player, Mathematical Report

41、 No. 58, 1973, McMaster University.17 L.E.Shader, Another Strategy for SIM, Mathematics Magazine, Vol. 51. No. 1, pp. 60-62, 1978.18 G. J. Simmons, The Game of SIM, Journal of Recreational Mathematics, 1969.致谢我再写毕业论文期间，孙老师对我的工作进行了全面、具体的指导。孙老师渊博的学识、敏锐的思维、民主而严谨的作风是我受益匪浅，并终生难忘。感谢于老师、高老师，在进行毕业论文工作中所给予的帮助。感谢资料室的老师的关心和帮助。感谢我的学友和朋友们对我的关心和帮助。