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

简单的染色问题

在我们美丽的地球上，有60多亿人口，任何六个人聚在一起，或者有三个人彼此相识，或者有三个人彼此不相识。你相信吗？那就先让我们来作个游戏！规则：正六边形的六个顶点，两游戏者每次可随意．．选用红或蓝色的笔，轮流选择其中的两点连线，谁第一个被迫画成一个同色的三角形（红色或白色），他．．就是失败者．这个游戏是否一定能分出胜负呢？与先下后下是否有关？

抽象数学问题：把六个点（任意三点不共线）的连线染两色，至少会出现一个同色三角形． 证明：任取一点A，那么由点A引出的5条边中，由抽屉原理，至少有三条是同色的，不妨设AB、AC、AD是蓝色的，如图所示．考察BC、BD、CD三条边，若这三条边中有一条是蓝色的，则与A形成一个蓝色三角形；若这三条边都是红色的，则三角形BCD为一个红色三角形．

“任何六个人聚在一起，或者有三个人彼此相识，或者有三个人彼此不相识”这样一个著名的实际问题也就迎刃而解．

1928年，在英国伦敦数学会的一次学术会议上，年仅24岁的年轻数学家弗兰克·普拉东·拉姆赛（Frank Plumpton Ramsey）证明了一个定理：如果某一集合（如点集）中事物的数量足够多，且每对事物间都存在一定数量的关系（如各种颜色的边）中的一种，那么必定存在一个包含若干数目事物的子集（如三点集），其中每对事物间也存在同样的关系（如同色三角形）．这个定理称为拉姆赛定理，告诉我们：如果平面上的点数足够多，且每对点间的线（边）或染红色或染蓝色，那么必定存在一个包含3个点的子集，他们之间的边同色，即包含一个同色三角形．

如果我们将刚才的六点染色游戏继续下去，染完所有的线段，同色三角形最少出现了几个？这是偶然吗？恭喜你！答对了，2个！在六点（任意三点不共线）染色游戏中，必有两个同色三角形．

证明：方法一：为方便叙述，我们把平面上有n个点，每两点都有连线的图称为n阶完全图，记作Kn．由拉姆赛定理知把K6边染红、蓝两色，必出现一个同色三角形，不妨设这个三角形是红色的ABC．现考虑△ABC以外的点D、E、F，由D引出的五条边中，由抽屉原理，至少有三条边是同色的，除了D与A、

A F B、C所连的边是蓝色的情形以外，其余情形均可仿照结前面的证明得到一个同色三角形；同理，E、F引出的边也有同样的结论．于

B E 是，只剩下如图情形，即D、E、F与△ABC的三顶点连线均是蓝色．这时，三角形DEF或者是红色三角形，或者与原来的蓝边形成

C D

C

B

D

A 1

一个蓝色三角形．

方法二（算两次）：考虑自同一点引出的两条边，如果他们颜色相同，就称他们组成一个“同色角”，设

2自点A引出r条红边，5－r条白边，则自A点引出的同色角共有（Cr2?C5?r）个，易知当r＝2或3时24＝24个同色角；另一方面，每个同色三角形中Cr2?C5?r最小，最小值为4，所以该六点图中至少有6×

有3个同色角，每个边不全同色的三角形中只有1个同色角．设同色三角形有x个，则不同色三角形有

33（C6?x）个，因此，同色角共有3x?(C6?x)?20?x个．综上，20?x?24，从而，x?2．

如果减少一点，做五点（任意三点不共线）染色游戏是否一定能分出胜负呢？如出现平局，平局的图形是什么样的呢？读者不妨动手一试，在五点染色游戏中，或者必出现一个同色三角形，或者必出现一个同色五边形（首尾顺次连接即可）．如将上述一类问题推广，可在哪几方面进行变化？请读者思考． 例1. 在2色完全图K9中，至少存在一个红色三角形或一个蓝色四边形．

证明：如果K9中有一个点v1引出至少4条红边，不妨设v1v2,v1v3,v1v4,v1v5为红边，这时v2,v3,v4,v5四个点所成的K4中或者每条边都是蓝色，或者至少有一条边为红色．在后一种情况，设红边为v2v3，则vvv123为红色三角形．如果K9中每个点引出的红边少于4条，那么每点至少引出5条蓝边．由于蓝边的总数的2倍?5?9?45，所以，蓝边的总数的2倍?46，从而至少有一点v1引出6条蓝边．设v1v2,v1v3,v1v4,v1v5, v1v,vvv,vv,vv5,v1v6,v1v7为蓝边，这时v,v,v,v,v,v所成的K中必有一个同色三角形．如果是红色三角形，结论成立；

6234567如果是蓝色三角形，那么它的三个顶点与v1构成蓝色的K4．

例2. （2005西部）设n个新生中，任意3个人中有2个人互相认识，任意4个人中有2个人互不认识，试求n的最大值．

解：当n?8时，如图所示的例子满足要求，其中表示8个学生，红色表示认A1,A2,A3,A4,A5,A6,A7,A8识．下设n个学生满足题设要求，证明n?8．为此先证明如下两种情况不可能出现．（1）若某人A至少认识6个人，A3记为B1,B2,B3,B4,B5,B6，由拉姆赛定理，这6个人中或者有3个人彼此不相识，与已知任意3个人中有2个人认识

矛盾；或者有3个人彼此相识，这时与这3个人共4个人互相认识与已知任意4个人中有2个人互不认识矛盾！（2）若A至多认识n?5个人，则剩下至少4个人均与A互不认识，从而与这4个人两两相识，矛

A1A2A8A7A6A4A5 2

盾！其次，当n?10时，（1）与（2）必有一种情况出现，故此时不满足要求．当n?9时，要使（1）与（2）均不出现，则此时每个人恰好认识其他5个人．于是，这9个人产生的朋友对的数目为矛盾！综上，所求n的最大值为8．

例2. （第六届IMO）17位学者，每一位都给其余的人写一封信，信的内容是讨论三个问题中的一个．而且两个人互相通信所讨论的是同一个问题。证明：至少有三位学者，他们之间通信所讨论的是同一个问题． 证明：作完全图K17，它的17个点vi(i?1,2,???,17)分别表示17位科学家.设他们讨论的题目为x,y,z,两位科学家讨论x连红线,讨论y连蓝线,讨论z连黄线.于是只须证明这个K17中有一同色三角形.任取一点

9?5?N，2?16?v1，自v1引出的边共16条，因而一定有???6条边同色，不妨设v1v2,v1v3,v1v4,v1v5,v1v6,v1v7为红色.

?3?如果有一条边v2v3也是红色，则v1v2v3为红色三角形；如果这个K6v2,v3,v4,v5,v6,v7构成的完全图K6中，

中没有红色边，只有蓝色和黄色，由拉姆赛定理知一定存同色三角形（蓝色或黄色）.

例3. 两个航空公司为十个城市通航，使得任意两个城市之间恰有一个公司开设直达航班的往返服务，证明：至少有一个公司能提供两个不相交的旅游圈，每圈可游览奇数个城市．

证明：在完全图中10个顶点中取出6个点，由拉姆赛定理知，这6点组成的K6的边染两色至少有一个同色三角形，不妨记为A1A2A3．由余下的7个点组成的K7中也至少存在一个同色三角形，记为

B1B2B3．当然，A1A2A3与B1B2B3是没有公共点的，如果他们同色，则结论成立．因此仅需考虑不同

色的情形．不妨设A1A2A3为红色三角形，而B1B2B3为蓝色三角形，这两个三角形之间还有9条边，这9条边染两色，至少有5条边是同色的，不妨设A1B1,A1B2,A1B3,A2B1,A2B2,A2B3,A3B1,A3B2,A3B3有5条蓝边．因此，在A1,A2,A3中，至少有一个点，它引出两条蓝边，不妨设A1B1,A1B2是蓝边．于是我们得到红色A1A2A3和蓝色A1B1B2．于是除了这两个红、蓝三角形（A1A2A3和A1B1B2）外，还剩5个点，我们把这5个点记作C1,C2,C3,C4,C5（其中有一个点曾经称为B3）．现在考虑由C1,C2,C3,C4,C5所成的K5，若这个K5中有同色三角形，则此三角形和A1A2A3、A1B1B2都无公共点，且必与其中之一同色，结论成立；若这个K5中无同色三角形，由前面的5点染色游戏知，必有一个同色五边形，它与

A1A2A3、A1B1B2无公共点．于是出现两个同色奇数圈．

由于染色问题主要涉及集合元素的分类，与自然数n密切相关，因此在处理手法上不能仅限于上面提

3

到的，数学归纳法也就不乏用武之地了．

例4. （第29届俄罗斯数学奥林匹克）某国有N个城市，每两个城市之间或者有公路，或者有铁路相连．一个旅行者希望到达每个城市恰好一次，并且最终回到他所出发的城市．证明：该旅行者可以挑选一个城市作为出发点，不但能够实现他的愿望，而且途中至多变换一次交通工具的种类．

证明：问题可以转化为，给定一个完全图Kn，对它的边染两种不同的颜色．证明，从中可以找到一个经过所有顶点的圈，该圈至多可以分为两个各自同色的部分．对N用数学归纳法．当N?3时，命题显然成立；假设N?k时命题成立，考虑N?k?1的情形．先从所考察的图中去掉一个顶点M及所有从它出发的边．由归纳假设知，在剩下的完全图Kk中存在一个经过所有顶点的圈．该圈之多可以分为两个各自同色的部分．下面分两种情形讨论：（1）该圈上的所有边全都同色．依次将圈上的顶点记为（2）该圈上A1,A2,???Ak．从中去掉边A1A2，然后将顶点M分别与A1、A2相连，所得的圈即符合要求．

的所有边不全同色．将顶点编号，使得对某个顶点Am，圈上由A1到Am的部分A1A2???Am为一种颜色（红色），AmAm?1???AkA1为另一种颜色（蓝色）．只要观察边MAm的颜色：如果该边为红色，则圈

A1A2???AmMAm?1???AkA1为所求；如果该边为蓝色，则圈A1A2???Am?1MAm???AkA1为所求．这就表明，对

于命题N?k?1也成立．

例5. （第30届俄罗斯数学奥林匹克）某国有若干个城市和k个不同的航空公司．任意2个城市之间，或者有1条属于某个航空公司的双向的直飞航线连接，或者没有航线连接．已知任意2条同一公司的航线都有公共的端点.证明：可将所有的城市分为k?2个组，使任意2个属于同一组的城市之间都没有航线相连． 证明：对k进行数学归纳．当k?0时，没有航空公司，结论显然成立．作一个凸多边形，其中的顶点为该国的城市，边为航线。分别以Ei(i?1,2???,k)表示各个航空公司的航线所对应的边的集合，由已知条件，易知对于每个集合Ei(i?1,2???,k)或者为三角形，或者为“花”，即具有一个公共顶点的若干条边．如果存在一个集合Ej是以顶点A为公共顶点的“花”，那么，就从图中去掉顶点A和所有由A所连出的边．于是在剩下的图中只有k?1家航空公司的航线．根据归纳假设，可以把所有的顶点分成k?1组，使得任意任意2个属于同一组的城市之间都没有航线相连．再把A作为第k?2组即可．如果所有的Ei(i?1,2???,k)都是三角形，此时图中恰好有3k条边，我们只需将图中的顶点分为尽可能少的组，使得任意2个属于同一组的顶点之间都没有边相连即可．否则假设所分出的组为B1,B2,???,Bn，且n?k?3．注意到，此时在任何两个组Bi和Bj之间，都一定有某条边联结Bi和Bj中的某2个顶点，若不然，就可以把两个组并成一

4

22组．从而，该图中至少有Cn条边，这样一来，就有Cn?(k?3)(k?2)?3k，矛盾．所以，原结论成立．

2 5

本文来源：https://www.bwwdw.com/article/5a9v.html