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

简单的染色问题在我们美丽的地球上，有60多亿人口，任何六个人聚在一起，或者有三个人彼此相识，或者有三个人彼此不相识。你相信吗？那就先让我们来作个游戏！规则：正六边形的六个顶点，两游戏者每次可随意选用红

简单的染色问题 60 在我们美丽的地球上，有多亿人口，任何六个人聚在一起，或者有三个人彼此相识，或者有三个 随意 人彼此不相识。你相信吗？那就先让我们来作个游戏！规则：正六边形的六个顶点，两游戏者每次可 轮流 选用红或蓝色的笔，选择其中的两点连线，谁第一个被迫画成一个同色的三角形（红色或白色），他 就是失败者．这个游戏是否一定能分出胜负呢？与先下后下是否有关？ 抽象数学问题：把六个点（任意三点不共线）的连线染两色，至少会出现一个同色三角形． 证明： AA5AB 任取一点，那么由点引出的条边中，由抽屉原理，至少有三条是同色的，不妨设、 A ACADBCBDCDA 、是蓝色的，如图所示．考察、、三条边，若这三条边中有一条是蓝色的，则与形成 BCD 一个蓝色三角形；若这三条边都是红色的，则三角形为一个红色三角形． D “” 任何六个人聚在一起，或者有三个人彼此相识，或者有三个人彼此不相识这样一个著名的实际问题也 C 就迎刃而解． B 192824·· 年，在英国伦敦数学会的一次学术会议上，年仅岁的年轻数学家弗兰克普拉东拉姆赛 FrankPlumptonRamsey （）证明了一个定理：如果某一集合（如点集）中事物的数量足够多，且每 对事物间都存在一定数量的关系（如各种颜色的边）中的一种，那么必定存在一个包含若干数目事物的子 集（如三点集），其中每对事物间也存在同样的关系（如同色三角形）．这个定理称为拉姆赛定理，告诉我 3 们：如果平面上的点数足够多，且每对点间的线（边）或染红色或染蓝色，那么必定存在一个包含个点 的子集，他们之间的边同色，即包含一个同色三角形． 如果我们将刚才的六点染色游戏继续下去，染完所有的线段，同色三角形最少出现了几个？这是偶然 2 吗？恭喜你！答对了，个！在六点（任意三点不共线）染色游戏中，必有两个同色三角形． 证明： 方法一：为方便叙述，我们把平面上有个点，每两点都有连线的图称为阶完全图，记作 ．由拉姆赛定理知把边染红、蓝两色，必出现一个同色三角形，不妨设这个三角形是红色的 △ABCDEFD ．现考虑以外的点、、，由引出的五条边中，由抽屉原理，至少有三条边是同色的， A F DABC 除了与、、所连的边是蓝色的情形以外，其余情形均可仿照结前面的证明得到一个同色三角形； EFDEF△ABC 同理，、引出的边也有同样的结论．于是，只剩下如图情形，即、、与的三顶点连线均是 DEF 蓝色．这时，三角形或者是红色三角形，或者与原来的蓝边形成一个蓝色三角形． B “” 方法二（算两次）：考虑自同一点引出的两条边，如果他们颜色相同，就称他们组成一个同色角， E Ar5rAr23 设自点引出条红边，－条白边，则自点引出的同色角共有（）个，易知当＝或时 46×424 最小，最小值为，所以该六点图中至少有＝个同色角；另一方面，每个同色三角形中 C 31 有个同色角，每个边不全同色的三角形中只有个同色角．设同色三角形有个，则不同色三角形有 D 1 A