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

让我们为全力打造甘肃名校—甘肃省华亭县皇甫学校而共同努力吧!走进奥数,成就辉煌—皇甫学校培优竞赛教程(李敬之个人竞赛空间)143第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让我们为全力打造甘肃名校—甘肃省华亭县皇甫学校而共同努力吧!走进奥数,成就辉煌—皇甫学校培优竞赛教程(李敬之个人竞赛空间)144且三顶点同色的等腰直角三角形.那么，当平面点二染色以后，是否一定存在边长为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)三顶点同色的正三角形，要么存在边长为3a三顶点同色的正三角形.例4连接圆周上9个不同点的36条线段染成红色或蓝色，假设9点中每3点所确定的三角形都至少含有一条红色边.证明有4点，其中每两点的连线都是红色.证明设9个点依次为v1，v2，…，v9，首先证明必存在一点，设为v1，从v1出发的红色线段不是5条.事实上，若不然，如果都是5条，则共有红色线段295不是整数，矛盾.若从v1出发的红色线段至少有6条，设v1v2，v1v3，v1v4，v1v5，v1v6，v1v7均为红色，则由第26讲例8评注可知，连结v2，v3，v4，v5，v6，v7的让我们为全力打造甘肃名校—甘肃省华亭县皇甫学校而共同努力吧!走进奥数,成就辉煌—皇甫学校培优竞赛教程(李敬之个人竞赛空间)145线段中必有同色三角形.由题意知它只能为红色三角形，设为v2v3v4，则v1，v2，v3，v4四点中两两皆连红线.若从v1出发的红色线段至多4条，则v1出发的蓝色线段至少有4条，设为v1v2，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把平面划分成形为全等正六边形的房间，并按如下办法开门：若三面墙汇聚于一点，那么在其中两面墙上各开一个门，而第三面墙不开门.证明：不论沿多么曲折的路线走回原来的房间，所穿过的门的个数一定是偶数.分析与解为方便起见，我们把有公共门的两个房间叫做相邻的.用两种不同的颜色涂平面上的这些房间，使相邻的房间的颜色不同(如图).注意，从某种颜让我们为全力打造甘肃名校—甘肃省华亭县皇甫学校而共同努力吧!走进奥数,成就辉煌—皇甫学校培优竞赛教程(李敬之个人竞赛空间)146色的房间走到同种颜色的房间，必须经过另一种颜色的房间.显然，从任一房间走到同种颜色的房间，必定经过偶数个门.这样，利用图形和不同的颜色就可以解出这道题.例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色的有xi块，竖着盖住的有y块.2×2砖盖住阴影格处(不妨假定，余仿此).假定能够盖住.那么有：,144,16421yxyx让我们为全力打造甘肃名校—甘肃省华亭县皇甫学校而共同努力吧!走进奥数,成就辉煌—皇甫学校培优竞赛教程(李敬之个人竞赛空间)147相减得4(x1－x2)=2.因为x1与x2均为整数，这是不可能的.同步训练1.有10个表面涂满红漆的正方体，其棱长分别为2，4，6，…，20.若把这些正方体全部锯成棱长为1的小正方体，求有多少个至少一面有漆的小正方体.2.将直线上的每一个点都染上红、黄两色中的一种，证明：必存在同颜色的三个点，使得其中一点是另两点为端点的线段的中点.3.在二染色的平面上一定存在一个矩形，它的四个顶点同色.4.将正方体的每一个面分成四个相等的正方形，从三种不同颜色中任选一种给一个正方形染色，且使任何两个有公共边的正方形染不同的颜色.证明：每种颜色恰好染8个正方形.并举出一种染色方案.5.某班有50个学生，男女各占一半，他们围成一圈，席地而坐开营火晚会，求证：必能找到一位两旁都是女生的学生.6.在2n×2n的棋盘上，把相对角的两格剪去，则不能用若干块1×2的小棋盘(又称为多米诺骨牌)无重迭地覆盖这个缺角的大棋盘.7.有一种计算机软件只能复制一个边长为1的正方形的四个边，然后贴上。请问要构造出一幅2525的方格表，至少总共要贴上几个正方形？8.求证：8×8国际象棋盘不可能被剪成7个2×2正方形小棋盘与9个1×4小长条.9.若由“L”形的4个小方格，无重迭地拼成一个m×n的矩形.试证：m×n必为8的倍数.10.设A1，A2，…，A6是平面上的六点，其中任三点不共线.如果这些点之间任意连接了13条线段，证明：必存在四点，它们每两点之间都有线段连接.11.将一个棱长分别为36厘米、54厘米和72厘米的长方体切割成一些大小相同、棱长是整数厘米的正方体，然后给这些正方体的表面涂色。有一高为1４厘米、半径为6厘米圆柱体桶，装有漆，已知每立方厘米的这种漆可以涂色72平方厘米。问：将这个长方体最多能切割成多少个棱长相同的小正方体，用这桶漆可以将它们全部染色？12.用不相交的对角线把凸n边形划分成三角形，并且在多边形的每个顶点汇集奇数个三角形.证明：n能被3整除.13.把正三角形划分为n2个同样的小正三角形，把这些小正三角形的一部分标上号码1，2，…，m，使得号码相邻的三角形有相邻边.证明：m2≤n2-n+1.14.能否在如图所示边长为8的正三角形内找出一条环游路线：由某个小正三角形中心出发，经过每个小正三角形一次再回到出发点？