简单的染色问题

1、14 / 14简单的染色问题哈师大附中 赵岩在我们美丽的地球上，有60多亿人口，任何六个人聚在一起，或者有三个人彼此相识，或者有三个人彼此不相识。你相信吗？那就先让我们来作个游戏！ 规则：正六边形的六个顶点，两游戏者每次可随意选用红或蓝色的笔，轮流选择其中的两点连线，谁第一个被迫画成一个同色的三角形（红色或白色），他就是失败者 这个游戏是否一定能分出胜负呢？与先下后下是否有关？ 抽象数学问题：把六个点（任意三点不共线）的连线染两色，至少会出现一个同色三角形ADBC证明：任取一点A，那么由点A引出的5条边中，由抽屉原理，至少有三条是同色的，不妨设AB、AC、AD是蓝色的，如图所示考察BC、BD、

2、CD三条边，若这三条边中有一条是蓝色的，则与A形成一个蓝色三角形；若这三条边都是红色的，则三角形BCD为一个红色三角形 “任何六个人聚在一起，或者有三个人彼此相识，或者有三个人彼此不相识”这样一个著名的实际问题也就迎刃而解 1928年，在英国伦敦数学会的一次学术会议上，年仅24岁的年轻数学家弗兰克·普拉东·拉姆赛（Frank Plumpton Ramsey）证明了一个定理：如果某一集合（如点集）中事物的数量足够多，且每对事物间都存在一定数量的关系（如各种颜色的边）中的一种，那么必定存在一个包含若干数目事物的子集（如三点集），其中每对事物间也存在同样的关系（如同色三角形） 这

3、个定理称为拉姆赛定理，告诉我们：如果平面上的点数足够多，且每对点间的线（边）或染红色或染蓝色，那么必定存在一个包含3个点的子集，他们之间的边同色，即包含一个同色三角形如果我们将刚才的六点染色游戏继续下去，染完所有的线段，同色三角形最少出现了几个？这是偶然吗？恭喜你！答对了，2个！在六点（任意三点不共线）染色游戏中，必有两个同色三角形证明：方法一：为方便叙述，我们把平面上有个点，每两点都有连线的图称为阶完全图，记作由拉姆赛定理知把边染红、蓝两色，必出现一个同色三角形，不妨设这个三角形是红色的ABFCDAE 现考虑ABC以外的点D、E、F，由D引出的五条边中，由抽屉原理，至少有三条边是同色的，除了

4、D与A、B、C所连的边是蓝色的情形以外，其余情形均可仿照结前面的证明得到一个同色三角形；同理，E、F引出的边也有同样的结论于是，只剩下如图情形，即D、E、F与ABC的三顶点连线均是蓝色这时，三角形DEF或者是红色三角形，或者与原来的蓝边形成一个蓝色三角形方法二（算两次）： 考虑自同一点引出的两条边，如果他们颜色相同，就称他们组成一个“同色角”，设自点A引出r条红边，5r条白边，则自A点引出的同色角共有（）个，易知当r2或3时最小，最小值为4，所以该六点图中至少有6×424个同色角；另一方面，每个同色三角形中有3个同色角，每个边不全同色的三角形中只有1个同色角设同色三角形有个，则不同色

5、三角形有（）个，因此，同色角共有个综上，从而，如果减少一点，做五点（任意三点不共线）染色游戏是否一定能分出胜负呢？如出现平局，平局的图形是什么样的呢？读者不妨动手一试，在五点染色游戏中，或者必出现一个同色三角形，或者必出现一个同色五边形（首尾顺次连接即可）如将上述一类问题推广，可在哪几方面进行变化？请读者思考例1在2色完全图中，至少存在一个红色三角形或一个蓝色四边形证明：如果中有一个点引出至少条红边，不妨设为红边，这时四个点所成的中或者每条边都是蓝色，或者至少有一条边为红色在后一种情况，设红边为，则为红色三角形如果中每个点引出的红边少于4条，那么每点至少引出5条蓝边由于蓝边的总数的2倍，所以，

6、蓝边的总数的2倍，从而至少有一点引出6条蓝边设为蓝边，这时所成的中必有一个同色三角形如果是红色三角形，结论成立；如果是蓝色三角形，那么它的三个顶点与构成蓝色的例2（2005西部）设个新生中，任意3个人中有2个人互相认识，任意4个人中有2个人互不认识，试求的最大值解：当时，如图所示的例子满足要求，其中表示8个学生，红色表示认识下设个学生满足题设要求，证明为此先证明如下两种情况不可能出现（1）若某人至少认识6个人，记为，由拉姆赛定理，这6个人中或者有3个人彼此不相识，与已知任意3个人中有2个人认识矛盾；或者有3个人彼此相识，这时与这3个人共4个人互相认识与已知任意4个人中有2个人互不认识矛盾！（2

7、）若至多认识个人，则剩下至少4个人均与互不认识，从而与这4个人两两相识，矛盾！其次，当时，（1）与（2）必有一种情况出现，故此时不满足要求当时，要使（1）与（2）均不出现，则此时每个人恰好认识其他5个人于是，这9个人产生的朋友对的数目为，矛盾！综上，所求的最大值为8例2（第六届IMO）17位学者，每一位都给其余的人写一封信，信的内容是讨论三个问题中的一个而且两个人互相通信所讨论的是同一个问题。证明：至少有三位学者，他们之间通信所讨论的是同一个问题证明：作完全图，它的17个点分别表示17位科学家.设他们讨论的题目为,两位科学家讨论连红线,讨论连蓝线,讨论连黄线.于是只须证明这个中有一同色三角形.

8、任取一点，自引出的边共16条，因而一定有条边同色，不妨设为红色. 构成的完全图中，如果有一条边也是红色，则为红色三角形；如果这个中没有红色边，只有蓝色和黄色，由拉姆赛定理知一定存同色三角形（蓝色或黄色）.例3两个航空公司为十个城市通航，使得任意两个城市之间恰有一个公司开设直达航班的往返服务，证明：至少有一个公司能提供两个不相交的旅游圈，每圈可游览奇数个城市证明： 在完全图中10个顶点中取出6个点，由拉姆赛定理知，这6点组成的的边染两色至少有一个同色三角形，不妨记为 由余下的7个点组成的中也至少存在一个同色三角形，记为 当然，与是没有公共点的，如果他们同色，则结论成立因此仅需考虑不同色的情形 不

9、妨设为红色三角形，而为蓝色三角形，这两个三角形之间还有9条边，这9条边染两色，至少有5条边是同色的，不妨设有5条蓝边 因此，在中，至少有一个点，它引出两条蓝边，不妨设是蓝边于是我们得到红色和蓝色于是除了这两个红、蓝三角形（和）外，还剩5个点，我们把这5个点记作（其中有一个点曾经称为） 现在考虑由所成的，若这个中有同色三角形，则此三角形和、都无公共点，且必与其中之一同色，结论成立；若这个中无同色三角形，由前面的5点染色游戏知，必有一个同色五边形，它与、无公共点于是出现两个同色奇数圈 由于染色问题主要涉及集合元素的分类，与自然数密切相关，因此在处理手法上不能仅限于上面提到的，数学归纳法也就不乏用武

10、之地了例4（第29届俄罗斯数学奥林匹克）某国有个城市，每两个城市之间或者有公路，或者有铁路相连一个旅行者希望到达每个城市恰好一次，并且最终回到他所出发的城市证明：该旅行者可以挑选一个城市作为出发点，不但能够实现他的愿望，而且途中至多变换一次交通工具的种类证明： 问题可以转化为，给定一个完全图，对它的边染两种不同的颜色证明，从中可以找到一个经过所有顶点的圈，该圈至多可以分为两个各自同色的部分 对N用数学归纳法 当时，命题显然成立； 假设时命题成立，考虑的情形先从所考察的图中去掉一个顶点M及所有从它出发的边由归纳假设知，在剩下的完全图中存在一个经过所有顶点的圈该圈之多可以分为两个各自同色的部分下面

11、分两种情形讨论：（1）该圈上的所有边全都同色依次将圈上的顶点记为从中去掉边，然后将顶点分别与、相连，所得的圈即符合要求（2）该圈上的所有边不全同色将顶点编号，使得对某个顶点，圈上由到的部分为一种颜色（红色），为另一种颜色（蓝色）只要观察边的颜色：如果该边为红色，则圈为所求；如果该边为蓝色，则圈为所求 这就表明，对于命题也成立例5（第30届俄罗斯数学奥林匹克）某国有若干个城市和个不同的航空公司任意个城市之间，或者有条属于某个航空公司的双向的直飞航线连接，或者没有航线连接已知任意条同一公司的航线都有公共的端点证明：可以将所有的城市分为个组，使得任意个属于同一组的城市之间都没有航线相连证明：对进行数

12、学归纳当时，没有航空公司，结论显然成立 作一个凸多边形，其中的顶点为该国的城市，边为航线。分别以表示各个航空公司的航线所对应的边的集合，由已知条件，易知对于每个集合或者为三角形，或者为“花”，即具有一个公共顶点的若干条边 如果存在一个集合是以顶点A为公共顶点的“花”，那么，就从图中去掉顶点A和所有由A所连出的边于是在剩下的图中只有家航空公司的航线根据归纳假设，可以把所有的顶点分成组，使得任意任意个属于同一组的城市之间都没有航线相连再把A作为第组即可 如果所有的都是三角形，此时图中恰好有条边，我们只需将图中的顶点分为尽可能少的组，使得任意个属于同一组的顶点之间都没有边相连即可否则假设所分出的组为

13、，且注意到，此时在任何两个组和之间，都一定有某条边联结和中的某个顶点，若不然，就可以把两个组并成一组从而，该图中至少有条边，这样一来，就有，矛盾 所以，原结论成立平面几何选讲反演变换基础知识一、定义1设是平面上的一个定点，是一个非零常数如果平面的一个变换，使得对于平面上任意异于的点与其对应点之间，恒有（1）三点共线；（2）则这个变换称为平面的一个反演变换，记做其中，定点称为反演中心，常数称为反演幂，点称为点的反点2在反演变换下，如果平面的图形变为图形，则称图形是图形关于反演变换的反形反演变换的不动点称为自反点，而反演变换的不变图形则称为自反图形3设两条曲线相交于点，、分别是曲线在点处的切线（如

14、果存在），则与的交角称为曲线在点处的交角；如果两切线重合，则曲线在点处的交角为特别地，如果两圆交于点，那么过点作两圆的切线，则切线的交角称为两圆的交角当两圆的交角为时，称为两圆正交；如果直线与圆相交，那么过交点作圆的切线，则切线与直线的交角就是直线与圆的交角当这个交角为时，称为直线与圆正交二、定理定理1在反演变换下，不共线的两对互反点是共圆的四点定理2在反演变换下，设两点（均不同于反演中心）的反点分别为，则有定理3在反演变换下，过反演中心的直线不变定理4在反演变换下，不过反演中心的直线的反形是过反演中心的圆；过反演中心的圆的反形是不过反演中心的直线定理5在反演变换下，不过反演中心的圆的反形仍是

15、不过反演中心的圆定理6在反演变换下，两条曲线在交点处的交角大小保持不变，但方向相反定理7如果两圆或一圆一直线相切于反演中心，则其反形是两条平行直线；如果两圆或一圆一直线相切于非反演中心，则其反形（两圆或一圆一直线）相切定理8如果两直线平行，则其反形（两圆或一圆一直线）相切于反演中心典型例题一、证明点共线例1的内切圆与边、分别相切于点、，设、分别是、的中点求证：的外心、内心与的外心三点共线证明：如图，设的内心为，内切圆半径为以内心为反演中心，内切圆为反演圆作反演变换，则、的反点分别为、，因而的反形是的外接圆故的外心、内心和的外心三点共线二、证明线共点 例2四边形内接于，对角线与相交于，设、的外心

16、分别为、求证：、三直线共点证明：作反演变换，则、互为反点，、互为反点，不变，直线不变，的外接圆的反形是直线由于直线与的外接圆正交，因而与正交，即有又，所以；同理，所以四边形为平行四边形，从而过的中点；同理也过的中点故、三线共点三、证明点共圆例3设半圆的直径为，圆心为，一直线与半圆交于、两点，且与直线交于再设与的外接圆的第二个交点为求证：证明： 以为反演中心作反演变换，其中，为半圆的半径，则半圆上的每一点都不变，与的反形分别为直线、且设、的反点分别为、，则为直线与的交点，在直径上，直线的反形为的外接圆，直线的反形为的外接圆而是外接圆的直径于是问题转化为证明 因为，是的中点，所以过、三点的圆是的九

17、点圆，而在九点圆上，又在边上（不同于点），故，因此四、证明一些几何（不）等式例4设六个圆都在一定圆内，每一个圆都与定圆外切，并且与相邻的两个小圆外切，若六个小圆与大圆的切点依次为、证明：证明：如图以为反演中心作反演变换，则与的反形为两条平行线，其余5个圆的反形皆是与两条平行线中一条相切的圆；且反形中第一个圆与第五个圆均与两平行线相切，而其余三圆均与相邻的两圆相切设、的反点分别为、，则其反形中的五个圆与两平行线中的一条（即的反形）依次切于、；再设这五个圆的半径依次为、，则由勾股定理可得，同理，显然，于是但，所以故练习：1（2002土耳其数学奥林匹克）两圆外切于点，且内切于另一于点、，另是小圆内公

18、切线割的弦的中点，证明：当、不共线时，是的内切圆圆心2（第30届IMO预选题）双心四边形是指既有内切圆又有外接圆的四边形证明双心四边形的两个圆心与对角线的交点共线3（1997全国高中数学联赛）已知两个半径不等的圆与圆相交于、两点，圆与圆分别于圆内切于、求证：的充分必要条件是、三点共线模拟试题哈师大附中 赵岩一、选择题（每小题6分，共36分）1若集合是整数，且整除，则为（A）空集（B）单元集（C）二元集（D）无穷集2设集合，映射使对任意的，都有是奇数，则这样的映射的个数是（A）45（B）27（C）15（D）11ABCDD1C1B1A13如图，已知正方体，过顶点在空间作直线，使与直线和所成的角都等

19、于60°这样的直线可以做（A）4条（B）3条 （C）2条 （D）1条4若方程在上有两个不同的实数解，则参数的取值范围是（A）0a1（B）3a1（C）a1（D）0a15，是的三元子集，满足：中的所有元素可以组成等差数列那么，这样的三元子集的个数是（A）（B）（C）（D）6在正整数数列中，由1开始依次按如下规则将某些数染成红色先染1，再染2个偶数2、4；再染4后面最邻近的3个连续奇数5、7、9；再染9后面最邻近的4个连续偶数10、12、14、16；再染此后最邻近的5个连续奇数17、19、21、23、25按此规则一直染下去，得到一红色子数列1，2，4，5，7，9，12，14，16，17，则

20、在这个红色子数列中，由1开始的第2003个数是（A）3844（B）3943（C）3945（D）4006二、填空题（每小题9分，共54分）7在四面体P-ABC中，PA=PB=a，PC=AB=BC=CA=b，且ab，则的取值范围为 8已知，则的值是_ 9关于x的不等式的解集是一些区间的并集，且这些区间的长度的和小于4，则实数的取值范围是 10设点B、C分别在第四、第一象限，且点B、C都在抛物线上，O为坐标原点，为直线OC的斜率，则的值为 11已知函数，若的定义域为时，值域为，则应满足的条件是_12数的末四位数字是_三、解答题13（20分）已知，（1）求的最大值与最小值；（2）求所有实数，使得对任意

21、三个实数，存在一个三角形具有边长ABOPQxyF1F214（20分）如图，A、B为椭圆 和双曲线的公共顶点.P、Q分别 为双曲线和椭圆上不同于A、B的动点，且满足.设直线AP、BP、AQ、BQ的斜率分别是，.（1）求证：；（2）设分别为椭圆和双曲线的右焦点；若，求的值15（20分）已知数列，满足：，求证：数列中，任何相邻两项之积减等于某个完全平方数的倍 加试题1的内心为，三角形内一点满足，求证：，而且等号当且仅当时成立2设，且，求证：3某国有若干个城市和个不同的航空公司任意个城市之间，或者有条属于某个航空公司的双向的直飞航线连接，或者没有航线连接已知任意条同一公司的航线都有公共的端点证明：可以将所有的城市分为个组，使得任意个属于同一组的城市之间都没有航线相连模拟试题答案第一试一、选择题：题号123456答案CABABB二、填空题：7； 8； 91,3； 10； 11； 12三、解答