染色问题与染色方法10956.docVIP

染色问题与染色方法 小方格染色问题 最简单的染色问题是从一种民间游戏中发展起來的方格盘上的染色问题?解决这类 问题的方法后来乂发展成为解决方格盘铺盖问题的重耍技巧. 例1如图29-1 （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））,那么在这两行中必出现四角同为蓝色的矩形，问题也得到 证明. 说明：（1）在上面证明过程中除了运用抽屉原则外，还耍用到一种思考问题的有效 方法，就是逐步缩小所要讨论的对彖的范围，把复朵问题逐步化为简单问题进行处 理的方法. （2）此例的行和列都不能再减少了.显然只有两行的方格盘染两色后是不一定存在 顶点同色的矩形的.下面我们举出一个3行6列染两色不存在顶点同色矩形的例子如 图29-2.这说明3行7列是染两色存在顶点同色的矩形的最小方格盘了.至今，染k 色而存在顶点同色的矩形的最小方格盘是什么还不得而知. 图 29-2 例2 （笫2届全国部分省市初屮数学通讯赛题）证明：用15块大小是4X 1 的矩形瓷砖和1块人小是2X2的矩形瓷砖，不能恰好铺盖8X8矩形的地面. 分析 将8X8矩形地面的一半染上一种颜色，另一半染上另一种颜色，再用4X1 和2X2的矩形瓷砖去盖，如果盖住的两种颜色的小矩形不是一?样多，则说明在给定 条件不完满铺盖不可能. 证明如图29-3,用间隔为两格且与副对角线平行的斜格同色的染色方式，以黑白 两种颜色将整个地面的方格染色?显然，地面上黑、白格各冇32个. 每块4X1的矩形砖不论是横放还是竖盖，且不论盖在何处，总是占据地面上的两个 白格、两个黑格，故15块4X1的矩形砖铺盖后还剩两个黑格和两个白格.但山丁与 副对角线平行的斜格总是同色，而与主对角线平行的相邻格总是异色，所以，不论 怎样放置，一块2X2的矩形砖，总是盖住三黑一白或一黑三白.这说明剩下的一?块 2X2矩形砖无论如何盖不住剩下的二黑二片的地面?从而问题得证. 图 29-3 例3 （1986年北京初二数学竞赛题）如图29-4 （1）是4个1X1的正方形 组成的“L”形，用若干个这种形硕纸片无重迭拼成一个mXn（长为ni个单位, 宽为n个单位）的矩形如图29-4 （2）.试证明nin必是8的倍数. 证明???mXn矩形由“L”形拼成，???mXn是4的倍数，.?』、□中必有一个是偶数， 不妨设为ni?把mXn矩形中的m列按一列黑、一列白间隔染色（如图29-4 （2））, 则不论形在这矩形屮的放置位置如何（“L”形的放置，共有8种可能），“L” 形或占有3白一黑四个单位正方形（笫一种），或占有3黑一白四个单位正方形（第 二种）? 设第一种“L”形共有p个，第二种“L”形共q个，则mXn矩形屮的口格单位止方 形数为3p+q,而它的黑格单位正方形数为p+3q. ??F为偶数，???nin矩形中黑、白条数相同，黑、白单位正方形总数也必相等?故有 3p+q二p+3q,从而p=q.所以“L”形的总数为2p个，即“L”形总数为偶数，所以mXn 一定是8的倍数. 图29?4 线段染色和点染色 下面介绍两类重要的染色问题. （1） 线段染色.较常见的一类染色问题是发样子组合数学中图论知识的所谓“边 染色”（或称“线段染色”），主要借助抽屉原则求解. 例4 （1947年匈牙利数学奥林匹克试题）世界上任何六个人中，一定有3 个人或者互相认识或者互相都不认识. 我们不直接证明这个命题，而来看与之等价的下述命题 例5 （1953年美国普特南数学竞赛题）空间六点，任三点不共线，任四点 不共面，成对地连接它们得十五条线段，用红色或蓝色染这些线段（一条线段只染 一种颜色）.求证:无论怎样染，总存在同色三角形. 证明 设A、B、C、D、E、F是所给六点?考虑以A为端点的线段AB、AC、AD、AE、 AF,由抽屉原则这五条线段屮至少有三条颜色相同，不妨设就是AB. AC. AD, FL它 们都染成红色.再来看ABCD的三边，如其中有一条边例如BC是红色的，则同色三角 形已出现（红色△ ABC） ； /fflABCD三边都不是红色的，则它就是蓝色的三角形，同 色三角形也现了.总之，不论在哪种情况下，都存在同色三角形. 如果将例4中的六个人看成例5中六点，两人认识的连红线，不认识的连蓝线，则例4 就变成了例5.例5的证明实际上用染色方法给出了例4的证明. 图 29-5 例6 （第6届