第25讲-染色问题与染色方法

1、让我们为全力打造甘肃名校甘肃省华亭县皇甫学校而共同努力吧!第25讲 染色问题与染色方法数学家像画家和诗人一样，是模式制造家。 G.H.哈代知识方法扫描染色是分类的直观表现，在数学竞赛中有大批以染色面目出现的问题，这类问题的特点是知识点少，逻辑性强，技巧性强，其内部蕴藏着深刻的数学思想.同时，染色作为一种解题手段也在数学竞赛中广泛使用.1. 染色问题解答染色问题，并不需要具备更多的数学知识，只需要具有缜密的思考能力和较强的分析能力.纵观各种染色试题，它与我们经常使用的数学方法紧密联系.大体上有如下几种方法：奇偶分析、归纳法、反证法、抽屉原理、构造法、组合计数等.2. 染色方法将问题中的对象适当进

2、行染色，有利于我们观察、分析对象之间的关系，像国际象棋的棋盘那样，我们可以把被研究的对象染上不同的颜色，许多隐藏的关系会变得明了，再通过对染色图形的处理达到对原问题的解决，这种解题方法称为染色法.常见的染色方式有：点染色、线段染色、小方格染色和对区域染色.经典例题解析例1 用任意的方式将平面上的每一点染上黑色或白色(称为二染色).求证：一定存在长为1的线段，它的两个端点同色.分析 在平面上任画一条长为1的线段，如图，若A，B两点同色，则结论已成立.若A，B两点不同色，为确定起见不妨设A为黑色，B为白色，以AB为边作正三角形ABC，则AB=BC=CA=1.这时C点要么是黑点，要么是白点.若C为黑

3、点，则AC为两个端点同色的长为1的线段.若C为白点，则BC为两个端点同色的长为1的线段.上述分析过程，其实已完成了证明过程，不过思路一旦找出，出现边长为1的正三角形的顶点A，B，C三点的构想是个关键，为此可得出如下简化的证明.证明 在平面上任作一个边长为1的正三角形，设三个顶点为A，B，C，由于平面上的每点只着黑、白两色之一，根据抽屉原理，A，B，C三点中必有两点同色，以这两同色点为端点的线段长度恰为1.评注 由例1可得更一般的结论：平面上的点二染色后，一定存在长为a(a0)的线段，它的两个端点同色.例2 对平面上的点黑白二染色后，一定存在三顶点同色的直角三角形.证明 对平面上的点黑白二染色，

4、根据例1的结论，存在边长为a(a0)的线段AB，它的两个端点同色(不妨设A，B同黑).以AB为边作正方形ABCD，对角线AC，BD交于点O，如图，如果D，O，C中有一个黑点，则该点与A，B构成三顶点同黑色的直角三角形.如果D，O，C全白色，则DOC就是三顶点全为白色的直角三角形.因此，二染色平面上一定存在顶点同色的直角三角形.评注 进一步由图证明可得：二染色平面上存在斜边要么为a，要么为a且三顶点同色的等腰直角三角形.那么，当平面点二染色以后，是否一定存在边长为1且顶点同色的等边三角形呢？例3将对这个问题作出回答.例3 用任意的方式，对平面上的每个点染黑色或白色，求证：一定存在一个边长为1或的

5、正三角形，它的三个顶点同色.证明 若存在边长为1且顶点同色的正三角形，则问题得证.若不存在边长为1且顶点同色的正三角形，则一定存在长为1的线段AB，两端点A，B异色.以AB=1为底作腰长为2的等腰三角形ABC，则C与A或B总有一对是异色的.不妨设长为2的线段AC两端点异色(见图(a).取AC的中点O，则O必与A，C之一同色(见图(b)，不妨设O与A同色.由于不存在边长为1的同色顶点的正三角形，所以以AO为一边的等边三角形的另外的顶点D和E必与A异色.此时，ECD就是一个边长为的顶点同色的正三角形.评注 事实上，当将平面分成宽度为的水平带状区域，且每个区域含下沿直线，不含上沿直线，使相邻的带状区

6、域染上不同颜色，对这样的平面二染色，任意边长为1的正三角形的三个顶点均不同色，但存在边长为的三顶点同色的三角形.由例3可得更一般的结论：平面上点二染色后，要么存在边长为a(a0)三顶点同色的正三角形，要么存在边长为 a三顶点同色的正三角形.例4 连接圆周上9个不同点的36条线段染成红色或蓝色，假设9点中每3点所确定的三角形都至少含有一条红色边.证明有4点，其中每两点的连线都是红色.证明 设9个点依次为v，v，v，首先证明必存在一点，设为v，从v出发的红色线段不是5条.事实上，若不然，如果都是5条，则共有红色线段不是整数，矛盾.若从v出发的红色线段至少有6条，设vv，vv，vv，vv，vv，vv

7、均为红色，则由第26讲例8评注可知，连结v，v，v，v，v，v的线段中必有同色三角形.由题意知它只能为红色三角形，设为vvv，则v，v，v，v四点中两两皆连红线.若从v出发的红色线段至多4条，则v出发的蓝色线段至少有4条，设为vv，vv，vv，vv，则v，v，v，v4点必然两两连红线.否则，例如若vv是蓝色的，则vvv是蓝色三角形，与题设至少有一边为红色矛盾.以上各例中，染色都是作为问题条件给出的，有时，染色方法也作为一种分类手段，因此，用形象直观地染色进行分类，也就成了一种很有特色的解题方法.例5 某桥牌俱乐部约定，四个人在一起打牌，同一方的两个人必须都曾合作过，或都不曾合作过.试证：只要有

8、五个人，就一定能凑齐四个人，按照约定在一起打牌.分析 本题证明采用构造一个涂色模型，使它与原问题间有一一对应的关系.如果模型中的问题证明了，那么原问题也相应地证明了.证明 五个人对应为空间五个点，如两个人合作过，那么对应两点连结红色线段，如两人不曾合作过，那么对应两点连结蓝色线段.因此原问题等价于证明涂色模型：空间五个点(无三点在一条直线上)，两两连线，涂上红色或蓝色之一.证明必存在两条无公共端点的同色线段.设五个点为A，A，A，A，A，不失一般性，不妨设AA为红色.观察AAA三条边的颜色.(1)如果AAA中有一条边为红色，设为AA，那么AA与AA是满足条件的两条线段；(2)如果AAA的三条边

9、均为蓝色，此时如AA，AA，AA与AA，AA，AA中如果有一条蓝色线段，那么问题就获证.如以AA是蓝色线段为例，那么AA与AA是满足条件的两条线段.反之，如果此时六条线段均为红色，如取AA与AA就是满足条件的两条线段.由于无公共端点的同色线段存在，证得原命题成立.例6 把平面划分成形为全等正六边形的房间，并按如下办法开门：若三面墙汇聚于一点，那么在其中两面墙上各开一个门，而第三面墙不开门.证明：不论沿多么曲折的路线走回原来的房间，所穿过的门的个数一定是偶数.分析与解 为方便起见，我们把有公共门的两个房间叫做相邻的.用两种不同的颜色涂平面上的这些房间，使相邻的房间的颜色不同(如图).注意，从某种

10、颜色的房间走到同种颜色的房间，必须经过另一种颜色的房间.显然，从任一房间走到同种颜色的房间，必定经过偶数个门.这样，利用图形和不同的颜色就可以解出这道题.例7 有一个20032003的棋盘和任意多个l2及13的矩形纸片，规定l2的纸片只能沿着棋盘的格线水平地放置，而13的纸片只能沿着棋盘的格线铅直地放置. 请问是否可依上述规定取用一些纸片不重叠地盖满整个棋盘？分析与解 先将棋盘的每一行黑白交错涂色，即第一行，第二行，第三行，依次为黑色，白色，黑色，.经过这样涂色后，开始时棋盘的黑白方格数之差为2003个.沿着棋盘的格线水平地放置12的纸片，每放上一个l2的纸片，就能盖住黑白方格各一个，所以这个

11、操作并不会改变黑白方格数之差；而每一个13的矩形纸片沿着棋盘的格线铅直地放置，所覆盖的三个方格都是同一颜色，所以每放置一片l3的矩形纸片，棋盘的黑白方格数之差就增加3个或减少3个.因为2003不是3的倍数，所以，依题述规定取用一些12及l3的矩形纸片是不可能不重叠地盖满整个棋盘的.例8 证明：如图，用15块4×1的矩形瓷砖与1块2×2的方形瓷砖，不能覆盖8×8的正方形地面(瓷砖不许断开！).分析 本例题有多种证法.一个共同点是：“不能覆盖”的证明，通常借助于反证法.证法1 将8×8的正方形地面的小方格，用黑、白色涂之，染色法如图.于是，每一块4×

12、;1瓷砖，不论怎样辅设，都恰好盖住两个白格两个黑格.15块4×1瓷砖共盖住30个白格和30个黑格.一块2×2瓷砖，无论怎么放，总是盖住“三白一黑”或“三黑一白”，即只能盖住奇数个白格和奇数个黑格.而盘中的黑白格总数相等(全为32个).所以用15块4×1砖与1块2×2砖不能完全覆盖8×8地面.证法2 将8×8的正方形地面的小方格.用代号为1，2，3，4的四种颜色涂之，染色法如(a).这时，4×1砖每次总能盖住1，2，3，4四色；而2×2砖不论放何处，总是不能同时盖住1，2，3，4四色.故是不可能的.证法3 同样用四色

13、涂之，涂法如(b).用反证法，设4×1砖横着盖住i色的有x块，竖着盖住的有y块.2×2砖盖住阴影格处(不妨假定，余仿此).假定能够盖住.那么有：相减得4(xx)=2.因为x与x均为整数，这是不可能的.同步训练1.有10个表面涂满红漆的正方体，其棱长分别为2，4，6，20.若把这些正方体全部锯成棱长为1的小正方体，求有多少个至少一面有漆的小正方体.2.将直线上的每一个点都染上红、黄两色中的一种，证明：必存在同颜色的三个点，使得其中一点是另两点为端点的线段的中点.3.在二染色的平面上一定存在一个矩形，它的四个顶点同色.4.将正方体的每一个面分成四个相等的正方形，从三种不同颜色中

14、任选一种给一个正方形染色，且使任何两个有公共边的正方形染不同的颜色.证明：每种颜色恰好染8个正方形.并举出一种染色方案.5.某班有50个学生，男女各占一半，他们围成一圈，席地而坐开营火晚会，求证：必能找到一位两旁都是女生的学生.6.在2n×2n的棋盘上，把相对角的两格剪去，则不能用若干块1×2的小棋盘(又称为多米诺骨牌)无重迭地覆盖这个缺角的大棋盘.7.有一种计算机软件只能复制一个边长为1的正方形的四个边，然后贴上。请问要构造出一幅的方格表，至少总共要贴上几个正方形？8.求证：8×8国际象棋盘不可能被剪成7个2×2正方形小棋盘与9个1×4小长条.9. 若由“L”形的4个小方格，无重迭地拼成一个m×n的矩形.试证：m×n必为8的倍数. 10. 设A，A，A是平面上的六点，其中任三点不共线.如果这些点之间任意连接了13条线段，证明：必存在四点，它们每两点之间都有线段连接.11. 将一个棱长分别为36厘米、54厘米和72厘米的长方体切割成一些大小相同、棱长是整数厘米的正方体，然后给这些正方体的表面涂色。有一高为1厘米、半径为6厘米圆柱体桶，装有漆，已知每立方厘米的这种漆可以涂色72平方厘米。问：将这个长方体最多能切割成多少个棱长相同的小正方体