竞赛讲座14染色问题与染色方法

《竞赛讲座14染色问题与染色方法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、竞赛讲座14-染色问题与染色方法1.小方格染色问题最简单的染色问题是从一种民间游戏屮发展起来的方格盘上的染色问题•解决这类问题的方法后来又发展成为解决方格盘铺盖问题的重要技巧.例1如图29-1（a）,3行7列小方格每一个染上红色或蓝色.试证:存在一个矩形，它的四个角上的小方格颜色相同.】234567a)图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

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

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

4、砖，总是盖住三黑一白或一黑三白.这说明剩下的一•块2X2矩形砖无论如何盖不住剩下的二黑二白的地面.从而问题得证.图29-3例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”形的放置，共有8种可能），形或占冇3白一黑四个单位正方形（第

5、一种），或占冇3黑一白四个单位正方形（第二种）.设第一种“L”形共冇p个，第二种形共q个，则mXn矩形中的白格单位正方形数为3p+q,而它的黑格单位正方形数为p+3q・•・・ni为偶数，・・・mXri矩形中黑、口条数相同，黑、口单位止方形总数也必相等•故有3p+q二p+3q,从而p二q.所以“L”形的总数为2p个，即“L”形总数为偶数，所以mXn一定是8的倍数.图29・41.线段染色和点染色卜•面介绍两类重耍的染色问题.（1）线段染色.较常见的一类染色问题是发样子组合数学屮图论知识的所谓“边染色”（或称“线段染色”），主耍借助抽屉原则求解.例4（1947年匈牙利数学奥林匹克试题）世界上任何六个

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

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