大学数学本科毕业论文--抽屉原理(4)

把这9种配组方式看作9个抽屉,则根据抽屉原理，有 ?50??9??1?6?? 所以至少有6名同学所拿的球的种类是完全一样的. 例12.你所在的年级有5个班，每班一支球队在同一块场地上进行单循环赛, 共要进行10场比赛. 则各队每两场比赛中间至少隔多少场才最公平呢？

下面是随便安排的一个赛程: 记5支球队为A, B, C, D, E，在下表左半部分的右上三角的10个空格中, 随手填上1,2,?，10, 就得到一个赛程, 即第1场A对B, 第2场B对C,?, 第10场C对E. 表的右半部分是各队每两场比赛间相隔的场次数, 显然这个赛程对A, E有利, 对D则不公平.

?n?1?答案是??2. ?2??证明

?m?2,当n?2m时?n?1?因?，所以分两种情况讨论. ?2????2??m?1,当n?2m?1时1）当n=2m为偶数时，这2m支球队为0，1，2，?，（2m-1）.顺次安排（m+1）场比赛需要2（m+1）支球队参赛，由抽屉原理，必然有重复出现的球队，由单循环赛知，重复出现的球队中一定存在某球队.其两场比赛中间相隔的场次数最多为m-2.

2)当n=2m+1为奇数时，这2m+1支球队为0,1,2,?,2m.顺次安排（m+1）场比赛需要2（m+1）支球队参赛，由抽屉原理，必然有重复出现的球队，其两场比赛中间相隔的场次数最多为m-1.

因此，当n支球队比赛时，若安排的赛程使各队每两场比赛中间至少相隔

?n?1??2场，则该赛程称为完美赛程. ??2??5.抽屉原理的推广定理－Ramsey定理

曹汝成编著的《组合数学》教科书中指出，应用抽屉原理虽然可以解决许多涉及存在性的组合问题,但对于一些更加复杂的有关存在性的组合问题，抽屉原理显得无能为力，这时我们就需要运用抽屉原理的推广定理Ramsey定理来解决

12

问题，下面我们就来探讨抽屉原理在应用上的不足.

Ramsey(1903-1930)是英国数理逻辑学家,他把抽屉原理加以推广，得出广义抽屉原理，也称为Ramsey定理.

Ramsey定理设p,q是正整数，p,q>2,则存在最小正整数R(p,q),使得当n>R(p,q)时，用红蓝两色涂Kn的边，则或存在一个蓝色的Kp,或存在一个红色的Kp.

Ramsey定理（狭义）的内容任意六个人中要么至少三个人认识，要么至少三个不认识.

Ramsey定理可以视为抽屉原理的推广，1947年，匈牙利数学家把这一原理引进到中学生数学竞赛中，当年匈牙利全国数学竞赛有一道这样的试题：“证明：任何六个人中，一定可以找到三个互相认识的人，或者三个互不认识的人.” 在1958年6-7月号美国《数学月刊》同样也登载着这样一个有趣的问题“任何六个人的聚会，总会有3人互相认识或3人互相不认识.”这就是著名的Ramsey问题.

这个问题乍看起来，似乎令人匪夷所思.但如果懂得抽屉原理，要证明这个问题是十分简单的： 我们用A、B、C、D、E、F代表六个人，从中随便找一个，例如A吧，把其余五个人放到“与A认识”和“与A不认识”两个“抽屉”里去，根据抽屉原理，至 少有一个抽屉里有三个人.不妨假定在“与A认识”的抽屉里有三个人，他们是B、C、D.如果B、C、D三人互不认识，那么我们就找到了三个互不认识的人； 如果B、C、D三人中有两个互相认识，例如B与C认识，那么，A、B、C就是三个互相认识的人.不管哪种情况，本题的结论都是成立的.

或者我们可以用染色的方法.以6个顶点分别代表6个人，如果两人相识，则在相应的两点间连一条红边，否则在相应的两点间连一蓝边.

命题1.对6个顶点的完全图K6任意进行红、蓝两边着色，都存在一个红色三角形或蓝色三角形.

证明如下

首先，把这6个人设为A、B、C、D、E、F六个点.由A点可以引出AB、AC、AD、AE、AF五条线段.

设如果两个人认识，则设这两个人组成的线段为红色；如果两个人不认识，则设这两个人组成的线段为蓝色.

由抽屉原则可知这五条线段中至少有三条是同色的.不妨设AB、AC、AD为红

13

色.若BC或CD为红色，则结论显然成立.

若BC和CD均为蓝色，则若BD为红色，则一定有三个人相互认识；若BD为蓝色，则一定有三个人互相不认识.

上述的Ramsey问题等价于下面的命题1.

命题1.对6个顶点的完全图K6任意进行红、蓝两边着色，都存在一个红色三角形或蓝色三角形.

命题1运用抽屉原理可以很容易很简便地对其进行证明.现将命题1推广成下面的命题2.

命题2.对六个顶点的完全图K6任意进行红、蓝两边着色，都至少有两个同色三角形.

由于命题2是要证明至少存在两个同色三角形的问题，而抽屉原理一般只局限在证明至少存在一个或必然存在一个的问题，所以对于上述命题抽屉原理就显得无能为力，这时需要运用Ramsey定理来解决问题.

证明 设v1,v2,v3,v4,v5,v6是K6的六个顶点，由上面的命题1可知，对K6任意进行红、蓝两边着色都有一个同色三角形，不妨设△v1v2v3是红色三角形.以下分各种情况来讨论

(1)若v1v4,v1v5,v1v6均为蓝边，如图1所示，则若v4,v5,v6之间有一蓝边，不妨设为v4v5，则三角形△v1v4v5为蓝色三角形；否则，△v4v5v6为红色三角形.

图1 图2

(2)若v1v4,v1v5,v1v6中有一条红边，不妨设v1v4为红边，此时若边v2v4,v3v4中有一条红边，不妨设v3v4是红边，则△v1v3v4是一红色三角形，见图2.

以下就v2v4,v3v4均为蓝边的情况对与v4相关联的边的颜色进行讨论. (ⅰ)若v4v5,v4v6中有一蓝边，不妨设v4v5为蓝边，如图3，此时，若v2v5,v3v5均为红边，则△v2v3v5是红色三角形；否则，△v2v4v5或△v3v4v5是蓝色三角形. (ⅱ)若v4v5,v4v6均为红边，见图4，此时，若v1,v5,v6之间有一条红边，不妨

14

设v1v5为红边，则△v1v4v5为红色三角形；否则，△v1v5v6为蓝色三角形.

图3 图4

由以上对各种情况的讨论知，对K6的任意红、蓝两边着色均有两个同色三

角形.

从以上例子可知，抽屉原理在应用上确有不足之处，之上只是个特例，至于在别的领域中的不足之处还需我们进一步的探索.

抽屉原理的应用领域十分广泛，涉及到高等数学的多个学科，并且在生活

中也有广泛的应用，可以巧妙的用于解决一些复杂问题，本文主要梳理总结了它在数论、离散、高等代数及抽象代数中的应用，其不足之处也由Ramsey定理进行了补充，使其能够更好的应用与问题解决当中.

15

6.参考文献

[1]陈景林,阎满富.组合数学与图论.北京中国铁道出版社出版,2000.04 [2]卢开澄.组合数学（第3版）.北京清华大学出版社，2002.07

[3]濮安山.“高等代数中抽屉原理的应用”.《哈师大自然科学学报》，2001.06 [4]王向东,周士藩等.高等代数常用方法[M].1989.11. [5]杨子胥.近世代数.北京.高等教育出版社.2003.12 [6]严士健.抽屉原则及其它的一些应用[J].数学通报,1959 [7]曹汝成.组合数学[M].华东理工大学出版社,2000.

16

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库大学数学本科毕业论文--抽屉原理(4)在线全文阅读。