初中数学八年级竞赛强化辅导讲义31讲：第 26 讲 染色问题与染色方法（含解析）

第 26 讲 染色问题与染色方法
知识方法
染色是分类的直观表现，在数学竞赛中有大批染色问题出现，这类问题的特点是知识点少，逻辑性强，技巧性强，其内部蕴含着深刻的数学思想.同时，染色作为一种解题手段也在数学竞赛中广泛使用.
1.染色问题
解答染色问题，并不需要具备更多的数学知识，只需要具有缜密的思考能力和较强的分析能力.纵观各种染色试题，它与我们经常使用的数学方法紧密联系.大体上有如下几种方法：奇偶分析、归纳法、反证法、抽屉原理、构造法、组合计数等.
2.染色方法
将问题中的对象适当进行染色，有利于我们观察、分析对象之间的关系，像国际象棋的棋盘那样，我们可以把被研究的对象染上不同的颜色，许多隐藏的关系就会变得明了，再通过对染色图形的处理达到对原问题的解决，这种解题方法称为染色法.常见的染色方式有点染色、线段染色、小方格染色和对区域染色.
经典例题解析
【例26-1】 用任意的方式将平面上的每一点染上黑色或白色(称为二染色).求证：一定存在长为 1 的线段，它的两个端点同色.
分析 在 平面上任画一条长为1的线段，如图26-1所示，若A、B两点同色，则结论已成立.若A、B两点不同色，为确定起见不妨设 A 为黑色,B 为白色,以AB 为边作正三角形ABC,则AB=BC=CA=1.这时 C 点要么是黑点，要么是白点.若C 为黑点，则AC 为两个端点同色的长为1的线段.若C 为白点，则BC 为两个端点同色的长为1 的线段.
第26讲 染色问题与染色方法
上述分析过程，其实已完成了证明过程，不过思路一旦找出，出现边长为1的正三角形的顶点 A、B、C三点的构想是个关键，为此可得出如下简化的证明.
证明 在平面上任作一个边长为1的正三角形，设三个顶点为A、B、C，由于平面上的每点只着黑、白两色之一，根据抽屉原理，A、B、C三点中必有两点同色，以这两同色点为端点的线段长度恰为 1.
评注 由例26-1可得更一般的结论：平面上的点二染色后，一定存在长为a(a>0)的线段，它的两个端点同色.
【例26-2】 对平面上的点黑白二染色后，一定存在三顶点同色的直角三角形.
证明 对平面上的点黑白二染色，根据例 26-1的结论，存在边长为a(a>0)的线段AB，它的两个端点同色(不妨设A、B同黑).以 AB 为边作正方形 ABCD,对角线 AC、BD 交于点 O,如图 26-2所示，如果 D、O、C中有一个黑点，则该点与 A、B构成三顶点同黑色的直角三角形.如果 D、O、C全白色，则△DOC 就是三顶点全为白色的直角三角形.因此，二染色平面上一定存在顶点同色的直角三角形.
例26-2进一步由图证明可得：二染色平面上存在斜边要么为a，要么为 a 且三顶点同色的等腰直角三角形.
那么，当平面点二染色以后，是否一定存在边长为1且顶点同色的等边三角形呢 例 26-3将对这个问题作出回答.
【例26-3】 用任意的方式，对平面上的每个点染黑色或白色，求证：一定存在一个边长为1 的正三角形，它的三个顶点同色
证明 若存在边长为1 且顶点同色的正三角形，则问题得证.
若不存在边长为1且顶点同色的正三角形，则一定存在长为1 的线段 AB，两端点A、B异色.以AB=1 为底作腰长为 2 的等腰三角形 ABC,则 C 与 A 或 B 总有一对是异色的.不妨设长为2的线段 AC 两端点异色，图26-3(a)所示.
取 AC 的中点 O,则 O必与 A.、C 之一同色,如图 26-3(b)所示,不妨设O与A 同色.由于不存在边长为1的同色顶点的正三角形，所以，以AO为一边的等边三角形的另外的顶点D和E必与A 异色.此时，△ECD 就是一个边长 的顶点同色的正三角形
评注 事实上，可将平面分成宽度为 的水平带状区域，且每个区域含下沿直线，不含上沿直线，使相邻的带状区域染上不同颜色，对这样的平面二染色，则任意边长为1的正三角形的三个顶点均不同色，但存在边长 的三顶点同色的三角形
由例26-3可得更一般的结论：平面上点二染色后，要么存在边长为a(a>0)的三顶点同色的正三角形，要么存在边长 a的三顶点同色的正三角形
【例26-4】 将连接圆周上9个不同点的36条线段染成红色或蓝色，假设9点中每3点所确定的三角形都至少含有一条红色边.证明：有4个点，其中每两个点的连线都是红色.
证明 设9个点依次为 v ，v ，…，v ，首先证明必存在一点，设为 v ，从 v 出发的红色线段不是5条.如果都是5条，那么共有红色线段条数 不是整数，矛盾.
若从 v 出发的红色线段至少有6条，设v v 、v v 、v v 、v v 、v v 、v v 均为红色，则由第25讲例 25-8评注可知,v 、v 、v 、v 、v 、v 两两相连的线段中必有同色三角形.由题意知它只能为红色三角形,设为△v v v ,则 v 、v 、v ,v 四点中两两皆连红线.
若从v 出发的红色线段至多4条，则v 出发的蓝色线段至少有4 条，设为V1V2、V V 、v v 、v v ,则 v 、v 、v 、v 四点必然两两连红线.否则,若v v 是蓝色的,则△v v v 是蓝色三角形，与题设至少有一边为红色矛盾.
以上各例中，染色都是作为问题条件给出的，有时，染色方法也作为一种分类手段，因此，用形象直观地染色进行分类，也就成了一种很有特色的解题方法.
【例26-5】 某桥牌俱乐部约定，四个人在一起打牌，同一方的两个人必须都曾合作过，或都不曾合作过.试证：只要有五个人，就一定能凑齐四个人，按照约定在一起打牌.
分析 本题证明采用构造一个染色模型，使它与原问题间有一一对应的关系.如果模型中的问题证明了，那么原问题也相应地证明了.
证明 五个人对应为空间五个点，若两个人合作过，那么对应两点连接红色线段，若两人不曾合作过，那么对应两点连接蓝色线段.因此原问题等价于证明涂色模型：空间五个点(无三点在一条直线上)，两两连线，涂上红色或蓝色之一.证明必存在两条无公共端点的同色线段.
设五个点为A 、A 、A 、A 、A ,不失一般性,不妨设A A 为红色.观察△A A A 三条边的颜色.
(1) 如果△A A A 中有一条边为红色,设为A A ,那么 A A 与A A 是满足条件的两条线段.
(2) 如果△A A A 的三条边均为蓝色，此时如果. 与 A A 中有一条蓝色线段，那么问题就获证.如以A A 是蓝色线段为例，那么 A A 与 A A 是满足条件的两条线段.反之，如果此时六条线段均为红色，如取 A A 与 A A 就是满足条件的两条线段.
由于无公共端点的同色线段存在，证得原命题成立.
【例26-6】 把平面划分成形状为全等正六边形的房间，并按如下办法开门：若三面墙汇聚于一点，则在其中两面墙上各开一个门，而第三面墙不开门.证明：不论沿多么曲折的路线走回原来的房间，所穿过的门的个数一定是偶数.
分析与解 为方便起见，我们把有公共门的两个房间叫作相邻的.用两种不同的颜色涂平面上的这些房间，使相邻的房间的颜色不同，如图 26-4所示.注意，从某种颜色的房间走到同种颜色的房间，必须经过另一种颜色的房间.显然，从任一房间走到同种颜色的房间，必定经过偶数个门.这样，利用图形和不同的颜色就可以解出这道题.
【例26-7】 有一个 2003×2003的棋盘和任意多个1×2及1×3的矩形纸片，规定1×2 的纸片只能沿着棋盘的格线水平地放置，而1×3的纸片只能沿着棋盘的格线竖直地放置.请问：是否可依上述规定取用一些纸片不重叠地盖满整个棋盘
分析与解 先将棋盘的每一列黑白交错涂色，即第一列、第二列、第三列……，依次为黑色、白色、黑色……经过这样涂色后，开始时棋盘的黑白方格数之差为 2003个.
沿着棋盘的格线水平地放置1×2的纸片，每放上一个1×2的纸片，就能盖住黑白方格各一个，所以这个操作并不会改变黑白方格数之差；而每一个1×3的矩形纸片沿着棋盘的格线竖直地放置，所覆盖的三个方格都是同一颜色，所以每放置一片1×3的矩形纸片，棋盘的黑白方格数之差就增加3个或减少3个.
因为2003不是3的倍数，所以，依题述规定取用一些1×2 及 1×3的矩形纸片是不可能不重叠地盖满整个棋盘的.
【例26-8】 证明:如图26-5 所示,用15块4×1的矩形瓷砖与1块2×2的方形瓷砖，不能覆盖8×8的正方形地面(瓷砖不许断开！).
功桩 本例题有多种证法.一个共同点是：“不能覆盖”的证明，通常借助于反证法.
证法1 将8×8的正方形地面的小方格，用黑、白色涂之，染色法如图26-6(a)所示.于是，每一块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的四种颜色涂之，染色法如图 26-6(b)所示.
这时，4×1瓷砖每次总能盖住1、2、3、4四色；而2×2瓷砖不论放何处，总是不能同时盖住1、2、3、4 四色.故是不可能的.
证法3 同样用四色涂之，涂法如图26-6(c)所示.
用反证法，设4×1瓷砖横着盖住i色的有x； 块，竖着盖住的有y块.2×2瓷砖盖住阴影格处(不妨假定，余仿此).假定能够盖住.那么有
两式相减得 即
因为x 与x 均为整数，所以这是不可能的.
强化训练
1.有10个表面涂满红漆的正方体，其棱长分别为2，4，6，…，20.若把这些正方体全部锯成棱长为1的小正方体，求有多少个至少一面有漆的小正方体.
2.将直线上的每一个点都染上红、黄两色中的一种，证明：必存在同颜色的三个点，使得其中一点是另两点为端点的线段的中点.
3.在二染色的平面上一定存在一个矩形，它的四个顶点同色.
4.将正方体的每一个面分成四个相等的正方形，从三种不同颜色中任选一种给一个正方形染色，且使任何两个有公共边的正方形染不同的颜色.证明：每种颜色恰好染8个正方形，并给出一种染色方案.
5.某班有50个学生，男女各占一半，他们围成一圈，席地而坐开篝火晚会，求证：必能找到一位两旁都是女生的学生.
6.在2n×2n 的棋盘上，把相对角的两格剪去，则不能用若干块1×2 的小棋盘(又称为多米诺骨牌)无重叠地覆盖这个缺角的大棋盘.
7.有一种计算机软件只能复制一个边长为1的正方形的四个边，然后贴上.请问：要构造出一幅25×25的方格表，至少总共要贴上几个正方形
8.求证：8×8国际象棋盘不可能被剪成7个2×2的正方形小棋盘与9个1×4小长条.
9.若由 L形的4个小方格无重叠地拼成一个m×n的矩形.试证：m×n必为8的倍数.
10.设A ，A ，…，A 是平面上的六点，其中任三点不共线.如果这些点之间任意连接了13条线段.证明：必存在四点，它们每两点之间都有线段连接.
11.将一个棱长分别为36cm、54cm和72cm的长方体切割成一些大小相同、棱长是整数厘米的正方体，然后给这些正方体的表面涂色.有一高为14cm、半径为6cm的圆柱体桶，装有漆，已知每立方厘米的这种漆可以涂色 .问：将这个长方体最多能切割成多少个棱长相同的小正方体，可以用这桶漆将它们全部染色
12.用不相交的对角线把凸n边形划分成若干个三角形，并且在多边形的每个顶点汇集奇数个三角形.证明：n能被 3 整除.
13.把正三角形划分为n 个同样的小正三角形，把这些小正三角形的一部分标上号码1，2，…，m，使得号码相邻的三角形有相邻边.证明：
14.能否在如图26-7所示的边长为8的正三角形内找出一条环游路线：由某个小正三角形中心出发，经过每个小正三角形一次再回到出发点
1.【答案】8000个.
2.【答案】证明：在直线上任取三点，必有两点同色，不妨设A、B 同为红色,取 AB 中点C,若 C 也是红色，则结论已成立，如答图26-1(a)所示；若C为黄色,则再取 D、E,使 DA=AB=BE.若 D、E中有红色点，比如D 是红点，则D、A、B三点合乎要求；若D、E均不是红点，即D、E均为黄点，这时 D、C、E 三点合乎要求,如答图26-1(b)所示.
3.【答案】证明：取三条水平直线与九条竖直直线，我们仅考虑这些直线的27 个交点.由于每列三个点都涂两种颜色，共有 种不同的涂色方式，所以九条竖直直线中存在两条，其交点处具有同样的涂色方式.我们选择这两条竖直直线，在每条线上两种颜色的三个点中间，一定能找到两个染有同样颜色的点.由于这两直线上三点的涂色状态分布相同，所以就找到这四个同色点恰为一个矩形的四个顶点.
4.【解析】考查立方体的位于顶点处的三个正方形.按照条件，这三个正方形必须染三种颜色.由于总共有24个正方形分布在8个顶点处，所以每种颜色要染8个正方形.答图26-2所示是满足题目条件的染色例子，其中1、2、3是三种颜色的代号.
5.【解析】将50个座位间隔涂成黑白两色.假设不论如何围坐都不能找到一位两旁都是女生的学生，那么25个黑色标记的座位最多只能坐12个女生，否则至少有两个女生中间坐一个学生.同样，25个白色标记的座位也最多只能坐12个女生，因此50个座位中最多只能坐24 个女生，与题设矛盾.
6.【解析】若把缺角的大棋盘上的格黑白相间染色，则其中一种颜色的格数(比如说黑色)比另一种颜色(白色)的格数多2.但是用1×2 的小棋盘覆盖这一大棋盘的格，无论位置如何，必恰覆盖一个黑格和一个白格.因此，如果能无重叠地覆盖整个大棋盘，那么黑格数与白格数必相等.与题设矛盾.
7.【答案】360.
【解析】以中心方格为正中央，将25×25 的方格表区分成12个宽度为1的方形环，则由中心往外数的第k 个环由8k个方格所组成.所有在最外围一环的方格都要复制，也就是25×25 方格表的周界.在其他的环中，任何两个相邻(有公共边)的方格，必须有一个要复制.因此，至少要复制8×12+(1+2+…+11)×4=360.另一方面,如果我们将25×25 的方格表以黑白相间的方式涂色，最角落是涂黑色.我们可以复制在最外围一环的方格及所有涂白色的方格，即可造出一幅25×25的方格表.所以，至少总共要贴上 360 个边长为 1 的正方形.
8.【答案】证明：如答图 26-3所示方法染色，每个2×2正方形或横放的1×4长条都包含 2 个黑格与 2个白格，而竖放的1×4 长条包含 4 个黑格或4个白格，因此竖放长条必有偶数个.同样横向染色即知，横放长条也是偶数个，所以长条数为偶数，而9是奇数.
9.【答案】证明：由于每个L形有 4 个小方格，若k个 L形恰好拼成一个 m×n 的矩形,则 mn=4k.我们证明k 是偶数即可.
由于 mn=4k，所以m、n 中必有一个为偶数，不妨设 m 为偶数.把棋盘的列交错地涂上黑、白两种颜色，则两种颜色的方格各有 2k个.
每个 L形占据奇数个(1个或3个)白格，由于白格的总数是偶数2k，如果L形纸片为奇数个(即k为奇数)，则奇数个奇数之和为奇数，不可能等于偶数 2k.所以k必为偶数.故是8的倍数.
10.【答案】证明：将已连接的 13 条线段全染成红色，还未连上的两条用蓝线连上(因为所有两点相连共有 15 条线段).可知，必有一个同色三角形.现在的蓝色线只有两条，所以同色三角形必为红色的.不妨设△A A A 是红色的，这时A 、A 、A 三点中必有一点,它与A 、A 、A 的连线全为红色(因为只有两条蓝线).设A A 、A A 、A A 全为红色,则 A 、A 、A 、A 为所求四点.
11.【答案】192.
【解析】桶的容积是 ，可以涂色
设切割出的小正方体的棱长是 mcm，表面积是 由题设可知m 应当是正整数.长方体的体积是 所切割出的小正方体是 个.所有切割出的小正方体总的表面积是 为了确保这桶漆可以将所有的小正方体的表面染上颜色，应当有不等式
解不等式得
因为m 必须是36、54 和72 的公约数，即所取的值只能是1、2、3、6、9、18之一.并且 m 的数值越小，所切割出的正方体就越多.经验算 >6，所以，m=9.将长方体切割成一些棱长相同的小正方体的个数是： (个).
故最多能将这个长方体切割成192个相同的、棱长是9cm的正方体.
12.【答案】证明：用黑、白两种颜色给这些三角形着色，使任何有公共边的两个三角形颜色不同.由于已知凸n边形的每个顶点都是奇数个三角形的顶点，因此这凸 n边形的每条边都属于同一颜色的三角形，不妨设为黑色(见答图 26-4)，进而推知黑色三角形比白色三角形多 n个角.
设n边形被分为k 个黑色三角形和l 个白色三角形，则黑色三角形和白色三角形的角的数目之差为n=3k-3l=3(k-l),即n能被3整除.
13.【答案】证明：把正三角形的三边都分为 n 等分，连接每两边对应的分点，即可得n 个同样的小正三角 形.对这 n 个 小 正三 角 形 采 用如答图 26-5所示方法染色，这时黑色三角形共有1+ 个，而白色三角形共有 1+2 个.
显然两个有相邻号码的三角形染有不同颜色，因而标号码的黑三角形仅能比白三角形多1，所以编号的三角形个数不超过 个.
14.【答案】不能.
【解析】仿题 13染色.