染色问题与染色方法

《染色问题与染色方法》由会员分享，可在线阅读，更多相关《染色问题与染色方法（9页珍藏版）》请在金锄头文库上搜索。

1、染色问题与染色方法1 小方格染色问题最简单的染色问题是从一种民间游戏中发展起来的方格盘上的染色问题 .解决这类 问题的方法后来又发展成为解决方格盘铺盖问题的重要技巧 .例1如图29-l（a）,3行7列小方格每一个染上红色或蓝色.试证:存在一个矩形，它的 四个角上的小方格颜色相同.(a)图 29-1证明 由抽屉原则,第1行的7个小方格至少有4个不同色,不妨设为红色（带阴影） 并在1、2、3、4列（如图 29-1（b）.在第1、2、3、4列（以下不必再考虑第5，6，7列）中，如第2行或第3行出现两 个红色小方格，则这个问题已经得证；如第 2行和第3行每行最多只有一个红色小 方格（如图29-1 （c

2、），那么在这两行中必出现四角同为蓝色的矩形，问题也得到 证明.说明：（1）在上面证明过程中除了运用抽屉原则外，还要用到一种思考问题的有效 方法，就是逐步缩小所要讨论的对象的范围，把复杂问题逐步化为简单问题进行处 理的方法.（2）此例的行和列都不能再减少了.显然只有两行的方格盘染两色后是不一定存在 顶点同色的矩形的.下面我们举出一个3行6列染两色不存在顶点同色矩形的例子如 图29-2.这说明3行7列是染两色存在顶点同色的矩形的最小方格盘了 至今，染k 色而存在顶点同色的矩形的最小方格盘是什么还不得而知 .例2（第2届全国部分省市初中数学通讯赛题）证明：用15块大小是4X1的矩形瓷砖和1块大小是2

3、X2的矩形瓷砖，不能恰好铺盖8X8矩形的地面分析 将8X8矩形地面的一半染上一种颜色，另一半染上另一种颜色，再用4X1 和 2X2 的矩形瓷砖去盖，如果盖住的两种颜色的小矩形不是一样多，则说明在给定 条件不完满铺盖不可能.证明 如图 29-3，用间隔为两格且与副对角线平行的斜格同色的染色方式，以黑白 两种颜色将整个地面的方格染色.显然，地面上黑、白格各有 32 个.每块 4X1 的矩形砖不论是横放还是竖盖， 且不论盖在何处，总是占据地面上的两个 白格、两个黑格，故15块4X1的矩形砖铺盖后还剩两个黑格和两个白格但由于与 副对角线平行的斜格总是同色，而与主对角线平行的相邻格总是异色，所以，不论

4、怎样放置，一块 2X2 的矩形砖，总是盖住三黑一白或一黑三白 . 这说明剩下的一块 2X2 矩形砖无论如何盖不住剩下的二黑二白的地面 .从而问题得证.例3（1986年北京初二数学竞赛题）如图29-4 （1 ）是4个1X1的正方形组成的“L”形，用若干个这种“L”形硬纸片无重迭拼成一个mXn （长为m个单位, 宽为 n 个单位）的矩形如图 29-4 （2）.试证明 mn 必是 8 的倍数.证明VmXn矩形由“L”形拼成，：mXn是4的倍数，：m、n中必有一个是偶数， 不妨设为m.把mXn矩形中的m列按一列黑、一列白间隔染色（如图29-4 （2）, 则不论“L”形在这矩形中的放置位置如何（“L”形

5、的放置，共有8种可能），“L” 形或占有3白一黑四个单位正方形（第一种） ，或占有3黑一白四个单位正方形（第 二种） .设第一种“L”形共有p个，第二种“L”形共q个，则mXn矩形中的白格单位正方 形数为3p+q，而它的黑格单位正方形数为p+3q.m为偶数，mXn矩形中黑、白条数相同，黑、白单位正方形总数也必相等故有 3p+q=p+3q，从而p=q.所以“L”形的总数为2p 个,即“L”形总数为偶数，所以mXn 一定是 8 的倍数.2 线段染色和点染色下面介绍两类重要的染色问题 .（1） 线段染色. 较常见的一类染色问题是发样子组合数学中图论知识的所谓“边 染色”（或称“线段染色”），主要借助

6、抽屉原则求解 .例 4（1947 年匈牙利数学奥林匹克试题）世界上任何六个人中，一定有 3个人或者互相认识或者互相都不认识.我们不直接证明这个命题，而来看与之等价的下述命题例 5（1953 年美国普特南数学竞赛题）空间六点，任三点不共线，任四点不共面，成对地连接它们得十五条线段，用红色或蓝色染这些线段（一条线段只染 一种颜色） . 求证:无论怎样染,总存在同色三角形.证明 设A、B、C、D、E、F是所给六点考虑以A为端点的线段AB、AC、AD、AE、AF，由抽屉原则这五条线段中至少有三条颜色相同，不妨设就是AB、AC、AD，且它 们都染成红色再来看厶BCD的三边，如其中有一条边例如BC是红色的

7、，则同色三角 形已出现（红色 ABC）；如厶BCD三边都不是红色的，则它就是蓝色的三角形，同 色三角形也现了. 总之,不论在哪种情况下,都存在同色三角形 .如果将例 4 中的六个人看成例 5 中六点,两人认识的连红线,不认识的连蓝线,则例 4 就变成了例 5. 例 5 的证明实际上用染色方法给出了例 4 的证明.图 29-5例 6（ 第6 届国际数学奥林匹克试题）有 17 位科学家,其中每一个人和其他所有人的人通信,他们的通信中只讨论三个题目 . 求证:至少有三个科学家相互之间 讨论同一个题目.证明 用平面上无三点共线的17个点A,A2,，A17分别表示17位科学家.设他们讨 论的题目为x,y

8、,z,两位科学家讨论x连红线，讨论y连蓝线,讨论z连黄线.于是只须 证明以这 17 个点为顶点的三角形中有一同色三角形 .考虑以 A 为端点的线段 AA,AA ,， AA ，由抽屉原则这 16 条线段中至少有 6 条同11 21 31 17色，不妨设 AA ， AA ， AA 为红色. 现考查连结六点 A ， A ， A 的 15 条线段，1 21 31 7237如其中至少有一条红色线段，则同色（红色）三角形已出现；如没有红色线段，则 这 15 条线段只有蓝色和黄色，由例 5 知一定存在以这 15 条线段中某三条为边的同 色三角形（蓝色或黄色） . 问题得证.上述三例同属图论中的接姆赛问题 .

9、 在图论中, 将 n 点中每两点都用线段相连所得的 图形叫做 n 点完全图, 记作 k. 这些点叫做“顶点”，这些线段叫做“边”.现在我们 n分别用图论的语言来叙述例 5、例 6.定理1若在k6中，任染红、蓝两色，则必有一只同色三角形.定理2在ki7中，任染红、蓝、黄三角，则必有一只同色三角形.2）点染色.先看离散的有限个点的情况 .例 7 （首届全国中学生数学冬令营试题）能否把 1 ，1，2，2，3，3，1986 ，1986这些数排成一行，使得两个1之间夹着一个数，两个2 之间夹着两个数， 两个1986、之间夹着一千九百八十六个数？请证明你的结论 .证明 将1986X2个位置按奇数位着白色，

10、偶数位着黑色染色，于是黑白点各有1986 个.图 29-6现令一个偶数占据一个黑点和一个白色，同一个奇数要么都占黑点， 要么都占白点. 于是 993 个偶数，占据白点 A=993 个，黑色 B=993 个.993个奇数，占据白点A2=2a个，黑点B2=2b个，其中a+b=993因此，共占白色 A=A +A =993+2a 个.黑点 B=B1+B2=993+2b 个，由于a+b=993 （非偶数！）：aHb，从而得AHB.这与黑、白点各有1986个矛盾.故这种排法不可能.“点”可以是有限个，也可以是无限个，这时染色问题总是与相应的几何问题联系 在一起的.例8对平面上一个点，任意染上红、蓝、黑三种

11、颜色中的一种 . 证明:平面内存在端点同色的单位线段.证明作出一个如图29-7的几何图形是可能的，其中 ABD、ACBD、AAEF、AGEF 都是边长为1的等边三角形，CG=1.不妨设A点是红色，如果B、E、D、F中有红色, 问题显然得证当B、E、D、F都为蓝点或黄点时，又如果B和D或E和F同色，问 题也得证. 现设 B 和 D 异色 E 和 F 异色， 在这种情况下， 如果 C 或 G 为黄色或蓝点， 则 CB、CD、GE、GF中有两条是端点同色的单位线段，问题也得证不然的话,C、G均为 红点，这时 CG 是端点同色的单位线段. 证毕.还有一类较难的对区域染色的问题，就不作介绍了 .图 29

12、-7练习二十九16X6的方格盘，能否用一块大小为3格，形如的弯角板与 11块大小为 3X1 的矩形板，不重迭不遗漏地来铺满整个盘面 .2 （第 49 届苏联基辅数学竞赛题）在两张 1982X1983 的方格纸涂上红、黑两种 颜色，使得每一行及每一列都有偶数个方格是黑色的 .如果将这两张纸重迭时， 有一 个黑格与一个红格重合，证明至少还有三个方格与不同颜色的方格重合 .3 有九名数学家，每人至多会讲三种语言，每三名中至少有 2 名能通话，那么其 中必有 3 名能用同一种语言通话 .4 如果把上题中的条件 9 名改为 8 名数学家，那么，这个结论还成立吗？为什么？5. 设n=6 （r-2） +3

13、（r3）,求证：如果有n名科学家，每人至多会讲3种语言, 每 3 名中至少有 2 名能通话，那么其中必有 r 名能用同一种语言通话.6. （ 1966 年波兰数学竞赛题）大厅中会聚了 100 个客人，他们中每人至少认识 67 人，证明在这些客人中一定可以找到 4 人，他们之中任何两人都彼此相识 .7. （首届全国数学冬令营试题）用任意方式给平面上的每一个点染上黑色或白色 .求证：一定存在一个边长为1或冉的正三角形，它三个顶点是同色的练习二十九 1 .将1、4行染红色、2、5行染黄色、3、6行染蓝色，然后就弯角板盖住板面的不同情况分类讨论2设第一张纸上的黑格A与第二张纸上的红格A重合如果在第一张

14、纸上A所 在的列中，其余的黑格（奇数个）均与第二张纸的黑格重合，那么由第二张纸上这 一列的黑格个数为偶数，知必有一黑格与第一张纸上的红格重合，即在这一列，第 一张纸上有一方格B与第二张纸上不同颜色的方格重合同理在A、E所在行 上各有一个方格C、D，第二张纸上与它们重合的方格C、D的颜色分别与C、 D不同.3把9名数学家用点AJA?,，A?表示两人能通话，就用线连结，并涂某 种颜色，以表示不同语种。两人不通话，就不连线（1）果任两点都有连线并涂有颜色，那么必有一点如A ,以其为一端点的8条线 段中至少有两条同色，比如A A、A A .可见A ，A，A之间可用同一语言1213123通话如情况不发生

15、，则至少有两点不连线，比如A 、A 由题设任三点必12有一条连线知，其余七点必与A或A有连线.这时七条线中，必有四条是从某一12点如A】引出的而这四条线中又必有二条同色，则问题得证.4结论不成立，如图所示（图中每条线旁都有一个数字，以表示不同语种）.1川、7 小第斗她图5类似于第3题证明.6.用点A、A、A 表示客人，红、蓝的连线分别表示两人相识或不相识，1 2 10 0因为由一个顶点引出的蓝色的线段最多有32条，所以其中至少有三点之间连红 线这三个点（设为Am 引出的蓝色线段最多为9 6条去掉所有这些 蓝色的线段（连同每条线段上的一个端点A1工1,2,3），这样，在图中至 少还剩下四个点，除A、A、A夕卜，设第四点为A，这四个点中A，A，A1234123每一个点与其它的点都以红色的线段相连，于是客人A 、A、A、A彼此两两 1234相识.7先利用右图证明”若平面上有两个异色的点距离为2,地么必定可以找到符合 题意的三角形” 再找长为2端点异色的线段以0（白色）为圆心，4为半径作 圆.如圆内皆白点，问题已证.否则圆内有一黑点P,以OP为底作腰长为