染色问题与染色方法10956

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

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列染两色不存在顶点同色矩形的例子如图29-2.这说明3行7列是染两色存在顶点同色的矩形的最小方格盘了.至今，染k色而存在顶点同色的矩形的最小方格盘是什么还不得而知.图29-2例2（笫2届全国部分省市初屮数

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

4、山丁与副对角线平行的斜格总是同色，而与主对角线平行的相邻格总是异色，所以，不论怎样放置，一块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矩形中的

5、m列按一列黑、一列白间隔染色（如图29-4（2））,则不论形在这矩形屮的放置位置如何（“L”形的放置，共有8种可能），“L”形或占有3白一黑四个单位正方形（笫一种），或占有3黑一白四个单位正方形（第二种）•设第一种“L”形共有p个，第二种“L”形共q个，则mXn矩形屮的口格单位止方形数为3p+q,而它的黑格单位正方形数为p+3q.・・F为偶数，・・・ni>

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

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

8、论三个题目.求证:至少有三个科学家相互之间讨论同一个题目.证明用平面上无三点共线的17个点A“