染色问题与染色方法10633

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

1、染色问题与染色方法1.小方格染色问题最简单的染色问题是从一种民间游戏屮发展起来的方格盘上的染色问题•解决这类问题的方法后来又发展成为解决方格盘铺盖问题的重要技巧.例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行每行最多只有一个红

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

3、学通讯赛题)证明:用15块人小是4x1的矩形瓷砖和1块大小是2x2的矩形瓷砖，不能恰好铺盖8x8矩形的地面.分析将8x8矩形地面的一半染上一种颜色，另一半染上另种颜色，再用4"和2x2的矩形瓷砖去盖，如果盖住的两种颜色的小矩形不是一样多，则说明在给定条件不窕满铺盖不可证明如图29・3,川间隔为两格与副对角线平行的斜格同色的染色方式，以黑白两种颜色将整个地而的方格染色.显然，地而上黑、口格各有32个.每块4幻的矩形砖不论是横放还是竖盖，且不论盖在何处，总是占据地面上的两个口格、两个黑格，故15块4x1的矩形砖铺盖后还剩两个黑格和两个白格.但由丁为副对角线平

4、行的斜格总是同色，而与主对角线平行的相邻格总是异色，所以，不论怎样放置，一块2x2的矩形砖，总是盖住三黑一白或一黑三白•这说明剩下的一块2x2矩形砖无论如何盖不住剩下的二黑二口的地面.从而问题得证.图29-3例3（1986年北京初二数学竞赛题）如图29-4（1）是4个1"的正方形组成的“L”形,用若干个这种“L”形碘纸片无重迭拼成一个ms（长为m个单位，宽为n个单位）的矩形如图29-4（2）•试证明mn必是8的倍数.证明Vmxn矩形由“L”形拼成,Amxn是4的倍数,・・.m、n中必有一个是偶数,不妨设为m.把ms矩形中的m列按一列黑、一列白间隔染色（如

5、图29・4（2））,则不论形在这矩形中的放置位置如何（“L”形的放置，共有8种可能），“L”形或占有3口一黑四个单位正方形（第一种），或占有3黑一白四个单位正方形（第二种）.设第一种“L”形共有p个，第二种U形共q个，则mxn矩形中的白格单位正方形数为3p+q,而它的黑格单位正方形数为p+3q.・・・ni为偶数，・・・nixn矩形中黑、白条数相同，黑、白单位正方形总数也必相等.故有3p+q=p+3q,从而p二q.所以形的总数为2p个，即形总数为偶数，所以mxn-定是8的倍数.图29・41.线段染色和点染色下面介绍两类重要的染色问题.（1）线段染色.较常见

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

7、条颜色相同，不妨设就是AB、AC、AD,且它们都染成红色.再来看ABCD的三边，如其中有一条边例如BC是红色的，则同色三角形已出现（红色厶ABC）；如ABCD三边都不是红色的，则它就是蓝色的三角形，同色三角形也现了.总Z,不论在哪种情况下,都存在同色三角形.如果将例4中的六个人看成例5中六点，两人认识的连红线，不认识的连蓝线，则例4就变成了例5.例5的证明实际上用染色方法给出了例4的证明.A0图29-5例6（第6届国际数学奥林匹克试题）冇17位科学家,其中每一个人和其他所冇人的人通信,他们的通信小只讨论三个题目.求证:至少有三个科学家相互之间讨论同一个题

8、目•证明用平面上无三点共线的17个点A

9、,A2,...,Ah分别表示17位科学家