从而存在c∈R,使或.
即方程ax=b在R中有解.
根据定理,R是除环.
由魏得邦定理,原命题得证.
4.抽屉原理在实际生活中的应用
抽屉原理不仅在高等数学中具有广泛应用,在我们的实际生活中,也能处处发现抽屉原理的影子.如招生录取、赛程安排、资源分配、职称评定等等,都不难看到抽屉原理的作用.
其实早在中国古代的春秋战国时期就有了运用抽屉原理的例子,那就是《晏子春秋》中的“二桃杀三士”的典故,将两个桃子赏赐给三名勇士,在这里可以将桃子看作抽屉,三个人作为元素放进抽屉,则根据抽屉原理,一定有一个抽屉要放入两个或两个以上的元素,回到问题情境中就是一定要有两个人吃一个桃子,导致这三名勇士最后自相残杀而亡,这就是著名的“二桃杀三士”.
后来宋朝时期费衮在他的《梁谿漫志》中就曾运用抽屉原理来驳斥但是流行的“算命”一说,费衮指出算命是把一个人出生的年、月、日、时作为依据,把这些作为“抽屉”,则不同的抽屉有12×360×60=259200个.把所有的人作为“物品”,则进入同一抽屉的人有成千上万个,因此“生时同者必不为少矣”.既然“八字”相同,“又何贵贱贫富之不同也?
这是大基数的社会现象,常给人感觉世事很奇巧,碰到同生日、同名的人,这也是抽屉原理在生活中的应用.而生活中也有常见的抽屉原理的应用之处,如“抢凳子”游戏,一群人抢凳子,凳子数比人少,必然淘汰一些人,又或者是13个人中总有2人是同一个月份出生,52张扑克牌中取出5张总有2张花色相同,在100米长的小路上种101棵小树,不管怎么种,至少有两棵树苗之间的距离不超过1米等等.
下面我们再来看几个例子.
例10.有11名学生到老师家借书,老师是书房中有A、B、C、D四类书,每名学生最多可借两本不同类的书,最少借一本.试证明必有两个学生所借的书的类型相同.
证明
若学生只借一本书,则不同的类型有A、B、C、D四种;若学生借两本不同类型的书,则不同的类型有=6种,即AB、AC、AD、BC、BD、CD.共有10种类型.
把这10种类型看作10个“抽屉”,把11个学生看作11个“物品”.那个学生借了哪种类型的书,就将其放入对应的那个抽屉里.
根据抽屉原理,.所以,至少有两个学生所借的书类型相同.
例11.体育用品仓库里有许多足球、排球和篮球,某班50名同学来仓库拿球,规定每个人至少拿1个球,至多拿2个球,问至少有几名同学所拿的球种类是一致的?
解
首先来看具体的拿球的配组方式,有以下9种:
{足},{排},{篮},{足,足},{排,排},{篮,篮},{足,排},{足,篮},{排,篮}.
把这9种配组方式看作9个抽屉,则根据抽屉原理,有
所以至少有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则不公平.
答案是.
证明
因,所以分两种情况讨论.
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支球队比赛时,若安排的赛程使各队每两场比赛中间至少相隔场,则该赛程称为完美赛程.
5.抽屉原理的推广定理-Ramsey定理
曹汝成编著的《组合数学》教科书中指出,应用抽屉原理虽然可以解决许多涉及存在性的组合问题,但对于一些更加复杂的有关存在性的组合问题,抽屉原理显得无能为力,这时我们就需要运用抽屉原理的推广定理Ramsey定理来解决问题,下面我们就来探讨抽屉原理在应用上的不足.
Ramsey(1903-1930)是英国数理逻辑学家,他把抽屉原理加以推广,得出广义抽屉原理,也称为Ramsey定理.
Ramsey定理设p,q是正整数,p,q>2,则存在最小正整数R(p,q),使得当n>R(p,q)时,用红蓝两色涂的边,则或存在一个蓝色的,或存在一个红色的.
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个顶点的完全图任意进行红、蓝两边着色,都存在一个红色三角形或蓝色三角形.
证明如下
首先,把这6个人设为A、B、C、D、E、F六个点.由A点可以引出AB、AC、AD、AE、AF五条线段.
设如果两个人认识,则设这两个人组成的线段为红色;如果两个人不认识,则设这两个人组成的线段为蓝色.
由抽屉原则可知这五条线段中至少有三条是同色的.不妨设AB、AC、AD为红色.若BC或CD为红色,则结论显然成立.
若BC和CD均为蓝色,则若BD为红色,则一定有三个人相互认识;若BD为蓝色,则一定有三个人互相不认识.
上述的Ramsey问题等价于下面的命题1.
命题1.对6个顶点的完全图任意进行红、蓝两边着色,都存在一个红色三角形或蓝色三角形.
命题1运用抽屉原理可以很容易很简便地对其进行证明.现将命题1推广成下面的命题2.
命题2.对六个顶点的完全图任意进行红、蓝两边着色,都至少有两个同色三角形.
由于命题2是要证明至少存在两个同色三角形的问题,而抽屉原理一般只局限在证明至少存在一个或必然存在一个的问题,所以对于上述命题抽屉原理就显得无能为力,这时需要运用Ramsey定理来解决问题.
证明设是的六个顶点,由上面的命题1可知,对任意进行红、蓝两边着色都有一个同色三角形,不妨设△是红色三角形.以下分各种情况来讨论
(1)若均为蓝边,如图1所示,则若之间有一蓝边,不妨设为,则三角形△为蓝色三角形;否则,△为红色三角形.
图1图2
(2)若中有一条红边,不妨设为红边,此时若边中有一条红边,不妨设是红边,则△是一红色三角形,见图2.
以下就均为蓝边的情况对与相关联的边的颜色进行讨论.
(ⅰ)若中有一蓝边,不妨设为蓝边,如图3,此时,若均为红边,则△是红色三角形;否则,△或△是蓝色三角形.
(ⅱ)若均为红边,见图4,此时,若之间有一条红边,不妨设为红边,则△为红色三角形;否则,△为蓝色三角形.
图3图4
由以上对各种情况的讨论知,对的任意红、蓝两边着色均有两个同色三角形.
从以上例子可知,抽屉原理在应用上确有不足之处,之上只是个特例,至于在别的领域中的不足之处还需我们进一步的探索.
抽屉原理的应用领域十分广泛,涉及到高等数学的多个学科,并且在生活中也有广泛的应用,可以巧妙的用于解决一些复杂问题,本文主要梳理总结了它在数论、离散、高等代数及抽象代数中的应用,其不足之处也由Ramsey定理进行了补充,使其能够更好的应用与问题解决当中.
6.参考文献
[1]陈景林,阎满富.组合数学与图论.北京中国铁道出版社出版,2000.04
[2]卢开澄.组合数学(第3版).北京清华大学出版社,2002.07
[3]濮安山.“高等代数中抽屉原理的应用”.《哈师大自然科学学报》,2001.06
[4]王向东,周士藩等.高等代数常用方法[M].1989.11.
[5]杨子胥.近世代数.北京.高等教育出版社.2003.12
[6]严士健.抽屉原则及其它的一些应用[J].数学通报,1959