下载文档原格式
第25讲染色问题与染色方法数学家像画家和诗人一样，是模式制造家。
——G.H.哈代知识方法扫描染色是分类的直观表现，在数学竞赛中有大批以染色面目出现的问题，这类问题的特点是知识点少，逻辑性强，技巧性强，其内部蕴藏着深刻的数学思想.同时，染色作为一种解题手段也在数学竞赛中广泛使用.1. 染色问题解答染色问题，并不需要具备更多的数学知识，只需要具有缜密的思考能力和较强的分析能力.纵观各种染色试题，它与我们经常使用的数学方法紧密联系.大体上有如下几种方法：奇偶分析、归纳法、反证法、抽屉原理、构造法、组合计数等.2. 染色方法将问题中的对象适当进行染色，有利于我们观察、分析对象之间的关系，像国际象棋的棋盘那样，我们可以把被研究的对象染上不同的颜色，许多隐藏的关系会变得明了，再通过对染色图形的处理达到对原问题的解决，这种解题方法称为染色法.常见的染色方式有：点染色、线段染色、小方格染色和对区域染色.经典例题解析例 1 用任意的方式将平面上的每一点染上黑色或白色(称为二染色).求证：一定存在长为1的线段，它的两个端点同色.分析在平面上任画一条长为1的线段，如图，若A，B两点同色，则结论已成立.若A，B两点不同色，为确定起见不妨设A为黑色，B为白色，以AB为边作正三角形ABC，则AB=BC=CA=1.这时C点要么是黑点，要么是白点.若C为黑点，则AC为两个端点同色的长为1的线段.若C为白点，则BC为两个端点同色的长为1的线段.上述分析过程，其实已完成了证明过程，不过思路一旦找出，出现边长为1的正三角形的顶点A，B，C三点的构想是个关键，为此可得出如下简化的证明.证明在平面上任作一个边长为1的正三角形，设三个顶点为A，B，C，由于平面上的每点只着黑、白两色之一，根据抽屉原理，A，B，C三点中必有两点同色，以这两同色点为端点的线段长度恰为1.评注由例1可得更一般的结论：平面上的点二染色后，一定存在长为a(a ＞0)的线段，它的两个端点同色.例2 对平面上的点黑白二染色后，一定存在三顶点同色的直角三角形.证明对平面上的点黑白二染色，根据例1的结论，存在边长为a(a＞0)的线段AB，它的两个端点同色(不妨设A，B同黑).以AB为边作正方形ABCD，对角线AC，BD交于点O，如图，如果D，O，C中有一个黑点，则该点与A，B构成三顶点同黑色的直角三角形.如果D，O，C全白色，则△DOC就是三顶点全为白色的直角三角形.因此，二染色平面上一定存在顶点同色的直角三角形.评注 进一步由图证明可得：二染色平面上存在斜边要么为a ，要么为2a 且三顶点同色的等腰直角三角形.那么，当平面点二染色以后，是否一定存在边长为1且顶点同色的等边三角形呢？例3将对这个问题作出回答.例3 用任意的方式，对平面上的每个点染黑色或白色，求证：一定存在一个边长为1或3的正三角形，它的三个顶点同色.证明 若存在边长为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 就是一个边长为3的顶点同色的正三角形.评注 事实上，当将平面分成宽度为23的水平带状区域，且每个区域含下沿直线，不含上沿直线，使相邻的带状区域染上不同颜色，对这样的平面二染色，任意边长为1的正三角形的三个顶点均不同色，但存在边长为3的三顶点同色的三角形.由例3可得更一般的结论：平面上点二染色后，要么存在边长为a (a ＞0)三顶点同色的正三角形，要么存在边长为3 a 三顶点同色的正三角形.例4 连接圆周上9个不同点的36条线段染成红色或蓝色，假设9点中每3点所确定的三角形都至少含有一条红色边.证明有4点，其中每两点的连线都是红色.证明 设9个点依次为v 1，v 2，…，v 9，首先证明必存在一点，设为v 1，从v 1出发的红色线段不是5条.事实上，若不然，如果都是5条，则共有红色线段295 不是整数，矛盾. 若从v 1出发的红色线段至少有6条，设v 1v 2，v 1v 3，v 1v 4，v 1v 5，v 1v 6，v 1v7均为红色，则由第26讲例8评注可知，连结v2，v3，v4，v5，v6，v7的线段中必有同色三角形.由题意知它只能为红色三角形，设为v2v3v4，则v1，v 2，v3，v4四点中两两皆连红线.若从v1出发的红色线段至多4条，则v1出发的蓝色线段至少有4条，设为v 1v2，v1v3，v1v4，v1v5，则v2，v3，v4，v54点必然两两连红线.否则，例如若v2v3是蓝色的，则△v1v2v3是蓝色三角形，与题设至少有一边为红色矛盾.以上各例中，染色都是作为问题条件给出的，有时，染色方法也作为一种分类手段，因此，用形象直观地染色进行分类，也就成了一种很有特色的解题方法.例5某桥牌俱乐部约定，四个人在一起打牌，同一方的两个人必须都曾合作过，或都不曾合作过.试证：只要有五个人，就一定能凑齐四个人，按照约定在一起打牌.分析本题证明采用构造一个涂色模型，使它与原问题间有一一对应的关系.如果模型中的问题证明了，那么原问题也相应地证明了.证明五个人对应为空间五个点，如两个人合作过，那么对应两点连结红色线段，如两人不曾合作过，那么对应两点连结蓝色线段.因此原问题等价于证明涂色模型：空间五个点(无三点在一条直线上)，两两连线，涂上红色或蓝色之一.证明必存在两条无公共端点的同色线段.设五个点为A1，A2，A3，A4，A5，不失一般性，不妨设A1A2为红色.观察△A3A4A5三条边的颜色.(1)如果△A3A4A5中有一条边为红色，设为A3A4，那么A1A2与A3A4是满足条件的两条线段；(2)如果△A3A4A5的三条边均为蓝色，此时如A1A3，A1A4，A1A5与A2A3，A2A4，A2A5中如果有一条蓝色线段，那么问题就获证.如以A1A3是蓝色线段为例，那么A1A3与A4A5是满足条件的两条线段.反之，如果此时六条线段均为红色，如取A1A3与A2A4就是满足条件的两条线段.由于无公共端点的同色线段存在，证得原命题成立.例6把平面划分成形为全等正六边形的房间，并按如下办法开门：若三面墙汇聚于一点，那么在其中两面墙上各开一个门，而第三面墙不开门.证明：不论沿多么曲折的路线走回原来的房间，所穿过的门的个数一定是偶数.分析与解为方便起见，我们把有公共门的两个房间叫做相邻的.用两种不同的颜色涂平面上的这些房间，使相邻的房间的颜色不同(如图).注意，从某种颜色的房间走到同种颜色的房间，必须经过另一种颜色的房间.显然，从任一房间走到同种颜色的房间，必定经过偶数个门.这样，利用图形和不同的颜色就可以解出这道题.例7 有一个2003⨯2003的棋盘和任意多个l⨯2及1⨯3的矩形纸片，规定l⨯2的纸片只能沿着棋盘的格线水平地放置，而1⨯3的纸片只能沿着棋盘的格线铅直地放置. 请问是否可依上述规定取用一些纸片不重叠地盖满整个棋盘？分析与解先将棋盘的每一行黑白交错涂色，即第一行，第二行，第三行，…，依次为黑色，白色，黑色，….经过这样涂色后，开始时棋盘的黑白方格数之差为2003个.沿着棋盘的格线水平地放置1⨯2的纸片，每放上一个l⨯2的纸片，就能盖住黑白方格各一个，所以这个操作并不会改变黑白方格数之差；而每一个1⨯3的矩形纸片沿着棋盘的格线铅直地放置，所覆盖的三个方格都是同一颜色，所以每放置一片l⨯3的矩形纸片，棋盘的黑白方格数之差就增加3个或减少3个.因为2003不是3的倍数，所以，依题述规定取用一些1⨯2及l⨯3的矩形纸片是不可能不重叠地盖满整个棋盘的.例8证明：如图，用15块4×1的矩形瓷砖与1块2×2的方形瓷砖，不能覆盖8×8的正方形地面(瓷砖不许断开！).分析本例题有多种证法.一个共同点是：“不能覆盖”的证明，通常借助于反证法.证法1将8×8的正方形地面的小方格，用黑、白色涂之，染色法如图.于是，每一块4×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同样用四色涂之，涂法如(b).用反证法，设4×1砖横着盖住i色的有x块，竖着盖住的有y块.2×2砖盖i住阴影格处(不妨假定，余仿此).假定能够盖住.那么有：⎩⎨⎧=+=+,144,16421y x y x 相减得4(x 1－x 2)=2.因为x 1与x 2均为整数，这是不可能的.同步训练1.有10个表面涂满红漆的正方体，其棱长分别为2，4，6，…，20.若把这些正方体全部锯成棱长为1的小正方体，求有多少个至少一面有漆的小正方体.2.将直线上的每一个点都染上红、黄两色中的一种，证明：必存在同颜色的三个点，使得其中一点是另两点为端点的线段的中点.3.在二染色的平面上一定存在一个矩形，它的四个顶点同色.4.将正方体的每一个面分成四个相等的正方形，从三种不同颜色中任选一种给一个正方形染色，且使任何两个有公共边的正方形染不同的颜色.证明：每种颜色恰好染8个正方形.并举出一种染色方案.5.某班有50个学生，男女各占一半，他们围成一圈，席地而坐开营火晚会，求证：必能找到一位两旁都是女生的学生.6.在2n ×2n 的棋盘上，把相对角的两格剪去，则不能用若干块1×2的小棋盘(又称为多米诺骨牌)无重迭地覆盖这个缺角的大棋盘.7.有一种计算机软件只能复制一个边长为1的正方形的四个边，然后贴上。
