《竞赛培训专题2-染色问题与染色方法》由会员分享，可在线阅读，更多相关《竞赛培训专题2-染色问题与染色方法（6页珍藏版）》请在金锄头文库上搜索。
1、- 1 -竞赛培训专题 2-染色问题与染色方法1 小方格染色问题最简单的染色问题是从一种民间游戏中发展起来的方格盘上的染色问题.解决这类问题的方法后来又发展成为解决方格盘铺盖问题的重要技巧.例 1 如图 29-1(a),3行 7列小方格每一个染上红色或蓝色.试证:存在一个矩形,它的四个角上的小方格颜色相同.证明 由抽屉原则,第 1行的 7个小方格至少有 4个不同色,不妨设为红色(带阴影)并在1、2、3、4 列（如图 29-1（b）.在第 1、2、3、4 列（以下不必再考虑第 5，6，7 列）中，如第 2行或第 3行出现两个红色小方格，则这个问题已经得证；如第 2行和第 3行每行最多只有一个红色
2、小方格（如图 29-1（c），那么在这两行中必出现四角同为蓝色的矩形，问题也得到证明.说明：（1）在上面证明过程中除了运用抽屉原则外，还要用到一种思考问题的有效方法，就是逐步缩小所要讨论的对象的范围，把复杂问题逐步化为简单问题进行处理的方法.（2）此例的行和列都不能再减少了.显然只有两行的方格盘染两色后是不一定存在顶点同色的矩形的.下面我们举出一个 3行 6列染两色不存在顶点同色矩形的例子如图 29-2.这说明 3行 7列是染两色存在顶点同色的矩形的最小方格盘了.至今,染 k色而存在顶点同色的矩形的最小方格盘是什么还不得而知.- 2 -例 2 (第 2届全国部分省市初中数学通讯赛题)证明:用
3、15块大小是 41的矩形瓷砖和1块大小是 22的矩形瓷砖，不能恰好铺盖 88矩形的地面.分析 将 88矩形地面的一半染上一种颜色，另一半染上另一种颜色，再用 41和22的矩形瓷砖去盖，如果盖住的两种颜色的小矩形不是一样多，则说明在给定条件不完满铺盖不可能.证明 如图 29-3，用间隔为两格且与副对角线平行的斜格同色的染色方式，以黑白两种颜色将整个地面的方格染色.显然，地面上黑、白格各有 32个.每块 41的矩形砖不论是横放还是竖盖，且不论盖在何处，总是占据地面上的两个白格、两个黑格，故 15块 41的矩形砖铺盖后还剩两个黑格和两个白格.但由于与副对角线平行的斜格总是同色，而与主对角线平行的相邻
4、格总是异色，所以，不论怎样放置，一块 22的矩形砖，总是盖住三黑一白或一黑三白.这说明剩下的一块 22矩形砖无论如何盖不住剩下的二黑二白的地面.从而问题得证. 例 3 （1986 年北京初二数学竞赛题）如图 29-4（1）是 4个 11的正方形组成的“L”形，用若干个这种“L”形硬纸片无重迭拼成一个mn（长为 m个单位，宽为 n个单位）的矩形如图 29-4（2）.试证明 mn必是 8的倍数.证明mn 矩形由“L”形拼成，mn 是 4的倍数，m、n 中必有一个是偶数，不妨设为 m.把 mn矩形中的m列按一列黑、一列白间隔染色（如图 29-4（2），则不论“L”形在这矩形中的放置位置如何（“L”形
5、的放置，共有 8种可能），“L”形或占有 3白一黑四个单位正方形（第一种），或占有 3黑一白四个单位正方形（第二种）.设第一种“L”形共有 p个，第二种“L”形共 q个，则 mn矩形中的白格单位正方形数为 3p+q，而它的黑格单位正方形数为 p+3q.m 为偶数，mn 矩形中黑、白条数相同，黑、白单位正方形总数也必相等.故有3p+q=p+3q，从而 p=q.所以“L”形的总数为 2p个，即“L”形总数为偶数，所以 mn一定是 8的倍数. 2 线段染色和点染色下面介绍两类重要的染色问题.- 3 -(1) 线段染色.较常见的一类染色问题是发样子组合数学中图论知识的所谓“边染色”（或称“线段染色”）
6、，主要借助抽屉原则求解.例 4 （1947 年匈牙利数学奥林匹克试题）世界上任何六个人中，一定有 3个人或者互相认识或者互相都不认识.我们不直接证明这个命题，而来看与之等价的下述命题例 5 （1953 年美国普特南数学竞赛题）空间六点，任三点不共线，任四点不共面，成对地连接它们得十五条线段，用红色或蓝色染这些线段（一条线段只染一种颜色）.求证:无论怎样染,总存在同色三角形.证明 设 A、B、C、D、E、F 是所给六点.考虑以 A为端点的线段 AB、AC、AD、AE、AF，由抽屉原则这五条线段中至少有三条颜色相同，不妨设就是 AB、AC、AD，且它们都染成红色.再来看BCD 的三边，如其中有一条
7、边例如 BC是红色的，则同色三角形已出现（红色ABC）；如BCD 三边都不是红色的，则它就是蓝色的三角形，同色三角形也现了.总之,不论在哪种情况下,都存在同色三角形.如果将例 4中的六个人看成例 5中六点,两人认识的连红线,不认识的连蓝线,则例 4就变成了例 5.例 5的证明实际上用染色方法给出了例 4的证明.例 6 (第 6届国际数学奥林匹克试题)有 17位科学家,其中每一个人和其他所有人的人通信,他们的通信中只讨论三个题目.求证:至少有三个科学家相互之间讨论同一个题目.证明 用平面上无三点共线的 17个点 A1,A2,，A 17分别表示 17位科学家.设他们讨论的题目为 x,y,z,两位科
8、学家讨论 x连红线,讨论 y连蓝线,讨论 z连黄线.于是只须证明以这 17个点为顶点的三角形中有一同色三角形.考虑以 A1为端点的线段 A1A2,A1A3,，A 1A17，由抽屉原则这 16条线段中至少有 6条同色，不妨设 A1A2，A 1A3，A 1A7为红色.现考查连结六点A2，A 3，A 7的 15条线段，如其中至少有一条红色线段，则同色（红色）三角形已出现；如没有红色线段，则这 15条线段只有蓝色和黄色，由例 5知一定存在以这 15条线段中某三条为边的同色三角形（蓝色或黄色）.问题得证.上述三例同属图论中的接姆赛问题.在图论中,将 n点中每两点都用线段相连所得的图形叫做 n点完全图,记
9、作 kn.这些点叫做“顶点”，这些线段叫做“边”.现在我们分别用图论的语言来叙述例 5、例 6.- 4 -定理 1 若在 k6中，任染红、蓝两色，则必有一只同色三角形.定理 2 在 k17中,任染红、蓝、黄三角，则必有一只同色三角形.（2）点染色.先看离散的有限个点的情况.例 7 （首届全国中学生数学冬令营试题）能否把 1，1，2，2，3，3，1986，1986这些数排成一行，使得两个 1之间夹着一个数，两个 2之间夹着两个数，两个1986、之间夹着一千九百八十六个数？请证明你的结论.证明 将 19862个位置按奇数位着白色，偶数位着黑色染色，于是黑白点各有 1986个.现令一个偶数占据一个黑
10、点和一个白色，同一个奇数要么都占黑点，要么都占白点.于是 993个偶数，占据白点 A1=993个，黑色 B1=993个.993个奇数，占据白点 A2=2a个，黑点 B2=2b个，其中 a+b=993.因此，共占白色 A=A1+A2=993+2a个. 黑点 B=B1+B2=993+2b个，由于 a+b=993（非偶数！）ab，从而得 AB.这与黑、白点各有 1986个矛盾.故这种排法不可能.“点”可以是有限个，也可以是无限个，这时染色问题总是与相应的几何问题联系在一起的.例 8 对平面上一个点，任意染上红、蓝、黑三种颜色中的一种.证明:平面内存在端点同色的单位线段.证明 作出一个如图 29-7的
11、几何图形是可能的,其中ABD、CBD、AEF、GEF 都是边长为 1的等边三角形，CG=1.不妨设 A点是红色，如果 B、E、D、F 中有红色，问题显然得证.当 B、E、D、F 都为蓝点或黄点时，又如- 5 -果 B和 D或 E和 F同色，问题也得证.现设 B和 D异色 E和 F异色,在这种情况下,如果C或 G为黄色或蓝点,则 CB、CD、GE、GF 中有两条是端点同色的单位线段，问题也得证.不然的话,C、G 均为红点，这时 CG是端点同色的单位线段.证毕.还有一类较难的对区域染色的问题，就不作介绍了.练习1 66 的方格盘，能否用一块大小为 3格，形如的弯 角板与 11块大小为31的矩形板，
12、不重迭不遗漏地来铺满整个盘面.2 （第 49届苏联基辅数学竞赛题）在两张 19821983的方格纸涂上红、黑两种颜色，使得每一行及每一列都有偶数个方格是黑色的.如果将这两张纸重迭时，有一个黑格与一个红格重合，证明至少还有三个方格与不同颜色的方格重合.3 有九名数学家，每人至多会讲三种语言，每三名中至少有 2名能通话，那么其中必有 3名能用同一种语言通话.4 如果把上题中的条件 9名改为 8名数学家，那么，这个结论还成立吗？为什么？5 设 n=6（r-2）+3（r3），求证：如果有 n名科学家，每人至多会讲 3种语言，每 3名中至少有 2名能通话，那么其中必有 r 名能用同一种语言通话.6 （1
13、966 年波兰数学竞赛题）大厅中会聚了 100个客人，他们中每人至少认识 67人，证明在这些客人中一定可以找到 4人，他们之中任何两人都彼此相识.7 （首届全国数学冬令营试题）用任意方式给平面上的每一个点染上黑色或白色.求证：一定存在一个边长为 1或 的正三角形，它三个顶点是同色的.练习答案将、行染红色、行染黄色、行染蓝色，然后就弯角板盖住板面的不同情况分类讨论设第一张纸上的黑格与第二张纸上的红格重合如果在第一张纸上所在的列中，其余的黑格（奇数个）均与第二张纸的黑格重合，那么由第二张纸上这一列的黑格个数为偶数，知必有一黑格与第一张纸上的红格重合，即在这一列，第一张纸上有一方格与第二张纸上不同颜
14、色的方格重合同理在、所在行上各有一个方格、，第二张纸上与它们重合的方格 、的颜色分别与、不同- 6 -把名数学家用点 ， ， 表示两人能通话，就用线连结，并涂某种颜色，以表示不同语种。两人不通话，就不连线（）果任两点都有连线并涂有颜色，那么必有一点如 ，以其为一端点的条线段中至少有两条同色，比如 、 可见 ， ， 之间可用同一语言通话如情况不发生，则至少有两点不连线，比如 、 由题设任三点必有一条连线知，其余七点必与 或 有连线这时七条线中，必有四条是从某一点如 引出的而这四条线中又必有二条同色，则问题得证结论不成立，如图所示（图中每条线旁都有一个数字，以表示不同语种）类似于第题证明用点 、
15、、 表示客人，红、蓝的连线分别表示两人相识或不相识，因为由一个顶点引出的蓝色的线段最多有条，所以其中至少有三点之间连红线这三个点（设为 、 、 ）引出的蓝色线段最多为条去掉所有这些蓝色的线段（连同每条线段上的一个端点 ，），这样，在图中至少还剩下四个点，除 、 、 外，设第四点为 ，这四个点中 ， ， 每一个点与其它的点都以红色的线段相连，于是客人 、 、 、 彼此两两相识先利用右图证明若平面上有两个异色的点距离为，地么必定可以找到符合题意的三角形再找长为端点异色的线段以（白色）为圆心，为半径作圆如圆内皆白点，问题已证否则圆内有一黑点，以为底作腰长为的三角形，则至少与、中一点异色，这样的线段找到
