高中数学竞赛讲座---简单的染色问题

ADBCABFCDAE简单的染色问题在我们美丽的地球上，有60多亿人口，任何六个人聚在一起，或者有三个人彼此相识，或者有三个人彼此不相识。你相信吗？那就先让我们来作个游戏！规则：正六边形的六个顶点，两游戏者每次可随意．．选用红或蓝色的笔，轮流．．选择其中的两点连线，谁第一个被迫画成一个同色的三角形（红色或白色），他就是失败者．这个游戏是否一定能分出胜负呢？与先下后下是否有关？抽象数学问题：把六个点（任意三点不共线）的连线染两色，至少会出现一个同色三角形．证明：任取一点A，那么由点A引出的5条边中，由抽屉原理，至少有三条是同色的，不妨设AB、AC、AD是蓝色的，如图所示．考察BC、BD、CD三条边，若这三条边中有一条是蓝色的，则与A形成一个蓝色三角形；若这三条边都是红色的，则三角形BCD为一个红色三角形．“任何六个人聚在一起，或者有三个人彼此相识，或者有三个人彼此不相识”这样一个著名的实际问题也就迎刃而解．1928年，在英国伦敦数学会的一次学术会议上，年仅24岁的年轻数学家弗兰克·普拉东·拉姆赛（FrankPlumptonRamsey）证明了一个定理：如果某一集合（如点集）中事物的数量足够多，且每对事物间都存在一定数量的关系（如各种颜色的边）中的一种，那么必定存在一个包含若干数目事物的子集（如三点集），其中每对事物间也存在同样的关系（如同色三角形）．这个定理称为拉姆赛定理，告诉我们：如果平面上的点数足够多，且每对点间的线（边）或染红色或染蓝色，那么必定存在一个包含3个点的子集，他们之间的边同色，即包含一个同色三角形．如果我们将刚才的六点染色游戏继续下去，染完所有的线段，同色三角形最少出现了几个？这是偶然吗？恭喜你！答对了，2个！在六点（任意三点不共线）染色游戏中，必有两个同色三角形．证明：方法一：为方便叙述，我们把平面上有n个点，每两点都有连线的图称为n阶完全图，记作nK．由拉姆赛定理知把6K边染红、蓝两色，必出现一个同色三角形，不妨设这个三角形是红色的ABC．现考虑△ABC以外的点D、E、F，由D引出的五条边中，由抽屉原理，至少有三条边是同色的，除了D与A、B、C所连的边是蓝色的情形以外，其余情形均可仿照结前面的证明得到一个同色三角形；同理，E、F引出的边也有同样的结论．于是，只剩下如图情形，即D、E、F与△ABC的三顶点连线均是蓝色．这时，三角形DEF或者是红色三角形，或者与原来的蓝边形成一个蓝色三角形．方法二（算两次）：考虑自同一点引出的两条边，如果他们颜色相同，就称他们组成一个“同色角”，设自点A引出r条红边，5－r条白边，则自A点引出的同色角共有（252rrCC）个，易知当r＝2或3时252rrCC最小，最小值为4，所以该六点图中至少有6×4＝24个同色角；另一方面，每个同色三角形中有3个同色角，每个边不全同色的三角形中只有1个同色角．设同色三角形有x个，则不同色三角形有（xC36）个，因此，同色角共有xxCx20)(336个．综上，2420x，从而，2x．如果减少一点，做五点（任意三点不共线）染色游戏是否一定能分出胜负呢？如出现平局，平局的图形是什么样的呢？读者不妨动手一试，在五点染色游戏中，或者必出现一个同色三角形，或者必出现一个同色五边形（首尾顺次连接即可）．如将上述一类问题推广，可在哪几方面进行变化？请读者思考．例1.在2色完全图9K中，至少存在一个红色三角形或一个蓝色四边形．证明：如果9K中有一个点1v引出至少4条红边，不妨设12131415,,,vvvvvvvv为红边，这时2345,,,vvvv四个点所成的4K中或者每条边都是蓝色，或者至少有一条边为红色．在后一种情况，设红边为23vv，则123vvv为红色三角形．如果9K中每个点引出的红边少于4条，那么每点至少引出5条蓝边．由于蓝边的总数的2倍5945，所以，蓝边的总数的2倍46，从而至少有一点1v引出6条蓝边．设121314151617,,,,,vvvvvvvvvvvv121314151617,,,,,vvvvvvvvvvvv为蓝边，这时234567,,,,,vvvvvv所成的6K中必有一个同色三角形．如果是红色三角形，结论成立；如果是蓝色三角形，那么它的三个顶点与1v构成蓝色的4K．例2.（2005西部）设n个新生中，任意3个人中有2个人互相认识，任意4个人中有2个人互不认识，试求n的最大值．解：当8n时，如图所示的例子满足要求，其中12345678,,,,,,,AAAAAAAA表示8个学生，红色表示认识．下设n个学生满足题设要求，证明8n．为此先证明如下两种情况不可能出现．（1）若某人A至少认识6个人，记为123456,,,,,BBBBBB，由拉姆赛定理，这6个人中或者有3个人彼此不相识，与已知任意3个人中有2个人认识矛盾；或者有3个人彼此相识，这时与这3个人共4个人互相认识与已知任意4个人中有2个人互不认识矛盾！（2）若A至多认识5n个人，则剩下至少4个人均与A互不认识，从而与这4个人两两相识，矛2A3A1A4A5A6A7A8A盾！其次，当10n时，（1）与（2）必有一种情况出现，故此时不满足要求．当9n时，要使（1）与（2）均不出现，则此时每个人恰好认识其他5个人．于是，这9个人产生的朋友对的数目为952N，矛盾！综上，所求n的最大值为8．例2.（第六届IMO）17位学者，每一位都给其余的人写一封信，信的内容是讨论三个问题中的一个．而且两个人互相通信所讨论的是同一个问题。证明：至少有三位学者，他们之间通信所讨论的是同一个问题．证明：作完全图17K，它的17个点(1,2,,17)ivi分别表示17位科学家.设他们讨论的题目为,,xyz,两位科学家讨论x连红线,讨论y连蓝线,讨论z连黄线.于是只须证明这个17K中有一同色三角形.任取一点1v，自1v引出的边共16条，因而一定有1663条边同色，不妨设12,vv1314151617,,,,vvvvvvvvvv为红色.234567,,,,,vvvvvv构成的完全图6K中，如果有一条边23vv也是红色，则123vvv为红色三角形；如果这个6K中没有红色边，只有蓝色和黄色，由拉姆赛定理知一定存同色三角形（蓝色或黄色）.例3.两个航空公司为十个城市通航，使得任意两个城市之间恰有一个公司开设直达航班的往返服务，证明：至少有一个公司能提供两个不相交的旅游圈，每圈可游览奇数个城市．证明：在完全图中10个顶点中取出6个点，由拉姆赛定理知，这6点组成的6K的边染两色至少有一个同色三角形，不妨记为123AAA．由余下的7个点组成的7K中也至少存在一个同色三角形，记为123BBB．当然，123AAA与123BBB是没有公共点的，如果他们同色，则结论成立．因此仅需考虑不同色的情形．不妨设123AAA为红色三角形，而123BBB为蓝色三角形，这两个三角形之间还有9条边111213212223313233,,,,,,,,ABABABABABABABABAB，这9条边染两色，至少有5条边是同色的，不妨设有5条蓝边．因此，在123,,AAA中，至少有一个点，它引出两条蓝边，不妨设1112,ABAB是蓝边．于是我们得到红色123AAA和蓝色112ABB．于是除了这两个红、蓝三角形（123AAA和112ABB）外，还剩5个点，我们把这5个点记作12345,,,,CCCCC（其中有一个点曾经称为3B）．现在考虑由12345,,,,CCCCC所成的5K，若这个5K中有同色三角形，则此三角形和123AAA、112ABB都无公共点，且必与其中之一同色，结论成立；若这个5K中无同色三角形，由前面的5点染色游戏知，必有一个同色五边形，它与123AAA、112ABB无公共点．于是出现两个同色奇数圈．由于染色问题主要涉及集合元素的分类，与自然数n密切相关，因此在处理手法上不能仅限于上面提到的，数学归纳法也就不乏用武之地了．例4.（第29届俄罗斯数学奥林匹克）某国有N个城市，每两个城市之间或者有公路，或者有铁路相连．一个旅行者希望到达每个城市恰好一次，并且最终回到他所出发的城市．证明：该旅行者可以挑选一个城市作为出发点，不但能够实现他的愿望，而且途中至多变换一次交通工具的种类．证明：问题可以转化为，给定一个完全图nK，对它的边染两种不同的颜色．证明，从中可以找到一个经过所有顶点的圈，该圈至多可以分为两个各自同色的部分．对N用数学归纳法．当3N时，命题显然成立；假设Nk时命题成立，考虑1Nk的情形．先从所考察的图中去掉一个顶点M及所有从它出发的边．由归纳假设知，在剩下的完全图kK中存在一个经过所有顶点的圈．该圈之多可以分为两个各自同色的部分．下面分两种情形讨论：（1）该圈上的所有边全都同色．依次将圈上的顶点记为12,,kAAA．从中去掉边12AA，然后将顶点M分别与1A、2A相连，所得的圈即符合要求．（2）该圈上的所有边不全同色．将顶点编号，使得对某个顶点mA，圈上由1A到mA的部分12mAAA为一种颜色（红色），11mmkAAAA为另一种颜色（蓝色）．只要观察边mMA的颜色：如果该边为红色，则圈1211mmkAAAMAAA为所求；如果该边为蓝色，则圈1211mmkAAAMAAA为所求．这就表明，对于命题1Nk也成立．例5.（第30届俄罗斯数学奥林匹克）某国有若干个城市和k个不同的航空公司．任意2个城市之间，或者有1条属于某个航空公司的双向的直飞航线连接，或者没有航线连接．已知任意2条同一公司的航线都有公共的端点.证明：可将所有的城市分为2k个组，使任意2个属于同一组的城市之间都没有航线相连．证明：对k进行数学归纳．当0k时，没有航空公司，结论显然成立．作一个凸多边形，其中的顶点为该国的城市，边为航线。分别以(1,2,)iEik表示各个航空公司的航线所对应的边的集合，由已知条件，易知对于每个集合(1,2,)iEik或者为三角形，或者为“花”，即具有一个公共顶点的若干条边．如果存在一个集合jE是以顶点A为公共顶点的“花”，那么，就从图中去掉顶点A和所有由A所连出的边．于是在剩下的图中只有1k家航空公司的航线．根据归纳假设，可以把所有的顶点分成1k组，使得任意任意2个属于同一组的城市之间都没有航线相连．再把A作为第2k组即可．如果所有的(1,2,)iEik都是三角形，此时图中恰好有3k条边，我们只需将图中的顶点分为尽可能少的组，使得任意2个属于同一组的顶点之间都没有边相连即可．否则假设所分出的组为12,,,nBBB，且3nk．注意到，此时在任何两个组iB和jB之间，都一定有某条边联结iB和jB中的某2个顶点，若不然，就可以把两个组并成一组．从而，该图中至少有2nC条边，这样一来，就有2(3)(2)32nkkCk，矛盾．所以，原结论成立．