棋盘染色问题-网上

学科：奥数教学内容：第7讲简单染色问题知识网络数学竞赛中的“染色”一般包括两个方面：染色问题和染色方法。如果染色作为题目的条件给出，那么一般要考虑的是存在与否，有何性质以及有多少种染法等，这就是染色问题。如果题目中没有提到染色，在解题中运用形象、直观的染色来进行分类，帮助解决问题这就是染色方法。重点·难点我们在前面几讲中也涉及到染色问题。一般来说，染色问题涉及分类、奇偶性、排列组合等多方面的知识。因此如何应用这些相关的知识点解题，是很关键的。在下面的例题中也可以看出，这些知识在解题中的应用。学法指导染色作为一种数学思维方法，可以用来推证说理，使一些难以讲清楚的问题一目了然。有时染色题可能很难想清楚，比如“四色问题”，但可以运用上面的知识点解决一些比较简单的染色问题。经典例题[例1]如图1所示，一个长方形被分成6块区域，若给每一块区域都染色，并且要求相邻的区域颜色不同，请问至少需要多少种不同的颜色？思路剖析由于A、B、C两两相邻，所以要使相邻的区域颜色不同，至少A、B、C的颜色不能相同。但是，仅有3种颜色够不够呢？对于区域较少的情形可以逐一试验，如果区域较多时，可以考虑取有多相邻区域的区域来先染色。解答先考虑有最多相邻区域的A，染第1种颜色；其次考虑与A相邻的B、C、D、E中，有最多相邻区域的E，染第2种颜色；再考虑B，它与A、E都相邻，染第3种颜色。由C和E不相邻，故C可用第2种颜色，D与B不相邻，D可用第3种颜色，F和A不相邻，F可染第一种颜色。这样，用第一种颜色染在A和F上，用第二种颜色染在C和E上，用第三种颜色染在B和D上即可满足题意要求。所以，满足条件的染色，至少需要三种颜色。[例2]用红、黄、蓝三种颜色涂一个正方体的六个面，两个面涂一种颜色，那么共有几种涂法？思路剖析本题要用到分类和组合的一些思想，同进，在解题时要注意，如果两种所谓不同涂法的正方体经翻转或旋转之后得到同样的效果，它只能是一种涂法。所以，我们可以取定一种颜色，就它所涂的两个面相对或相邻来分类。解答我们将染红的两个面分为相对和相邻的两种情形来考虑：（1）红色的两面相对，不妨设上面和下面是红色的，那么由于黄色的两面可以相对也可以相邻，并且一旦黄色的面确定后蓝色的面也随即确定。因此，这种情形有两种涂法。（2）红色的两面相邻，不妨设后面和下面是红色的，则黄色可相对为一种，蓝色可相对也为一种。若黄色的面相邻，可以有左面和上面两面的这一种（图2b），也可以有左面与前面两面的这一种（图2c），这两种是否可以经过翻转而重合呢？不行的。我们可将图2b的红色两面调换位置，使后面成为底面，底面成为后面，则图2b的黄色分别位于前面和右面，和图2c是不一样的，所以它们是两种不同的涂法。综上所述，符合题意的染色法共有6种。[例3]有一个7×7的棋盘，每一个小方格中有一只小甲虫，假定在同一时刻，所有的小甲虫都爬到相邻的格子中（横向或纵向的格，不能斜爬），问此时能否出现空格？思路剖析初看题，似乎无从下手，但是我们可以利用“染色”的手段，使问题得到简化。我们用的手段同前面所讲的奇偶性很类似。解答将7×7棋盘用黑白两种颜色相间染色，如图3所法，此时，共有黑格25个，白格24个。因此，当每个小格中的甲虫同时爬向邻格时，即黑格中的甲虫爬到白格中，白格中的甲虫爬到黑格中，由于黑格比白格多一格，则原来白格中的甲虫爬到黑格后必定至少有一个黑格是空的。所以此时肯定会出现空格。[例4]对世界上任何六个人来说，其中至少有三个人，他们要么互相认识，要么互相都不认识，请说明其中的理由。思路剖析将这个问题换一种叙述方式：在纸上画出六个点，表示六个人，如果两个人互相认识，就在代表这两个人的两点间连一条红色直线；如果两个人互相认识，就在代表两个人的两点间连一条蓝色直线。这样，六个点中的任意两点之间总能连一条直线，要么红线要么蓝线。因此问题就转化为，以A、B、C、D、E、F这六个顶点中，必然存在一个三角形，它的三条边颜色是一样的。解答在六点中任取其中一点A，如图4所示，它与其他五点有五条连线，每一条连线要么红要么蓝，而根据抽屉原理，其中至少有三条线颜色相同，不妨设AC、AD和AE是在条蓝色的连线。而CD、CE和DE三条连线中，只要有一点蓝色的，就会有一个三边都是蓝色的三角形出现。这说明有三个人互相都不认识。而如果CD、CE和DE三条连线均不是蓝色的，那么三角形CDE三边颜色都是红色，这说明有三个人互相都认识。[例5]如图5所示，将圆分成4个互不相同的扇形，每个扇形用红、黄、蓝三种颜色中一种颜色染色，要求相邻扇形所染的颜色不同，请问共有多少种染色方法？思路剖析我们将四个扇形分别用表示。在一般情形下，有三种染法，有两种，有两种，而要根据和的颜色是否相同来确定。解答当染红色时，列表如下。从表中可以看出：当染红色时，共有6种染法。同理，当染黄色时，也都有6种染法。所以，符合题意的染色法有6×3=18（种）。[例6]现有1，1，2，2，3，3，…，10，10共20个数。请问能否将这些数排成一行并且满足：两个1之间有一个数，两个2之间有两个数，两个3之间有三个数，…，两个10之间有十个数？试证明你的结论。思路剖析对本题，解题的思路比较多，我们采用“染色”法来解答，应用奇偶性来找出矛盾。解答将这20个数所应占有20上位置进行黑白相间染色。如图6所示，白色位置和黑色位置各占10个。根据题意，两个奇数之间要有奇数个数，两个偶数之间要有偶数个数，则两个奇数所占的位置应该是颜色相同的两个位置，而每个偶数要占5个黑色位置和5个白色位置。剩下的10个奇数，要么占10个黑色位置，要么占10个白色位置。于是如果满足题设的要求，则需要15个白色位置和5个黑色位置或者需要5个白色位置和15个黑色位置，这与黑白位置各占10个相矛盾。所以没有满足题设的排法。[例7]用125块体积相等的黑白两种正方体，黑白相间的拼成一个大正方体（如图7所示），那么露在表面上的黑色正方体的个数是多少？思路剖析对此类问题，一般是分类来逐步求出每一部分的个数，或者利用容斥原理来解题：即由每个面的黑格数乘以6再减去多算的几个黑方块。解答☆解法一：八个顶点共有1×8=8（个）黑方块；十二条棱中间共有1×10=12（个）黑方块；六个面中间共有5×6=30（个）黑方块。所以，露在表面上的黑色正方体的个数是8+12+30=50（个）。☆解法二：如果一个黑格子是一个黑正方体，则有13×6=78（个），但八个顶点的八个黑正方体被计算了三遍，十二条棱中间的十二个黑正方体被计算了两遍。所以露在表面上的黑色正方体的个数有78-8×2-12=78-16-12=50（个）。[例8]圆周上有10个点，将圆周分成10段互不包含的弧圈，现将其中6个点染成黑色，余下4个点染成白色。如果规定：两端都是黑色点的弧段标上数字2，两端都是白色点的弧段标上数字0，两端颜色不同的弧段标上数字1，把所有这些数字加起来的总和是多少？思路剖析首先随意染一两种形式，可以算出，这些数加起来的和是12，也就是谘，和与染色方式无关。我们可以先考虑六个黑点是连在一起的，先移动一个黑点，若移动后6个黑点仍相邻，则其和不变；若移动后这个黑点落在一个白点和另外三个白点之间，则少了1个2，少了1个0，多了两个1，总和不变。继续移动黑点，若落在两个白点之间，如上所述，其和不变；若落在一黑一白之间，则2、0、1的个数均不变，从而其和亦不变。解答☆解法一：6个黑白点，4个白点的任意染色，总有2个黑色相邻，现将其余的黑点移动到这两个黑点之间。（1）若黑点的两边都是白点时，移动后减少2个1，增加了1个0，1个2，其和不变。（2）若黑点的两边都是黑点时，移动后加数完全相同，其和不变。（3）若黑点的两边恰是一黑一白时，移动后加数完全相同，其和不变。移动至6个黑点相邻、4个白点相邻时，其和为12，由移动中其和始终不变可知，一开始时各数字的和也是12。☆解法二：记黑点为数字1，白点为数字0，则黑黑弧上数字2转化为端点上两数字之和，同样黑白弧，白白弧也是一样的。这就把弧上数字之和转化为各点数字之和。由于每一点都是左右两段弧的端点，因而弧上数字和为点上数字和的两倍。即所有这些数字加起来的总和是N=2×（1+1+1+1+1+1+0+0+0+0）=12。☆解法三：设黑黑弧有a条，白白弧有b条，则黑白弧有（10-a-b）条。弧上各数字之和为N=2a+(10-a-b)=10+a-b。可见，关键是求a-b。为此，我们在黑黑弧之间插入一个白点，共插入a个白点；在白白弧之间插入一个黑点，共插入b个黑点。这时，整个圆周黑白相间，黑点数6+b等于自然数4+a，有6+b=4+a，即a-b=6-4=2，从而N=10+（a-b）=12。即所有这些数字加起来的总和是12。点津“染色”问题涉及的领域比较广，这要求我们要灵活地应用各种不同方法来解题。比如：例1涉及排列组合；例2涉及分类和组合；例3涉及及奇偶性；例4涉及抽屉原理；例5涉及排列组合和分类的的原理；例6涉及奇偶性；例7涉及组合容斥原理；例8则要求一些知识的整体灵活应用。因此要求对前面的知识有深刻的了解。发散思维训练1．如图9所示，A、B、C、D、E、F六个部分分别代表六个国家，那么至少要用______种颜色进行涂色，才能使相邻的国家所涂的颜色不同。2．线段AB内有3个点，若以这5个点为端点线段中点都染上红色，则线段AB上至少有______个红点。3．给图10的6个点染色，使相邻的点不同色，最少需要______种颜色。4．如图11所示，一个长方形分成6个不同的三角形，绿色三角形面积占长方形面积的15%，黄色三角形面积是21平方厘米。那么，长方形的面积是______平方厘米。5．如图12所示，现有一个6×6的方格棋盘中，将部分1×1小方格染红。如果随意划掉4行4列，都要使得剩下的小方格中一定有一个是红色，那么至少要涂______个小方格。6．甲、乙两人对一根300厘米的木棍染色，首先甲从要棍的一上端点开始染黑3厘米，再间隔7厘米不染黑，如此交接下去。然后乙从另一端点开始留出5厘米不染黑，接着染5厘米，交替下去做到底。最后木棍上染黑部分总长有______厘米。7．如图12所示为某展览馆的36个展室，每两个相邻的展室之间有门相通。请问能否从入口进去，不重复地参观完全部展室后，从出口出来？8．把14个（1×1×2）立方厘米的小长方体摆成如图13所示的样子，然后把露出表面的都涂上颜色，则被染上颜色的面积是多少？参考答案发散思维训练1．解：首先在相邻区域最多的A国涂上第1种颜色；再与A国相邻的B、C、D、E、F中找出相邻区域最多的C国涂上2种颜色；然后在F国涂第3种颜色；由于B国与A、C、F均有公共边，所以在B国涂第4种颜色；由D国与B国无公共边，所以D国涂第4种颜色；E国与C国无公共边涂第2种颜色。因此，至少要用4种颜色进行涂色。注意：上述涂法并不是惟一的。2．解：如答图1所示，要使红点个数最少，点A、C、D、E、B应该均匀分布。设AC、CD、DE、EB的中点依次为都染了红色。这样AD的中点为C，AE的中点为，AB的中点为D，CE的中点为D，CB的中点为，DB的中点为E。所以点C、D、E都染红色。故线段AB上最少有7个红点。3．解：先考虑相邻的点最多的D、E、F，这三点相邻，必须用3种不同的颜色，然后由A、D不相邻，B、F不相邻，C、E不相邻，所以A和D、B和F、C和E可以用一种颜色来染，这样最少要用3种颜色来染。4．解：仔细观察，红色的两个三角形的面积和应该是整个长方形面积的一半。所以黄色三角形的面积占长方形面积的（50%-15%）=35%，又由于黄色三角形的面积的21平方厘米，所以长方形的面积是。5．解：如果随意划去的4行4列恰都是红色小方格，再加上剩下的一个小方格，至少要有4×4+1=17（个）小方格要涂红。6．解：可以看出，每隔10厘米染黑的部分重复出现，并且甲所染的部分被乙所染的部分覆盖了，所以最后木棍上染黑部分总长为。7．解：不能。用黑白颜色把36个展览室相间地染色，则黑白色展室各有18个，并且入口和出口的展室颜色