当前位置:首页 >> 学科竞赛 >> 高中数学竞赛专题讲座---简单的染色问题

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


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

关? 抽象数学问题:把六个点(任意三点不共线)的连线染两色,至少会出现一个同色三角形. 证明:任取一点 A,那么由点 A 引出的 5 条边中,由抽屉原理,至少有 三条是同色的,不妨设 AB、AC、AD 是蓝色的,如图所示.考察 BC、BD、 CD 三条边,若这三条边中有一条是蓝色的,则与 A 形成一个蓝色三角形; 若这三条边都是红色的,则三角形 BCD 为一个红色三角形. “任何六个人聚在一起,或者有三个人彼此相识,或者有三个人彼此不相 识”这样一个著名的实际问题也就迎刃而解. 1928 年, 在英国伦敦数学会的一次学术会议上, 年仅 24 岁的年轻数学家弗兰克· 普拉东· 拉姆赛 (Frank Plumpton Ramsey)证明了一个定理:如果某一集合(如点集)中事物的数量足够多,且每对事物间都 存在一定数量的关系(如各种颜色的边)中的一种,那么必定存在一个包含若干数目事物的子集(如三点 集) ,其中每对事物间也存在同样的关系(如同色三角形) .这个定理称为拉姆赛定理,告诉我们:如果平 面上的点数足够多,且每对点间的线(边)或染红色或染蓝色,那么必定存在一个包含 3 个点的子集,他 们之间的边同色,即包含一个同色三角形. 如果我们将刚才的六点染色游戏继续下去,染完所有的线段,同色三角形最少出现了几个?这是偶然 吗?恭喜你!答对了,2 个!在六点(任意三点不共线)染色游戏中,必有两个同色三角形. 证明: 方法一: 为方便叙述, 我们把平面上有 n 个点, 每两点都有连线的图称为 n 阶完全图, 记作 K n . 由 拉姆赛定理知把 K6 边染红、蓝两色,必出现一个同色三角形,不妨设这个三角形是红色的 ABC .现考 虑△ ABC 以外的点 D、E、F,由 D 引出的五条边中,由抽屉原理,至少有三条边是同色的,除了 D 与 A、 A F B、C 所连的边是蓝色的情形以外,其余情形 均可仿照结前面的证明得到一个同色三角 形; 同理, E、 F 引出的边也有同样的结论. 于 B E 是,只剩下如图情形,即 D、E、F 与△ ABC 的三顶点连线均是蓝色.这时,三角形 DEF 或者是红色三角形,或者与原来的蓝边形成 C D A C B D A

1

一个蓝色三角形. 方法二(算两次) :考虑自同一点引出的两条边,如果他们颜色相同,就称他们组成一个“同色角”,设
2 自点 A 引出 r 条红边,5-r 条白边,则自 A 点引出的同色角共有( C r2 ? C5 ? r )个,易知当 r=2 或 3 时 2 C r2 ? C5 ? r 最小,最小值为 4,所以该六点图中至少有 6×4=24 个同色角;另一方面,每个同色三角形中

有 3 个同色角,每个边不全同色的三角形中只有 1 个同色角.设同色三角形有 x 个,则不同色三角形有
3 3 ( C6 ? x )个,因此,同色角共有 3 x ? (C 6 ? x) ? 20? x 个.综上, 20 ? x ? 24 ,从而, x ? 2 .

如果减少一点,做五点(任意三点不共线)染色游戏是否一定能分出胜负呢?如出现平局,平局的图 形是什么样的呢?读者不妨动手一试,在五点染色游戏中,或者必出现一个同色三角形,或者必出现一个 同色五边形(首尾顺次连接即可) .如将上述一类问题推广,可在哪几方面进行变化?请读者思考. 例 1. 在 2 色完全图 K9 中,至少存在一个红色三角形或一个蓝色四边形. 证明: 如果 K9 中有一个点 v1 引出至少 4 条红边, 不妨设 v1v2 , v1v3 , v1v4 , v1v5 为红边, 这时 v2 , v3 , v4 , v5 四 个点所成的 K 4 中或者每条边都是蓝色, 或者至少有一条边为红色. 在后一种情况, 设红边为 v2 v3 , 则 v vv 123 为红色三角形.如果 K9 中每个点引出的红边少于 4 条,那么每点至少引出 5 条蓝边.由于蓝边的总数的 2 倍 ? 5 ? 9 ? 45 ,所以,蓝边的总数的 2 倍 ? 46 ,从而至少有一点 v1 引出 6 条蓝边.设 v1v2 , v1v3 , v1v4 , v1v5 , v1v6 , v1v7

v3 , v1v4 , v1v5 , v1v6 , v1v7 为蓝边,这时 v , v , v , v , v , v 所成的 K 中必有一个同色三角形.如果是红色三角形,结论成立; 6 2 3 4 5 6 7
如果是蓝色三角形,那么它的三个顶点与 v1 构成蓝色的 K 4 . 例 2. (2005 西部)设 n 个新生中,任意 3 个人中有 2 个人互相认识,任意 4 个人中有 2 个人互不认识, 试求 n 的最大值. 解:当 n ? 8 时,如图所示的例子满足要求,其中 表示 8 个学生,红色表示认 A1 , A2 , A3 , A4 , A5 , A6 , A7 , A 8 识.下设 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 个人两两相识,矛

A1 A2

A8 A7

A6 A4 A5

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?
如果有一条边 v2 v3 也是红色, 则 v1v2v3 为红色三角形; 如果这个 K6 v2 , v3 , v4 , v5 , v6 , v7 构成的完全图 K6 中, 中没有红色边,只有蓝色和黄色,由拉姆赛定理知一定存同色三角形(蓝色或黄色). 例 3. 两个航空公司为十个城市通航,使得任意两个城市之间恰有一个公司开设直达航班的往返服务,证 明:至少有一个公司能提供两个不相交的旅游圈,每圈可游览奇数个城市. 证明:在完全图中 10 个顶点中取出 6 个点,由拉姆赛定理知,这 6 点组成的 K6 的边染两色至少有一 个同色三角形,不妨记为 A1 A2 A3 .由余下的 7 个点组成的 K7 中也至少存在一个同色三角形,记为

B1B2 B3 .当然, A1 A2 A3 与 B1B2 B3 是没有公共点的,如果他们同色,则结论成立.因此仅需考虑不同
色的情形.不妨设 A1 A2 A3 为红色三角形,而 B1B2 B3 为蓝色三角形,这两个三角形之间还有 9 条边 ,这 9 条边染两色,至少有 5 条边是同色的,不妨设 A1 B1, A1 B2 , A1 B3, A2 B1, A2 B2, A2 B3, A3 B1, A3 B2, A3 B3 有 5 条蓝边.因此,在 A1 , A2 , A3 中,至少有一个点,它引出两条蓝边,不妨设 A 1B 1, A 1B2 是蓝边.于是我 们得到红色 A1 A2 A3 和蓝色 A 1B 1B2 .于是除了这两个红、蓝三角形( A 1 A2 A 3和 A 1B 1B2 )外,还剩 5 个点,我们把这 5 个点记作 C1 , C2 , C3 , C4 , C5(其中有一个点曾经称为 B3 ) .现在考虑由 C1 , C2 , C3 , C4 , C5 所成的 K5 ,若这个 K5 中有同色三角形,则此三角形和 A1 A2 A3 、 A 1B 1B2 都无公共点,且必与其中之一 同色,结论成立;若这个 K5 中无同色三角形,由前面的 5 点染色游戏知,必有一个同色五边形,它与

A1 A2 A3 、 A1B1B2 无公共点.于是出现两个同色奇数圈.
由于染色问题主要涉及集合元素的分类,与自然数 n 密切相关,因此在处理手法上不能仅限于上面提

3

到的,数学归纳法也就不乏用武之地了. 例 4. (第 29 届俄罗斯数学奥林匹克) 某国有 N 个城市, 每两个城市之间或者有公路, 或者有铁路相连. 一 个旅行者希望到达每个城市恰好一次,并且最终回到他所出发的城市.证明:该旅行者可以挑选一个城市 作为出发点,不但能够实现他的愿望,而且途中至多变换一次交通工具的种类. 证明:问题可以转化为,给定一个完全图 K n ,对它的边染两种不同的颜色.证明,从中可以找到一 个经过所有顶点的圈,该圈至多可以分为两个各自同色的部分.对 N 用数学归纳法.当 N ? 3 时,命题显 然成立;假设 N ? k 时命题成立,考虑 N ? k ? 1的情形.先从所考察的图中去掉一个顶点 M 及所有从它 出发的边.由归纳假设知,在剩下的完全图 K k 中存在一个经过所有顶点的圈.该圈之多可以分为两个各 自同色的部分.下面分两种情形讨论: (1)该圈上的所有边全都同色.依次将圈上的顶点记为 (2)该圈上 A1 , A2 , ??? Ak .从中去掉边 A1 A2 ,然后将顶点 M 分别与 A1 、 A2 相连,所得的圈即符合要求. 的所有边不全同色.将顶点编号,使得对某个顶点 Am ,圈上由 A1 到 Am 的部分 A1 A2 ??? Am 为一种颜色(红 色) , Am Am?1 ??? Ak A1 为 另 一 种 颜 色 ( 蓝 色 ) . 只 要 观 察 边 MAm 的 颜 色 : 如 果 该 边 为 红 色 , 则 圈

A1 A2 ??? Am MAm?1 ??? Ak A1 为所求;如果该边为蓝色,则圈 A1 A2 ??? Am?1MAm ??? Ak A1 为所求.这就表明,对
于命题 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 ) 或者为三角形, 或者为“花”, 即具有一个公共顶点的若干条边. 如 果存在一个集合 E j 是以顶点 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 和 B j 之间,都一定有某条边联结 Bi 和 B j 中的某 2 个顶点,若不然,就可以把两个组并成一

4

2 2 组.从而,该图中至少有 Cn 条边,这样一来,就有 Cn ?

(k ? 3)(k ? 2) ? 3k ,矛盾.所以,原结论成立. 2

5


更多相关文档:

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

高中数学竞赛专题讲座---简单的染色问题_学科竞赛_高中教育_教育专区。简单的染色问题在我们美丽的地球上,有 60 多亿人口,任何六个人聚在一起,或者有三个人彼此相...

高中数学竞赛讲座 14染色问题与染色方法

高中数学竞赛讲座 14染色问题与染色方法_学科竞赛_高中教育_教育专区。竞赛讲座 14 -染色问题与染色方法 1. 小方格染色问题 最简单的染色问题是从一种民间游戏中发...

高中数学竞赛 染色问题与染色方法

染色问题与染色方法-高中... 8页 免费 高中数学竞赛专题讲座--... 5页 免费...第二专题 染色问题与染色方法一、区域染色 例 1、有一个 3× 7 的棋盘,用...

高中竞赛数学讲义第14讲染色问题

高中竞赛数学讲义第14讲染色问题_学科竞赛_高中教育_教育专区。第 14 讲 染色问题本节主要讲述用染色的方法解有关的竞赛题.染色,是一种辅助解题的手段,通过染色,...

高中数学奥林匹克竞赛讲座:14染色问题与染色方法

高中数学奥林匹克竞赛讲座... 10页 5财富值喜欢此文档的还喜欢 ...最简单的染色问题是从一种民间游戏中发展起来的方格盘上的染色问题.解决这类问...

高中数学《排列组合染色问题》典例讲解

高中数学《排列组合染色问题》典例讲解_高二数学_数学_高中教育_教育专区。高中数学《排列组合染色体问题》探究排列组合染色问题的探究上饶县二中 徐凯 在任教高二数学...

2012江苏省数学竞赛《提优教程》教案:第14讲 染色问题

2012江苏省数学竞赛《提优教程》教案:第14讲 染色问题_学科竞赛_高中教育_教育专区。第 14 讲 染色问题本节主要讲述用染色的方法解有关的竞赛题.染色,是一种辅...

思科数学【提优教程】江苏省2012高中数学竞赛 第14讲 染色问题教案

思科数学【提优教程】江苏省2012高中数学竞赛 第14讲 染色问题教案_金融/投资_经管营销_专业资料。思科数学【提优教程】江苏省2012高中数学竞赛讲义 高中数学培优第...

高中数学竞赛专题讲座---竞赛中的数论问题

高中数学竞赛专题讲座---竞赛中的数论问题_学科竞赛_高中教育_教育专区。竞赛中...an 最大。显然,最特殊且最简单的正整数是 1。例如取 a1=1,这里由 a1a2 ?...
更多相关标签:
高中数学竞赛专题讲座 | 初中数学竞赛专题讲座 | 新党章专题讲座 | 食品安全知识专题讲座 | 河南消防竞赛专题首页 | 法治专题讲座 | 专题讲座主持词 | 经济专题讲座论文 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com