小学奥数染色与操作问题教师版

实际操作与策略问题这类题目能够很好的提高学生思考问题的能力，激发学生探索数学规律的兴趣，并通过寻找最佳策略过程，培养学生的创造性思维能力，这也是各类考试命题者青睐的这类题目的原因。

模块一、探索与操作【例 1】 将1—13这13个自然数分别写在13张卡片上，再将这13张卡片按一定的顺序从左至右排好．然后进行如下操作：将从左数第一张和第二张依次放到最后，将第三张取出而这张卡片上的数是1；再将下面的两张依次放到最后并取出下一张，取出的卡片上面的数是2；继续将下面的两张依次放到最后并取出下一张，取出的卡片上面的数是3……如此进行下去，直到取出最后一张是13为止．则13张卡片最初从左到右的顺序为 ．【考点】游戏与策略 【难度】3星 【题型】填空【解析】 这13张卡片依次是原来的第3，第6，第9，第12，第2，第7，第11，第4，第10，第5，第1，第8，第13张，所以原来的顺序为11，5，1，8，10，2，6，12，3，9，7，4，13【答案】11，5，1，8，10，2，6，12，3，9，7，4，13【巩固】 在纸上写着一列自然数1，2，…，98，99．一次操作是指将这列数中最前面的三个数划去，然后把这三个数的和写在数列的最后面．例如第一次操作后得到4，5，…，98，99，6；而第二次操作后得到7，8，…，98，99，6，15．这样不断进行下去，最后将只剩下一个数，则最后剩下的数是 ．【考点】游戏与策略 【难度】3星 【题型】填空【解析】 第一轮：分33次划1～9，后面写上6，15，24，…，294共33个数．第二轮：分11次划去这33例题精讲知识框架游戏与策略个数，后面写上45，126，207，…，855，共11个数．之后的操作一次减少2个数，故还需操作5次．设这11个数为：1a ，2a ，…，11a ．则接下去的数是：123()a a a ++，456()a a a ++，789()a a a ++，1011123()a a a a a ++++，4567891011123()a a a a a a a a a a a ++++++++++．因此最后一数为：1231112994950a a a a ++++=+++=．【答案】4950。

第十三讲：构造与论证教学目标1.掌握最佳安排和选择方案的组合问题.2.利用基本染色去解决相关图论问题．知识点拨各种探讨给定要求能否实现，在论证中，有时需进行分类讨论，有时则要着眼于极端情形，或从整体把握．设计最佳安排和选择方案的组合问题，这里的最佳通常指某个量达到最大或最小．解题时，既要构造出取得最值的具体实例，又要对此方案的最优性进行论证．论证中的常用手段包括抽屉原则、整除性分析和不等式估计．组合证明题，在论证中，有时需进行分类讨论，有时则需要着眼于极端情况，或从整体把握。

若干点及连接它们的一些线段组成图，与此相关的题目称为图论问题。

若干点及连接它们的一些线段组成图，与此相关的题目称为图论问题，这里宜从特殊的点或线着手进行分析．各种以染色为内容，或通过染色求解的组合问题，基本的染色方式有相间染色与条形染色．例题精讲模块一最佳安排和选择方案【例 1】一个盒子里有400枚棋子，其中黑色和白色的棋子各200枚．下面我们对这些棋子做如下操作：每次拿出2枚棋子，如果颜色相同，就补1枚黑色棋子回去；如果颜色不同，就补1枚白色的棋子回去．这样的操作，实际上就是每次都少了1枚棋子，那么，经过399次操作后，最后剩下的棋子是颜色(填“黑”或者“白”)．【解析】在每一次操作中，若拿出的两枚棋子同色，则补黑子1枚，所以拿出的白子可能为0枚或2枚；若拿出的两枚棋子异色，则补白子1枚，“两枚棋子异色”说明其中一黑一白，那么此时拿出的白子数为0枚．可见每次操作中拿出的白子都是偶数枚，而由于起初白子有200枚，是偶数枚，所以每次操作后剩下的白子都是偶数枚，因此最后1枚不可能是白子，只能是黑子．【例 2】5卷本百科全书按从第1卷到第5卷的递增序号排列，今要将它们变为反序排列，即从第5卷到第1卷．如果每次只能调换相邻的两卷，那么最少要调换多少次?【解析】因为必须是调换相邻的两卷，将第5卷调至原来第1卷的位置最少需4次，得到的顺序为51234；现在将第4卷调至此时第l卷的位置最少需3次，得到的顺序为54123；现在将第3卷调至此时第l卷的位置最少需2次，得到的顺序为54312；最后将第l卷和第2卷对调即可．所以，共需调换4+3+2+1=10次．【例 3】有3堆小石子，每次允许进行如下操作：从每堆中取走同样数目的小石子，或是将其中的某一石子数是偶数的堆中的一半石子移入另外的一堆．开始时，第一堆有1989块石子，第二堆有989块石子，第三堆有89块石子．问能否做到：、(1)某2堆石子全部取光? (2)3堆中的所有石子都被取走?【解析】(1)可以，如(1989，989，89) →(1900，900，0)→(950，900，950)→(50，0，50)→(25，25，50)→(O，0，25)．(2)因为操作就两种，每堆取走同样数目的小石子，将有偶数堆石子堆中一半移至另一堆，所以每次操作石子总数要么减少3的倍数，要么不变．现在共有1989+989+89=3067，不是3的倍数，所以不能将3堆中所有石子都取走．【例 4】n支足球队进行比赛，比赛采用单循环制，即每对均与其他各队比赛一场.现规定胜一场得2分，平一场得1分，负一场得0分.如果每一队至少胜一场，并且所有各队的积分都不相同，问：（1）n=4是否可能？（2）n=5是否可能？C场比赛，而每场比赛有2【解析】（1）我们知道4个队共进行了24C×2=12.因为每一队至少分产生，所以4个队的得分总和为24胜一场，所以得分最低的队至少得2分，又要求每个队的得分都不相同，所以4个队得分最少2+3+4+5=14＞12，不满足.即n=4不可能。

第14讲染色问题本节主要讲述用染色的方法解有关的竞赛题．染色，是一种辅助解题的手段，通过染色，把研究对象分类标记，以便直观形象地解决问题，因此染色就是分类的思想的具体化，例如染成两种颜色，就可以看成是奇偶分析的一种表现形式．染色，也是构造抽屉的一个重要方法，利用染色分类，从而构造出抽屉，用抽屉原理来解题．A类例题例1⑴有一个6×6的棋盘，剪去其左上角和右下角各一个小格(边长为1)后，剩下的图形能不能剪成17个1×2的小矩形？⑵剪去国际象棋棋盘左上角2×2的正方形后，能不能用15个由四个格子组成的L形完全覆盖？分析把棋盘的格子用染色分成两类，由此说明留下的图形不能满足题目的要求．证明⑴如图，把6×6棋盘相间染成黑、白二色，使相邻两格染色不同．则剪去的两格同色．但每个1×2小矩形都由一个白格一个黑格组成，故不可能把剩下的图形剪成17个1×2矩形．⑵如图，把8×8方格按列染色，第1，3，5，7列染黑，第2、4、6、8列染白．这样染色，其中黑格有偶数个．由于每个L形盖住三黑一白或三白一黑，故15个L形一定盖住奇数个黑格，故不可能．说明用不同的染色方法解决不同的问题．例2 用若干个由四个单位正方形组成的“L”形纸片无重叠地拼成一个m n的矩形，则mn必是8的倍数．分析易证mn是4的倍数，再用染色法证mn是8的倍数．证明：每个L形有4个方格，故4|mn．于是m、n中至少有一个为偶数．设列数n为偶数，则按奇数列染红，偶数列染蓝．于是红格与蓝格各有12mn个，而12mn是偶数．每个L形或盖住3红1蓝，或盖住1红3蓝，设前者有p个，后者有q个．于是红格共盖住3p+q个即p+q为偶数，即有偶数个L形．设有2k个L形．于是mn=2k×4=8k．故证．说明奇偶分析与染色联合运用解决本题．情景再现1．下面是俄罗斯方块的七个图形：请你用它们拼出(A)图，再用它们拼出(B)图(每块只能用一次，并且不准翻过来用)．如果能拼出来，就在图形上画出拼法，并写明七个图形的编号；如果不能拼出来，就说明理由．2．能否用图中各种形状的纸片（不能剪开）拼成一个边长为75的正方形？（图中每个小方格的边长都为1）请说明理由．B类例题例3 ⑴以任意方式对平面上的每一点染上红色或者蓝色．证明：一定存在无穷条长为1的线段，这些线段的端点为同一颜色．⑵以任意方式对平面上的每一点染上红色或者蓝色．证明：存在同色的三点，且其中一点为另两点中点．分析任意染色而又要求出现具有某种性质的图形，这是染色问题常见的题型，常用抽屉原理或设置两难命题的方法解．证明⑴取边长为1的等边三角形，其三个顶点中必有两个顶点同色．同色两顶点连成线段即为一条满足要求的线段，由于边长为1的等边三角形有无数个，故满足要求的线段有无数条．⑵取同色两点A、B，延长AB到点C，使BC=AB，再延长BA 到点D，使AD=AB，若C、D中有一点为红色，例如点C为红色，则点B为AC中点．则命题成立．否则，C、D全蓝，考虑AB中点M，它也是CD中点．故无论M染红还是蓝，均得证．说明⑴中，两种颜色就是两个“抽屉”，三个点就是三个“苹果”，于是根据抽屉原理，必有两个点落入同一抽屉．⑵中，这里实际上构造了一个两难命题：非此即彼，二者必居其一．让同一点既是某两个红点的中点，又是两个蓝点的中点，从而陷入两难选择的境地，于是满足条件的图形必然存在．达到证明的目的．例4 ⑴以任意方式对平面上的每一点染上红色或者蓝色．证明：一定可以找到无穷多个顶点为为同一种颜色的等腰三角形．⑵以任意方式对平面上的每一点染上红色或者蓝色．证明：一定可以找到无穷多个顶点为为同一种颜色的等腰直角三角形．分析⑴同样可以设置两难命题：由于等腰三角形的顶点在底边的垂直平分线上，故先选两个同色点连成底边，再在连线的垂直平分线上找同色的点，这是解法1的思路．利用圆的半径相等来构造等腰三角形的两腰，这是解法2的思路．利用抽屉原理，任5个点中必有三点同色，只要这5点中任三点都是一个等腰三角形的顶点即可，而正五边形的五个顶点中任三个都是等腰三角形的顶点，这是解法3的思路．⑵连正方形的对角线即得到两个等腰直角三角形，所以从正方形入手解决相题第2问．⑴证明1任取两个同色点A、B(设同红)，作AB的垂直平分线MN，若MN上(除与AB交点外)有红色点，则有红色三角形，若无红色点，则MN上至多一个红点其余均蓝，取关于AB对称的两点C、D，均蓝．则若AB上有(除交点外)蓝点，则有蓝色三角形，若无蓝点，则在矩形EFGH内任取一点K(不在边上)若K为蓝，则可在CD上取两点与之构成蓝色三角形，若K为红，则可在AB上找到两点与之构成红色三角形．证明2任取一红点O，以O为圆心任作一圆，若此圆上有不是同一直径端点的两个红点A、B，则出现红色顶点等腰三角形OAB，若圆上只有一个红点或只有同一直径的两个端点是红点，则圆上有无数蓝点，取两个蓝点(不关于红点为端点的直径对称)C、D，于是CD的垂直平分线与圆的两个交点E、F为蓝点，于是存在蓝色顶点的等腰三角形CDE．证明3取一个正五边形ABCDE，根据抽屉原理，它的5个顶点中，必有三个顶点(例如A、B、C)同色，则△ABC即为等腰三角形．⑵证明任取两个蓝点A、B，以AB为一边作正方形ABCD，若C、D有一为蓝色，则出现蓝色三角形．若C、D均红，则对角线交点E或红或蓝，出现红色或蓝色等腰直角三角形．显然按此作法可以得到无数个等腰直角三角形．(由本题也可以证明上一题．)例5 设平面上给出了有限个点(不少于五点)的集合S，其中若干个点被染成红色，其余点被染成蓝色，且任意三个同色点不共线．求证：存在一个三角形，具有下述性质：⑴以S中的三个同色点为顶点；⑵此三角形至少有一条边上不含另一种颜色的点．分析要证明存在同色三角形不难，而要满足第⑵个条件，可以用最小数原理．证明由于S中至少有五点，这些点染成两种颜色，故必存在三点同色．且据已知，此三点不共线，故可连成三角形．取所有同色三角形，由于S只有有限个点，从而能连出的同色三角形只有有限个，故其中必有面积最小的．其中面积最小的三角形即为所求．首先，这个三角形满足条件⑴，其次，若其三边上均有另一种颜色的点，则此三点必可连出三角形，此连出三角形面积更小，矛盾．说明最小数原理，即极端原理．见第十二讲．例6 将平面上的每个点都染上红、蓝二色之一，证明：存在两个相似的三角形，其相似比为1995，且每一个三角形的三个顶点同色．(1995年全国联赛加试题)分析把相似三角形特殊化，变成证明相似的直角三角形，在矩形的网格中去找相似的直角三角形，这是证法1的思路．证法2则是研究形状更特殊的直角三角形：含一个角为30˚的直角三角形．证明可以找到任意边长的这样的三角形，于是对任意的相似比，本题均可证．证法3则是考虑两个同心圆上三条半径交圆得的三组对应点连出的两个三角形一定相似，于是只要考虑找同心圆上的同色点，而要得到3个同色点，只要任取5个只染了两种颜色的点就行；而要得到5个同色点，则只要取9个只染了两种颜色的点即行．证明1 首先证明平面上一定存在三个顶点同色的直角三角形．任取平面上的一条直线l，则直线l上必有两点同色．设此两点为P、Q，不妨设P、Q同着红色．过P、Q作直线l的垂线l1、l2，若l1或l2上有异于P、Q的点着红色，则存在红色直角三角形．若l1、l2上除P、Q外均无红色点，则在l1上任取异于P的两点R、S，则R、S必着蓝色，过R作l1的垂线交l2于T，则T必着蓝色．△RST即为三顶点同色的直角三角形．下面再证明存在两个相似比为1995的相似的直角三角形．设直角三角形ABC三顶点同色(∠B为直角)．把△ABC补成矩形ABCD(如图)．把矩形的每边都分成n等分(n为正奇数，n>1，本题中取n=1995)．连结对边相应分点，把矩形ABCD分成n2个小矩形．AB边上的分点共有n+1个，由于n为奇数，故必存在其中两个相邻的分点同色，(否则任两个相邻分点异色，则可得A、B异色)，不妨设相邻分点E、F同色．考察E、F所在的小矩形的另两个顶点E'、F'，若E'、F'异色，则△EFE'或△DFF'为三个顶点同色的小直角三角形．若E'、F'同色，再考察以此二点为顶点而在其左边的小矩形，…．这样依次考察过去，不妨设这一行小矩形的每条竖边的两个顶点都同色．同样，BC边上也存在两个相邻的顶点同色，设为P、Q，则考察PQ所在的小矩形，同理，若P、Q所在小矩形的另一横边两个顶点异色，则存在三顶点同色的小直角三角形．否则，PQ所在列的小矩形的每条横边两个顶点都同色．现考察EF所在行与PQ所在列相交的矩形GHNM，如上述，M、H都与N同色，△MNH为顶点同色的直角三角形．由n=1995，故△MNH∽△ABC，且相似比为1995，且这两个直角三角形的顶点分别同色．证明2 首先证明：设a为任意正实数，存在距离为2a的同色两点．任取一点O(设为红色点)，以O为圆心，2a为半径作圆，若圆上有一个红点，则存在距离为2a的两个红点，若圆上没有红点，则任一圆内接六边形ABCDEF的六个顶点均为蓝色，但此六边形边长为2a．故存在距离为2a的两个蓝色点．下面证明：存在边长为a，3a，2a的直角三角形，其三个顶点同色．如上证，存在距离为2a的同色两点A、B(设为红点)，以AB为直径作圆，并取圆内接六边形ACDBEF，若C、D、E、F中有任一点为红色，则存在满足要求的红色三角形．若C、D、E、F为蓝色，则存在满足要求的蓝色三角形．下面再证明本题：由上证知，存在边长为a，3a，2a及1995a，19953a，1995⨯2a的两个同色三角形，满足要求．证明3 以任一点O为圆心，a及1995a为半径作两个同心圆，在小圆上任取9点，其中必有5点同色，设为A、B、C、D、E，作射线OA、OB、OC、OD、OE，交大圆于A'，B'，C'，D'，E'，则此五点中必存在三点同色，设为A'、B'、C'．则∆ABC与∆A'B'C'为满足要求的三角形．情景再现3．以任意方式对平面上的每一点染上红色或者蓝色．证明：一定存在一个矩形，它的四个顶点同色．4．以任意方式对平面上的每一点染上红色或者蓝色．证明：一定可以找到无穷多个顶点全为同一种颜色的全等三角形．5．图中是一个6×6的方格棋盘，现将部分1×1小方格涂成红色。

专题14 染色问题1.下图是一套房子的平面图,图中的方格代表房间,每个房间都有通向任何一个邻室的门.有人想从某个房间开始,依次不重复地走遍每一个房间,他的想法能实现吗?2.展览会有36个展室(如图),每两相邻展室之间均有门相通.能不能从入口进去,不重复地参观完全部展室后,从出口出来呢?3.图中的16个点表示16个城市,两个点之间的连线表示这两个城市有公路相通.问能否找到一条不重复地走遍这16座城市的路线?4.下图是由4个小方格组成的“L ”形硬纸片,用若干个这种纸片无重叠地拼成一个4 n 的长方形,试证明:n 一定是偶数.5.中国象棋盘上最多能放几只马互不相“吃”(“马”走“日”字,另不考虑“别马腿”的情况).6.能否用一个田字和15个4⨯1矩形覆盖8⨯8棋盘?7.能否用1个田字和15个T 字纸片,拼成一个8⨯8的正方形棋盘?8.在8⨯8棋盘上,马能否从左下角的方格出发,不重地走遍棋盘,最后回到起点?若能请找出一条路,若不能,请说明理由.9.下面三个图形都是从4⨯4的正方形分别剪去两个1⨯1的小方格得到的,问可否把它们分别剪成1⨯2的七个小矩形?(1)(2) (3)10.把三行七列的21个小格组成的矩形染色,每个小格染上红、蓝两种色中的一种.求证:总可以找到4个同色小方格,处于某个矩形的4个角上(如图)红红红红11.17个科学家互相通信,在他们的通信中共讨论3个问题,而任意两个科学家之间仅讨论1个问题.证明:至少有3个科学家,他们彼此通信讨论的是同一个问题.12.用一批1⨯2⨯4的长方体木块,能不能把一个容积为6⨯6⨯6的正方体木箱充塞填满?说明理由.13.在平面上有一个27⨯27的方格棋盘,在棋盘的正中间摆好81枚棋子,它们被罢成一个9⨯9的正方形.按下面的规则进行游戏:每一枚棋子都可沿水平方向或竖直方向越过相邻的棋子,放进紧挨着这枚棋子的空格中,并把越过的这格棋子取出来.问:是否存在一种走法,使棋盘上最后恰好剩下一枚棋子?14.12⨯12的超极棋盘上,一匹超级马每步跳至3⨯4矩形的另一角(如图).问能否从任一点出发遍历每一格恰一次,再回到出发点(这种情况又称马有“回路”)?123———————————————答 案—————————————————————— 1. 不能.对房间染色,使最下面的两个房间染成黑色,与黑色相邻的房染成白色,则图中有7个黑色房间和5个白色房间.如果要想不重复地走过每一个房间,黑色与白色房间数应该相等.故题中的想法是不能实现的. 2. 不能.对展室进行染色,使相邻两房间分别是黑色和白色的.此时入口处展室的颜色与出口处展室的颜色是相同的,而不重复参观完36个展室,入口与出口展室的颜色应该不相同. 3. 不能.对这16个城市进行黑白相间的染色,一种颜色有9个,另一种颜色有7个.而要不重复地走遍这16个城市,黑色与白色的个数应该相等. 4. 如图,对4⨯n 长方形的各列分别染上黑色和白色.任一L 形纸片所占的3黑1白,第二类占3白1黑.设第一类有a 个,第二类有b 个,因为涂有两种颜色的方格数相等,故有3b +a =3a +b ,即a =b ,也就是说第一类与第二类相等,因此各种颜色的方格数都是4的倍数,总数是8的倍数,从而n 是偶然.5. 将棋盘黑白相间染色,由“马”的走法可知,放在黑点上的“马”,只能吃放在某些白点上的马.整个棋盘上黑、白点的个数均为45,故可在45个黑点放上马,它们是不能互吃的.6. 如图的方式对棋盘染色.那么一个田字形盖住1个或3个白格,而一个4⨯1的矩形盖住2个白格.这样一来一个田字和15个4⨯1的矩形能盖住的白格数是一个奇数,但上图中的白格数是一个偶数,因此一个田字形和15个4⨯1的矩n 个7. 将棋盘里黑白相间涂色.一个田字形盖住2个白格,一个T字形盖住3个或1个白格.故1个田字和15个T字盖住的白格数是一个奇数,但棋盘上的白格数是一个偶数.因此一个田字形和15个T字形不能盖住8⨯8的棋盘.8. 将棋盘黑白相间地染色后,马的走法是从一种颜色的格子跳到另一种颜色.棋盘上有32个白格与32个黑格,故马可能跳遍整个棋盘.图中给出了一种走法.564158355039603347445540593451384257464936533261454843543162375220530632211161329642141714251061922782312151287183269249. 先对4⨯4的棋盘黑白相间的涂色(如图),这道题的实际问题是问7个1⨯2矩形能否分别复盖剪去A、B；剪去A、C；剪去A、D的三个棋盘.若7个1⨯2矩形可以复盖剪残的棋盘,因为每个1⨯2矩形均可盖住一个白格和一个黑格,所以棋盘的白格与黑格数目应该相等.都是7个.而剪去A格和C格的棋盘(2)有5个白格8个黑格,剪去A、D的棋盘(3)有5个白格8个黑格,因此这两个剪损的棋盘均不能被7,也就不能剪成7个1⨯2的矩形.棋盘(1)可以被7个1⨯2的矩形所复盖.下面给出一种剪法:A11277B26543654310. 在第一行的7格中必有4格同色,不妨设这4格位于前4个位置,且均为红色.然后考虑前4列构成的3⨯4矩形.若第二行和第3行中出现2个或2个以上的红色格子.则该行的两个红色格子与第一行的红色格子就组成一个4角同为红色格子的矩形.若不然,则第2、3行中都至少有3个蓝格在前4列中,不妨设第2行前3格为蓝色,显然第三行中的前3格中至少有2个蓝格，故在二、三行的前4列中必存在四角都是蓝色的矩形.11. 将17个科学家用17个点代表,两点之间连结的线段表示两个科学家之间讨论的问题.用三种颜色给这些线段染色,表示三个问题,于是问题就变成:给17个点之间的所有连结线段用三种颜色染色,必有同色三角形.从任意一点,不妨设从A 向其他16点A 1,A 2,…A 16共可连成16条线段,用三种颜色染色,由抽屉原则可知,必有6条线段同色.设这6条线段为AA 1,AA 2,…AA 6且同为红色.考虑A 1,A 2,A 3,A 4,A 5,A 6这六点之间的连线,若有一条为红色,(如A 1A 2为红色) ,则三角形AA 1A 2为红色的同色三角形.若这六点之间的连线中,没有一条是红色的,则它们之间只能涂两种颜色.考虑从A 1引出的五条线段A 1A 2 A 1A 3 A 1A 4 A 1A 5 A 1A 6,由抽屉原理知,其中必有三条是同色的.不妨设这三条为A 1A 2 A 1A 3 A 1A 4,且同为蓝色.若三角形A 2A 3A 4的三边中有一条为蓝色的,则有一个蓝色的三角形存在;若三角形A 2A 3A 4三边都不是蓝色的,则它的三边是同为第三色的同色三角形.12. 把正方体木箱分成27个小正方体,每个小正方体的体积为2⨯2⨯2=8.将这些正方体如右图黑白相间染上色.显然黑色2⨯2⨯2的正方体有14个,白色2⨯2⨯2小正方体有13个.每一个这样的正方体相当于8个1⨯1⨯1的小正方体.将1⨯2⨯4的长方体放入木箱,无论怎么放,每个长方体木块盖住8个边长为1的单位正方体,其中有4个黑色的,4个白色的.木箱共含6⨯6⨯6=216个单位正方体,26个长方体木块共盖住8⨯26=208个单位正方体,其中黑白各占104个,余下216-208=8个单位正方体是黑色的.但是第27个1⨯2⨯4长方体木块不管怎样A A 1A 2A 3A 4A 5A 6A 1A 2A 3A4放,也无法盖住这8个黑色单位正方体.13. 如图,将整个棋盘的每一格都分别染上红、白、黑三种颜色,这种染色方式将棋盘分成了三个部分.按照游戏规则,每走一步,有两种颜色方格中的棋子数分别减少了1个,而第三种颜色的棋子数增加了一个.这表明每走一步,每个部.因为一开始时,81枚棋子摆成一个9 9的正方形,显然三个部分的棋子数是相同的,从而每走一步,三部分中的棋子数的奇偶性是相同的.如果走了若干步以后,棋盘上恰好剩下一枚棋子,则两部分上的棋子数为偶数,而另一部分上的棋子数为奇数.这种结果是不可能出现的.14. 用两种方法对超级棋盘染色.首先,将棋盘黑白相间染色,则马每跳一步,它所在的方格就要改变一次颜色.不妨设第奇数步跳入白格.其次,将棋盘的第3,4,5及8,9,10这六行染成黑色,其余六行染成白色.在此种染色方式下,马从白格一定跳入黑格.又因黑白格总数相同,马要遍历每一格恰一次又回到出发点,因此,马从黑格只能跳入白格而不能跳入黑格.不妨设马第奇数步跳入白格.但是对于一种满足要求跳法,在两种染色方式下第奇数步跳入的格子的全体是不同的,这显然是不可能的,故题目要求的跳法是不存在的.。

小学奥数杂题染色问题【三篇】
导读：本文小学奥数杂题染色问题【三篇】，仅供参考，如果觉得很不错，欢迎点评和分享。

【第一篇】 1.如图是一套房子的平面图，图中的方格代表房间，每个房间都有通向任何一个邻室的门．有人想从某个房间开始，依次不重复地走遍每一个房间，他的想法能实现吗？
解析：对房间染色，使最下面的两个房间染成黑色，与黑色相邻的房染成白色，
则图中有7个黑色房间和5个白色房间．
如果要想不重复地走过每一个房间，黑色与白色房间数应该相等．故题中的想法是不能实现的．
点评：完成本题也可根据要求据图中的房间实际找下路线，看是否能够找到．【第二篇】展览会有36个展室(如图),每两相邻展室之间均有门相通.能不能从入口进去,不重复地参观完全部展室后,从出口出来呢? 答案：不能.对展室进行染色,使相邻两房间分别是黑色和白色的.此时入口处展室的颜色与出口处展室的颜色是相同的,而不重复参观完36个展室,入口与出口展室的颜色应该不相同. 【第三篇】染色问题基本解法：三面涂色和顶点有关8个顶点。

两面染色和棱长有关。

即新棱长（棱长-2）×12一面染色和表面积有关。

同样用新棱长计算表面积公式（棱长-2）×（棱长-2）*6 0面染色和体积有关。

用新棱长计算体积公式（棱
长-2）×（棱长-2）×（棱长-2）长方体的解法和立方体同理，即计算各种公式前长、宽、高都要先减2再利用公式计算。

1.使学生掌握乘法原理主要内容，掌握乘法原理运用的方法；2.使学生分清楚什么时候用乘法原理，分清有几个必要的步骤，以及各步之间的关系．3.培养学生准确分解步骤的解题能力；乘法原理的数学思想主旨在于分步考虑问题，本讲的目的也是为了培养学生分步考虑问题的习惯．一、乘法原理概念引入老师周六要去给同学们上课，首先得从家出发到长宁上8点的课，然后得赶到黄埔去上下午1点半的课．如果说申老师的家到长宁有5种可选择的交通工具（公交、地铁、出租车、自行车、步行），然后再从长宁到黄埔有2种可选择的交通工具（公交、地铁），同学们，你们说老师从家到黄埔一共有多少条路线？我们看上面这个示意图，老师必须先的到长宁，然后再到黄埔．这几个环节是必不可少的，老师是一定要先到长宁上完课，才能去黄埔的．在没学乘法原理之前，我们可以通过一条一条的数，把线路找出来，显而易见一共是10条路线．但是要是老师从家到长宁有25种可选择的交通工具，并且从长宁到黄埔也有30种可选择的交通工具，那一共有多少条线路呢？这样数，恐怕是要耗费很多的时间了．这个时候我们的乘法原理就派上上用场了．二、乘法原理的定义完成一件事，这个事情可以分成n个必不可少的步骤（比如说老师从家到黄埔，必须要先到长宁，那么一共可以分成两个必不可少的步骤，一是从家到长宁，二是从长宁到黄埔），第1步有A种不同的方法，第二步有B种不同的方法，……，第n步有N种不同的方法．那么完成这件事情一共有A×B×……×N种不同的方法．结合上个例子，老师要完成从家到黄埔的这么一件事，需要2个步骤，第1步是从家到长宁，一共5种选择；第2步从长宁到黄埔，一共2种选择；那么老师从家到黄埔一共有5×2个可选择的路线了，即10条．三、乘法原理解题三部曲1、完成一件事分N个必要步骤；2、每步找种数（每步的情况都不能单独完成该件事）；3、步步相乘四、乘法原理的考题类型教学目标知识要点7-2-3乘法原理之染色问题1、路线种类问题——比如说老师举的这个例子就是个路线种类问题；2、字的染色问题——比如说要3个字，然后有5种颜色可以给每个字然后，问3个字有多少种染色方法；3、地图的染色问题——同学们可以回家看地图，比如中国每个省的染色情况，给你几种颜色，问你一张包括几个部分的地图有几种染色的方法；4、排队问题——比如说6个同学，排成一个队伍，有多少种排法；5、数码问题——就是对一些数字的排列，比如说给你几个数字，然后排个几为数的偶数，有多少种排法．【例 1】 地图上有A ，B ，C ，D 四个国家(如下图)，现有红、黄、蓝三种颜色给地图染色，使相邻国家的颜色不同，但不是每种颜色都必须要用，问有多少种染色方法？DC B A【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】 A 有3种颜色可选；当B ，C 取相同的颜色时，有2种颜色可选，此时D 也有2种颜色可选．根据乘法原理，不同的涂法有32212⨯⨯=种；当B ，C 取不同的颜色时，B 有2种颜色可选，C 仅剩1种颜色可选，此时D 也只有1种颜色可选(与A 相同)．根据乘法原理，不同的涂法有32116⨯⨯⨯=种．综上，根据加法原理，共有12618+=种不同的涂法．【答案】18【巩固】 如果有红、黄、蓝、绿四种颜色给例题中的地图染色，使相邻国家的颜色不同，但不是每种颜色都必须要用，问有多少种染色方法？【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】 第一步，首先对A 进行染色一共有4种方法，然后对B 、C 进行染色，如果B 、C 取相同的颜色，有三种方式，D 剩下3种方式，如果B 、C 取不同颜色，有326⨯=种方法，D 剩下2种方法，对该图的染色方法一共有43332284⨯⨯+⨯⨯=（）种方法． 【注意】给地图染色问题中有的可以直接用乘法原理解决，有的需要分类解决，前者分类做也可以解决问题．【答案】84【例 2】 在右图的每个区域内涂上A 、B 、C 、D 四种颜色之一，使得每个圆里面恰有四种颜色，则一共有__________种不同的染色方法．7654321【考点】乘法原理之染色问题 【难度】4星 【题型】解答【解析】 因为每个圆内4个区域上染的颜色都不相同，所以一个圆内的4个区域一共有43224⨯⨯=种染色方法．如右图所示，当一个圆内的1、2、3、4四个区域的颜色染定后，由于6号区域的颜色不能与2、3、4三个区域的颜色相同，所以只能与1号区域的颜色相同，同理5号区域只能与4号区域的颜色相同，7号区域只能与2号区域的颜色相同，所以当1、2、3、4四个区域的颜色染定后，其他区域的颜色也就相应的只有一种染法，所以一共有24种不同的染法．【答案】24【例 3】 如图，地图上有A ，B ，C ，D 四个国家，现用五种颜色给地图染色，要使相邻国家的颜色不相同，有多少种不同染色方法?例题精讲DCB A【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】 为了按要求给地图上的这四个国家染色，我们可以分四步来完成染色的工作：第一步：给A 染色，有5种颜色可选．第二步：给B 染色，由于B 不能与A 同色，所以B 有4种颜色可选．第三步：给C 染色，由于C 不能与A 、B 同色，所以C 有3种颜色可选．第四步：给D 染色，由于D 不能与B 、C 同色，但可以与A 同色，所以D 有3种颜色可选．根据分步计数的乘法原理，用5种颜色给地图染色共有5433180⨯⨯⨯=种不同的染色方法．【答案】180【巩固】 如图，一张地图上有五个国家A ，B ，C ，D ，E ，现在要求用四种不同的颜色区分不同国家，要求相邻的国家不能使用同一种颜色，不同的国家可以使用同—种颜色，那么这幅地图有多少着色方法？ED C BA【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】 第一步，给A 国上色，可以任选颜色，有四种选择；第二步，给B 国上色，B 国不能使用A 国的颜色，有三种选择；第三步，给C 国上色，C 国与B ，A 两国相邻，所以不能使用A ，B 国的颜色，只有两种选择；第四步，给D 国上色，D 国与B ，C 两国相邻，因此也只有两种选择；第五步，给E 国上色，E 国与C ，D 两国相邻，有两种选择． 共有4322296⨯⨯⨯⨯=种着色方法．【答案】96【例 4】 如图：将一张纸作如下操作，一、用横线将纸划为相等的两块，二、用竖线将下边的区块划为相等的两块，三、用横线将最右下方的区块分为相等的两块，四、用竖线将最右下方的区块划为相等的两块……，如此进行8步操作，问：如果用四种颜色对这一图形进行染色，要求相邻区块颜色不同，应该有多少种不同的染色方法？【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】 对这张纸的操作一共进行了8次，每次操作都增加了一个区块，所以8次操作后一共有9个区块，我们对这张纸，进行染色就需要9个步骤，从最大的区块从大到小开始染色，每个步骤地染色方法有：4、3、2、2、2……，所以一共有：4322222221536⨯⨯⨯⨯⨯⨯⨯⨯=种．【答案】1536【巩固】 用三种颜色去涂如图所示的三块区域，要求相邻的区域涂不同的颜色，那么共有几种不同的涂法？ABC【考点】乘法原理之染色问题【难度】2星【题型】解答【解析】涂三块毫无疑问是分成三步．第一步，涂A部分，那么就有三种颜色的选择；第二步，涂B部分，由于要求相邻的区域涂不同的颜色，A和B相邻，当A确定了一种颜色后，B只有两种颜色可选择了；第三步，涂C部分，C和A、B都相邻，A和B确定了两种不相同的颜色，那么C只有一种颜色可选择了．然后再根据乘法原理．3216⨯⨯=【答案】6【例 5】如图，有一张地图上有五个国家，现在要用四种颜色对这一幅地图进行染色，使相邻的国家所染的颜色不同，不相邻的国家的颜色可以相同．那么一共可以有多少种染色方法？【考点】乘法原理之染色问题【难度】3星【题型】解答【解析】这一道题实际上就是例题，因为两幅图各个字母所代表的国家的相邻国家是相同的，如果将本题中的地图边界进行直角化就会转化为原题，所以对这幅地图染色同样一共有4322296⨯⨯⨯⨯=种方法．【讨论】如果染色步骤为----C A BD E,那么应该该如何解答？答案：也是4322296⨯⨯⨯⨯=种方法．如果染色步骤为----C AD B E那么应该如何解答？答案：染色的前两步一共有4×3种方法，但染第三步时需要分类讨论，如果D与A颜色相同，那么B有2种染法，E也有2种方法，如果D与A染不同的颜色，那么D有2种染法那么B只有一种染法，E有2种染法，所以一共应该有43(122212)96⨯⨯⨯⨯+⨯⨯=种方法，(教师应该向学生说明第三个步骤用到了分类讨论和加法原理，加法原理在下一讲中将会讲授)，染色步骤选择的经验方法：每一步骤所染的区块应该尽量和之前所染的区块相邻．【答案】96【巩固】某沿海城市管辖7个县，这7个县的位置如右图．现用红、黑、绿、蓝、紫五种颜色给右图染色，要求任意相邻的两个县染不同颜色，共有多少种不同的染色方法?【考点】乘法原理之染色问题【难度】4星【题型】解答【解析】为了便于分析，把地图上的7个县分别编号为A、B、C、D、E、F、G(如左下图)．GF DC B AE为了便于观察，在保持相邻关系不变的情况下可以把左图改画成右图．那么，为了完成地图染色这件工作需要多少步呢?由于有7个区域，我们不妨按A 、B 、C 、D 、E 、F 、G 的顺序，用红、黑、绿、蓝、紫五种颜色依次分7步来完成染色任务．第1步：先染区域A ，有5种颜色可供选择；第2步：再染区域B ，由于B 不能与A 同色，所以区域B 的染色方式有4种；第3步：染区域C ，由于C 不能与B 、A 同色，所以区域C 的染色方式有3种；第4步：染区域D ，由于D 不能与C 、A 同色，所以区域D 的染色方式有3种；第5步：染区域E ，由于E 不能与D 、A 同色，所以区域E 的染色方式有3种；第6步：染区域F ，由于F 不能与E 、A 同色，所以区域F 的染色方式有3种；第7步：染区域G ，由于G 不能与C 、D 同色，所以区域G 的染色方式有3种．根据分步计数的乘法原理，共有54333334860⨯⨯⨯⨯⨯⨯=种不同的染色方法．【答案】4860【例 6】 用3种颜色把一个33⨯的方格表染色，要求相同行和相同列的3个格所染的颜色互不相同，一共有 种不同的染色法．【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】 根据题意可知，染完后这个33⨯的方格表每一行和每一列都恰有3个颜色．用3种颜色染第一行，有336P =种染法；染完第一行后再染第一列剩下的2个方格，有2种染法；当第一行和第一列都染好后，再根据每一行和每一列都恰有3个颜色对剩下的方格进行染色，可知其余的方格都只有唯一一种染法．所以，根据乘法原理，共有326⨯=种不同的染法．【答案】6【例 7】 如右图，有A 、B 、C 、D 、E 五个区域，现用五种颜色给区域染色，染色要求：每相邻两个区域不同色，每个区域染一色．有多少种不同的染色方式？EDC BA 【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】 先采用分步：第一步给A 染色，有5种方法；第二步给B 染色，有4种方式；第三步给C 染色，有3种方式；第四步给D 染色，有3种方式；第五步，给E 染色，由于E 不能与A 、B 、D 同色，但可以和C 同色．此时就出现了问题：当D 与B 同色时，E 有3种颜色可染；而当D 与B 异色时，E 有2种颜色可染．所以必须从第四步就开始分类：第一类，D 与B 同色．E 有3种颜色可染，共有5433180⨯⨯⨯=（种）染色方式；第二类，D 与B 异色．D 有2种颜色可染，E 有2种颜色可染，共有54322240⨯⨯⨯⨯=（种）染色方式．根据加法原理，共有180240420+=（种）染色方式．【注意】给图形染色问题中有的可以直接用乘法原理解决，但如果碰到有首尾相接的图形往往需要分类解决．【答案】420【巩固】 如右图，有A ，B ，C ，D 四个区域，现用四种颜色给区域染色，要求相邻区域的颜色不同，每个区域染一色．有多少种染色方法？D C B A【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】 A 有4种颜色可选，然后分类：第一类：B ，D 取相同的颜色．有3种颜色可染，此时D 也有3种颜色可选．根据乘法原理，不同的染法有43336⨯⨯=（种）；第二类：当B ，D 取不同的颜色时，B 有3种颜色可染，C 有2种颜色可染，此时D 也有2种颜色可染．根据乘法原理，不同的染法有432248⨯⨯⨯=（种）．根据加法原理，共有364884+=(种)染色方法．【答案】84【巩固】用四种颜色对右图的五个字染色，要求相邻的区域的字染不同的颜色，但不是每种颜色都必须要用．问：共有多少种不同的染色方法?学奥而思数【考点】乘法原理之染色问题【难度】3星【题型】解答【解析】第一步给“而”上色，有4种选择；然后对“学”染色，“学”有3种颜色可选；当“奥”，“数”取相同的颜色时，有2种颜色可选，此时“思”也有2种颜色可选，不同的涂法有32212⨯⨯=种；当“奥”，“数”取不同的颜色时，“奥”有2种颜色可选，“数”剩仅1种颜色可选，此时“思”也只有1种颜色可选(与“学”相同)，不同的涂法有32116⨯⨯⨯=种．所以，根据加法原理，共有43(222)72⨯⨯⨯+=种不同的涂法．【答案】72【例 8】分别用五种颜色中的某一种对下图的A，B，C，D，E，F六个区域染色，要求相邻的区域染不同的颜色，但不是每种颜色都必须要用．问：有多少种不同的染法？【考点】乘法原理之染色问题【难度】4星【题型】解答【解析】先按A，B，D，C，E的次序染色，可供选择的颜色依次有5，4，3，2，3种，注意E与D的颜色搭配有339⨯=(种)，其中有3种E和D同色，有6种E和D异色．最后染F，当E与D同色时有3种颜色可选，当E与D异色时有2种颜色可选，所以共有542(3362)840⨯⨯⨯⨯+⨯=种染法．【答案】840【例 9】将图中的○分别涂成红色、黄色或绿色，要求有线段相连的两个相邻○涂不同的颜色，共有多少种不同涂法？D CBA【考点】乘法原理之染色问题【难度】3星【题型】解答【解析】如右上图，当A，B，C，D的颜色确定后，大正方形四个角上的○的颜色就确定了，所以只需求A，B，C，D有多少种不同涂法．按先A，再B，D，后C的顺序涂色．按---A B D C的顺序涂颜色：A有3种颜色可选；当B，D取相同的颜色时，有2种颜色可选，此时C也有2种颜色可选，不同的涂法有32212⨯⨯=种；当B，D取不同的颜色时，B有2种颜色可选，D仅剩1种颜色可选，此时C也只有1种颜色可选(与A相同)，不同的涂法有32116⨯⨯⨯=(种)．所以，根据加法原理，共有12618+=种不同的涂法．【答案】18【例 10】用4种不同的颜色来涂正四面体（如图，每个面都是完全相同的正三角形）的4个面，使不同的面涂有不同的颜色，共有________种不同的涂法.（将正四面体任意旋转后仍然不同的涂色法，才被认为是不同的）【考点】乘法原理之染色问题【难度】4星【题型】填空【关键词】迎春杯，中年级，复赛，第9题【解析】不旋转时共有4×3×2×1=24种染色方式，而一个正四面体有4×3=12种放置方法（4个面中选1个作底面，再从剩余3个面中选1个作正面），所以每种染色方式被重复计算了12次，则不同的染色方法有24÷12=2种。

7-2-3乘法原理之染色问题1.使学生掌握乘法原理主要内容，掌握乘法原理运用的方法；2.使学生分清楚什么时候用乘法原理，分清有几个必要的步骤，以及各步之间的关系．3.培养学生准确分解步骤的解题能力；乘法原理的数学思想主旨在于分步考虑问题，本讲的目的也是为了培养学生分步考虑问题的习惯．一、乘法原理概念引入老师周六要去给同学们上课，首先得从家出发到长宁上8点的课，然后得赶到黄埔去上下午1点半的课．如果说申老师的家到长宁有5种可选择的交通工具（公交、地铁、出租车、自行车、步行），然后再从长宁到黄埔有2种可选择的交通工具（公交、地铁），同学们，你们说老师从家到黄埔一共有多少条路线？我们看上面这个示意图，老师必须先的到长宁，然后再到黄埔．这几个环节是必不可少的，老师是一定要先到长宁上完课，才能去黄埔的．在没学乘法原理之前，我们可以通过一条一条的数，把线路找出来，显而易见一共是10条路线．但是要是老师从家到长宁有25种可选择的交通工具，并且从长宁到黄埔也有30种可选择的交通工具，那一共有多少条线路呢？这样数，恐怕是要耗费很多的时间了．这个时候我们的乘法原理就派上上用场了．二、乘法原理的定义完成一件事，这个事情可以分成n个必不可少的步骤（比如说老师从家到黄埔，必须要先到长宁，那么一共可以分成两个必不可少的步骤，一是从家到长宁，二是从长宁到黄埔），第1步有A种不同的方法，第二步有B种不同的方法，……，第n步有N种不同的方法.那么完成这件事情一共有A x B x……x N种不同的方法．结合上个例子，老师要完成从家到黄埔的这么一件事，需要2个步骤，第1步是从家到长宁，一共5种选择；第2步从长宁到黄埔，一共2种选择；那么老师从家到黄埔一共有5x2个可选择的路线了，即10条.三、乘法原理解题三部曲1、完成一件事分N个必要步骤；2、每步找种数（每步的情况都不能单独完成该件事）；3、步步相乘四、乘法原理的考题类型1、路线种类问题——比如说老师举的这个例子就是个路线种类问题；2、字的染色问题——比如说要3个字，然后有5种颜色可以给每个字然后，问3个字有多少种染色方法；3、地图的染色问题——同学们可以回家看地图，比如中国每个省的染色情况，给你几种颜色，问你一张包括几个部分的地图有几种染色的方法；4、排队问题——比如说6个同学，排成一个队伍，有多少种排法；5、数码问题——就是对一些数字的排列，比如说给你几个数字，然后排个几为数的偶数，有多少种排法．【例1】地图上有A, B, C, D四个国家（如下图），现有红、黄、蓝三种颜色给地图染色，使相邻国家的颜色不同，但不是每种颜色都必须要用，问有多少种染色方法？【考点】乘法原理之染色问题【难度】3星【题型】解答【解析】A有3种颜色可选；当B, C取相同的颜色时，有2种颜色可选，此时D也有2种颜色可选.根据乘法原理，不同的涂法有3x 2x 2=12种；当B, C取不同的颜色时，B有2种颜色可选，C仅剩1种颜色可选，此时D也只有1种颜色可选（与A相同）.根据乘法原理，不同的涂法有3x2x 1 x 1=6种.综上，根据加法原理，共有12 + 6=18种不同的涂法.【答案】18【巩固】如果有红、黄、蓝、绿四种颜色给例题中的地图染色,使相邻国家的颜色不同,但不是每种颜色都必须要用,问有多少种染色方法？【考点】乘法原理之染色问题【难度】3星【题型】解答【解析】第一步，首先对A进行染色一共有4种方法，然后对B、C进行染色，如果B、C取相同的颜色，有三种方式，D 剩下3种方式，如果B、C取不同颜色，有3x2=6种方法，D剩下2种方法，对该图的染色方法一共有4x（3x3 + 3x2x2）= 84种方法.【注意】给地图染色问题中有的可以直接用乘法原理解决，有的需要分类解决，前者分类做也可以解决问题. 【答案】84【例2】在右图的每个区域内涂上A、B、C、D四种颜色之一，使得每个圆里面恰有四种颜色，则一共有 __________ 种不同的染色方法．【考点】乘法原理之染色问题【难度】4星【题型】解答【解析】因为每个圆内4个区域上染的颜色都不相同，所以一个圆内的4个区域一共有4x3x2=24种染色方法.如右图所示，当一个圆内的1、2、3、4四个区域的颜色染定后，由于6号区域的颜色不能与2、3、4三个区域的颜色相同，所以只能与1号区域的颜色相同，同理5号区域只能与4号区域的颜色相同，7号区域只能与2号区域的颜色相同，所以当1、2、3、4四个区域的颜色染定后，其他区域的颜色也就相应的只有一种染法，所以一共有24种不同的染法.【答案】24【例3】如图，地图上有A，B，C，D四个国家，现用五种颜色给地图染色，要使相邻国家的颜色不相同，有多少种不同染色方法?ABC D【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】为了按要求给地图上的这四个国家染色，我们可以分四步来完成染色的工作：第一步：给A 染色，有5种颜色可选.第二步：给B 染色，由于B 不能与A 同色，所以B 有4种颜色可选.第三步：给C 染色，由于C 不能与A 、B 同色，所以C 有3种颜色可选.第四步：给D 染色，由于D 不能与B 、C 同色，但可以与A 同色，所以D 有3种颜色可选. 根据分步计数的乘法原理，用5种颜色给地图染色共有5 x 4 x 3 x 3=180种不同的染色方法. 【答案】180 【巩固】如图，一张地图上有五个国家A , B , C , D , E ，现在要求用四种不同的颜色区分不同国家，要求相邻的国家不能使用同一种颜色，不同的国家可以使用同—种颜色，那么这幅地图有多少着色 方法？【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】第一步，给A 国上色，可以任选颜色，有四种选择；第二步，给B 国上色，B 国不能使用A 国的颜色，有三种选择；第三步，给C 国上色，C 国与B , A 两国相邻，所以不能使用A , B 国的颜色，只有两种选择；第四步，给D 国上色，D 国与B , C 两国相邻，因此也只有两种选择；第五步，给E 国上色，E 国与C , D 两国相邻，有两种选择.共有4x 3x 2x 2x 2=96种着色方法.【答案】96【例 4】 如图：将一张纸作如下操作，一、用横线将纸划为相等的两块，二、用竖线将下边的区块划为相等的两块，三、用横线将最右下方的区块分为相等的两块，四、用竖线将最右下方的区块划为相等的两块……，如此进行8步操作，问：如果用四种颜色对这一图形进行染色，要求相邻区块颜色不同，应该有多少种不同的染色方法？【解析】对这张纸的操作一共进行了8次，每次操作都增加了一个区块，所以8次操作后一共有9个区块， 我们对这张纸，进行染色就需要9个步骤，从最大的区块从大到小开始染色，每个步骤地染色方法 有：4、3、2、2、2 ，所以一共有：4x 3x 2x 2x 2x 2x 2x 2x 2 = 1536 种.【答案】1536 【巩固】用三种颜色去涂如图所示的三块区域，要求相邻的区域涂不同的颜色，那么共有几种不同的涂法？【考点】乘法原理之染色问题 【题型】解答【难度】3星【考点】乘法原理之染色问题 【难度】2星 【题型】解答【解析】涂三块毫无疑问是分成三步.第一步，涂A 部分，那么就有三种颜色的选择；第二步，涂B 部分， 由于要求相邻的区域涂不同的颜色，A 和B 相邻，当A 确定了一种颜色后，B 只有两种颜色可选择 了；第三步，涂C 部分，C 和A 、B 都相邻，A 和B 确定了两种不相同的颜色，那么C 只有一种颜 色可选择了.然后再根据乘法原理.3x 2x 1=6【答案】6【例 5】 如图，有一张地图上有五个国家，现在要用四种颜色对这一幅地图进行染色，使相邻的国家所染的颜色不同，不相邻的国家的颜色可以相同.那么一共可以有多少种染色方法？【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】这一道题实际上就是例题，因为两幅图各个字母所代表的国家的相邻国家是相同的，如果将本题中的地图边界进行直角化就会转化为原题，所以对这幅地图染色同样一共有4x 3x 2x 2x 2=96种方法.【讨论】如果染色步骤为C - A - B - D - E ,那么应该该如何解答？答案：也是4x 3x 2x 2x 2=96种方法.如果染色步骤为C - A - D - B - E 那么应该如何解答？答案：染色的前两步一共有4x3种方法，但染第 三步时需要分类讨论，如果D 与A 颜色相同，那么B 有2种染法，E 也有2种方法，如果D 与A 染 不同的颜色，那么D 有2种染法那么B 只有一种染法，E 有2种染法，所以一共应该有4x 3x （1x 2x 2 + 2x 1 x 2） = 96种方法，（教师应该向学生说明第三个步骤用到了分类讨论和加法原理，加法原理在下一讲中将会讲授），染色步骤选择的经验方法：每一步骤所染的区块应该尽量和之前所 染的区块相邻.【答案】96 【巩固】某沿海城市管辖7个县，这7个县的位置如右图．现用红、黑、绿、蓝、紫五种颜色给右图染色，要求任意相邻的两个县染不同颜色，共有多少种不同的染色方法?为了便于分析，把地图上的7个县分别编号为A 、B 、C 、D 、E 、F 、G （如左下图）.为了便于观察，在保持相邻关系不变的情况下可以把左图改画成右图.那么，为了完成地图染色这 件工作需要多少步呢【考点】乘法原理之染色问题 【难度】4星 【题型】解答 【解析】由于有7个区域，我们不妨按A 、B 、C 、D 、E 、F 、G 的顺序，用红、黑、绿、蓝、紫五种颜 色依次分7步来完成染色任务．第1步：先染区域A ，有5种颜色可供选择;再染区域B ，由于B 不能与A 同色，所以区域B 的染色方式有4种； 染区域C ，由于C 不能与B 、A同色，所以区域C 的染色方式有3种； 染区域D ，由于D 不能与C 、A 同色，所以区域D 的染色方式有3种; 染区域E ，由于E 不能与D 、A 同色，所以区域E 的染色方式有3种； 染区域F ，由于F 不能与E 、A 同色，所以区域F 的染色方式有3种; 染区域G ，由于G 不能与C 、D 同色，所以区域G的染色方式有3种.根据分步计数的乘法原理，共有5 x 4 x 3 x 3 x 3 x 3 x 3=4860种不同的染色方法.【答案】4860【例6】 用3种颜色把一个3x 3的方格表染色，要求相同行和相同列的3个格所染的颜色互不相同，一共有 ____ 种不同的染色法.【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】根据题意可知，染完后这个3x 3的方格表每一行和每一列都恰有3个颜色.用3种颜色染第一行，有P 3=6种染法；染完第一行后再染第一列剩下的2个方格，有2种染法； 当第一行和第一列都染好后3，再根据每一行和每一列都恰有3个颜色对剩下的方格进行染色，可知 其余的方格都只有唯一一种染法.所以，根据乘法原理，共有3 x 2=6种不同的染法.【答案】6【例7】 如右图，有A 、B 、C 、D 、E 五个区域，现用五种颜色给区域染色，染色要求：每相邻两个区域不同色，每个区域染一色．有多少种不同的染色方式？【解析】先采用分步：第一步给A 染色，有5种方法；第二步给B 染色，有4种方式；第三步给C 染色，有 3种方式；第四步给D 染色，有3种方式；第五步，给E 染色，由于E 不能与A 、B 、D 同色，但可 以和C 同色.此时就出现了问题：当D 与B 同色时，E 有3种颜色可染；而当D 与B 异色时，E 有 2种颜色可染.所以必须从第四步就开始分类：第一类，D 与B 同色.E 有3种颜色可染，共有5 x 4 x 3 x 3=180 （种）染色方式；第二类，D 与B 异色.D 有2种颜色可染，E 有2种颜色可染，共有5x 4x 3x 2x 2=240 （种）染色 方式.根据加法原理，共有180 + 240=420 （种）染色方式.【注意】给图形染色问题中有的可以直接用乘法原理解决，但如果碰到有首尾相接的图形往往需要分类解决. 【答案】420【巩固】如右图，有A , B , C , D 四个区域，现用四种颜色给区域染色，要求相邻区域的颜色不同，每个区域染一色．有多少种染色方法？【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】A 有4种颜色可选，然后分类：第一类：B , D 取相同的颜色.有3种颜色可染，此时D 也有3种颜色可选.根据乘法原理，不同 的染法有4x 3x 3=36 （种）；第二类：当B , D 取不同的颜色时，B 有3种颜色可染，C 有2种颜色可染，此时D 也有2种颜色 可染.根据乘法原理，不同的染法有4x 3x 2x 2=48 （种）.根据加法原理，共有36 + 48=84（种）染色方法.第2步 第3步 第4步 第5步 第6步 第7步 【考点】 乘法原理之染色问题 【难度】3星 【题型】解答【答案】84 【巩固】用四种颜色对右图的五个字染色，要求相邻的区域的字染不同的颜色，但不是每种颜色都必须要用．问：共有多少种不同的染色方法?【解析】第一步给“而”上色，有4种选择；然后对“学”染色，“学”有3种颜色可选； 当“奥”，“数”取相同的颜色时，有 2 种颜色可选，此时“思”也有 2 种颜色可选，不同的涂法有3 x 2 x 2 = 12 种；当“奥”，“数”取不同的颜色时，“奥”有2种颜色可选，“数”剩仅1种颜色可选，此时“思”也只有1种 颜色可选（与“学”相同），不同的涂法有3 x 2 x 1x 1=6种.所以，根据加法原理，共有4x 3x （2x 2 + 2） = 72种不同的涂法.【答案】72分别用五种颜色中的某一种对下图的A , B , C , D , E , F 六个区域染色，要求相邻的区域染不同的颜色，但不是每种颜色都必须要用．问：有多少种不同的染法？【解析】先按A , B , D , C , E 的次序染色，可供选择的颜色依次有5, 4, 3, 2, 3种，注意E 与D 的颜 色搭配有3 x 3=9（种），其中有3种E 和D 同色，有6种E 和D 异色.最后染F ，当E 与D 同色时 有3种颜色可选，当E 与D 异色时有2种颜色可选，所以共有5x 4x 2x （3x 3 + 6x 2） = 840种染法.【答案】840【例9】 将图中的。

专题14 染色问题1.下图是一套房子的平面图,图中的方格代表房间,每个房间都有通向任何 一个邻室的门.有人想从某个房间开始,依次不重复地走遍每一个房间,他的想法能实现吗?2.展览会有36个展室(如图),每两相邻展室之间均有门相通.能不能从入口 进去,不重复地参观完全部展室后,从出口出来呢?3.图中的16个点表示16个城市,两个点之间的连线表示这两个城市有公路 相通.问能否找到一条不重复地走遍这16座城市的路线?4.下图是由4个小方格组成的“L ”形硬纸片,用若干个这种纸片无重叠地 拼成一个4 n 的长方形,试证明:n 一定是偶数.5.中国象棋盘上最多能放几只马互不相“吃”(“马”走“日”字,另不考虑“别马腿”的情况).6.能否用一个田字和15个4⨯1矩形覆盖8⨯8棋盘?7.能否用1个田字和15个T 字纸片,拼成一个8⨯8的正方形棋盘?8.在8⨯8棋盘上,马能否从左下角的方格出发,不重地走遍棋盘,最后回到起点?若能请找出一条路,若不能,请说明理由.9.下面三个图形都是从4⨯4的正方形分别剪去两个1⨯1的小方格得到的,问可否把它们分别剪成1⨯2的七个小矩形?10.把三行七列的21个小格组成的矩形染色,每个小格染上红、蓝两种色中的一种.求证:总可以找到4个同色小方格,处于某个矩形的4个角上(如图)11.17个科学家互相通信,在他们的通信中共讨论3个问题,而任意两个科学家之间仅讨论1个问题.证明:至少有3个科学家,他们彼此通信讨论的是同一个问题.12.用一批1⨯2⨯4的长方体木块,能不能把一个容积为6⨯6⨯6的正方体木箱充塞填满?说明理由.13.在平面上有一个27⨯27的方格棋盘,在棋盘的正中间摆好81枚棋子,它们被罢成一个9⨯9的正方形.按下面的规则进行游戏:每一枚棋子都可沿水平方向或竖直方向越过相邻的棋子,放进紧挨着这枚棋子的空格中,并把越过的这格棋子取出来.问:是否存在一种走法,使棋盘上最后恰好剩下一枚棋子?14.12⨯12的超极棋盘上,一匹超级马每步跳至3⨯4矩形的另一角(如图).问能否从任一点出发遍历每一格恰一次,再回到出发点(这种情况又称马有“回12 3———————————————答 案——————————————————————1. 不能.对房间染色,使最下面的两个房间染成黑色,与黑色相邻的房染成白色,则图中有7个黑色房间和5个白色房间.如果要想不重复地走过每一个房间,黑色与白色房间数应该相等.故题中的想法是不能实现的.2. 不能.对展室进行染色,使相邻两房间分别是黑色和白色的.此时入口处展室的颜色与出口处展室的颜色是相同的,而不重复参观完36个展室,入口与出口展室的颜色应该不相同.3. 不能.对这16个城市进行黑白相间的染色,一种颜色有9个,另一种颜色有7个.而要不重复地走遍这16个城市,黑色与白色的个数应该相等.4. 如图,对4⨯n 长方形的各列分别染上黑色和白色.任一L 形纸片所占的方3黑1白,第二类占3白1黑.设第一类有a 个,第二类有b 个,因为涂有两种颜色的方格数相等,故有3b +a =3a +b ,即a =b ,也就是说第一类与第二类相等,因此各种颜色的方格数都是4的倍数,总数是8的倍数,从而n 是偶然.5. 将棋盘黑白相间染色,由“马”的走法可知,放在黑点上的“马”,只能吃放在某些白点上的马.整个棋盘上黑、白点的个数均为45,故可在45个黑点放上马,它们是不能互吃的.6. 如图的方式对棋盘染色.那么一个田字形盖住1个或3个白格,而一个4⨯1的矩形盖住2个白格.这样一来一个田字和15个4⨯1的矩形能盖住的白格数是一个奇数,但上图中的白格数是一个偶数,因此一个田字形和15个4⨯1的矩形n 个7. 将棋盘里黑白相间涂色.一个田字形盖住2个白格,一个T字形盖住3个或1个白格.故1个田字和15个T字盖住的白格数是一个奇数,但棋盘上的白格数是一个偶数.因此一个田字形和15个T字形不能盖住8⨯8的棋盘.8. 将棋盘黑白相间地染色后,马的走法是从一种颜色的格子跳到另一种颜色.棋盘上有32个白格与32个黑格,故马可能跳遍整个棋盘.图中给出了一种走法.9. 先对4⨯4的棋盘黑白相间的涂色(如图),这道题的实际问题是问7个1⨯2矩形能否分别复盖剪去A、B；剪去A、C；剪去A、D的三个棋盘.若7个1⨯2矩形可以复盖剪残的棋盘,因为每个1⨯2矩形均可盖住一个白格和一个黑格,所以棋盘的白格与黑格数目应该相等.都是7个.而剪去A格和C格的棋盘(2)有5个白格8个黑格,剪去A、D的棋盘(3)有5个白格8个黑格,因此这两个剪损的棋盘均不能被7个也就不能剪成7个1⨯2的矩形.棋盘(1).下面给出一种剪法:10. 在第一行的7格中必有4格同色,不妨设这4格位于前4个位置,且均为红色.然后考虑前4列构成的3⨯4矩形.若第二行和第3行中出现2个或2个以上的红色格子.则该行的两个红色格子与第一行的红色格子就组成一个4角同为红色格子的矩形.若不然,则第2、3行中都至少有3个蓝格在前4列中,不妨设第2行前3格为蓝色,显然第三行中的前3格中至少有2个蓝格，故在二、三行的前4列中必存在四角都是蓝色的矩形.11. 将17个科学家用17个点代表,两点之间连结的线段表示两个科学家之间讨论的问题.用三种颜色给这些线段染色,表示三个问题,于是问题就变成:给17个点之间的所有连结线段用三种颜色染色,必有同色三角形.从任意一点,不妨设从A向其他16点A1,A2,…A16共可连成16条线段,用三种颜色染色,由抽屉原则可知,必有6条线段同色.设这6条线段为AA1,AA2,…AA6且同为红色.考虑A1,A2,A3,A4,A5,A6这六点之间的连线,若有一条为红色,(如A1A2为红色) ,则三角形AA1A2为红色的同色三角形.若这六点之间的连线中,没有一条是红色的,则它们之间只能涂两种颜色.考虑从A1引出的五条线段A1A2A1A3A1A4A1A5A1A6,由抽屉原理知,其中必有三条是同色的.不妨设这三条为A1A2A1A3A1A4,且同为蓝色.若三角形A2A3A4的三边中有一条为蓝色的,则有一个蓝色的三角形存在;若三角形A2A3A4三边都不是蓝色的,则它的三边是同为第三色的同色三角形.12. 把正方体木箱分成27个小正方体,每个小正方体的体积为2⨯2⨯2=8.将这些正方体如右图黑白相间染上色.显然黑色2⨯2⨯2的正方体有14个,白色2⨯2⨯2小正方体有13个.每一个这样的正方体相当于8个1⨯1⨯1的小正方体.将1⨯2⨯4的长方体放入木箱,无论怎么放,每个长方体木块盖住8个边长为1的单位正方体,其中有4个黑色的,4个白色的.木箱共含6⨯6⨯6=216个单位正方体,26个长方体木块共盖住8⨯26=208个单位正方体,其中黑白各占104个,余下216-208=8个单位正方体是黑色的.但是第27个1⨯2⨯4长方体木块不管怎样放,也无法盖住这8个黑色单位正方体.13. 如图,将整个棋盘的每一格都分别染上红、白、黑三种颜色,这种染色方式将棋盘分成了三个部分.按照游戏规则,每走一步,有两种颜色方格中的棋子数分别减少了1个,而第三种颜色的棋子数增加了一个.这表明每走一步,每个部.AA1 A2A3A4A5A6A1A2A3A4因为一开始时,81枚棋子摆成一个9 9的正方形,显然三个部分的棋子数是相同的,从而每走一步,三部分中的棋子数的奇偶性是相同的.如果走了若干步以后,棋盘上恰好剩下一枚棋子,则两部分上的棋子数为偶数,而另一部分上的棋子数为奇数.这种结果是不可能出现的.14. 用两种方法对超级棋盘染色.首先,将棋盘黑白相间染色,则马每跳一步,它所在的方格就要改变一次颜色.不妨设第奇数步跳入白格.其次,将棋盘的第3,4,5及8,9,10这六行染成黑色,其余六行染成白色.在此种染色方式下,马从白格一定跳入黑格.又因黑白格总数相同,马要遍历每一格恰一次又回到出发点,因此,马从黑格只能跳入白格而不能跳入黑格.不妨设马第奇数步跳入白格.但是对于一种满足要求跳法,在两种染色方式下第奇数步跳入的格子的全体是不同的,这显然是不可能的,故题目要求的跳法是不存在的.。

染色问题（一）染色问题是一种将题目研究对象分类的形象化方法，通过将问题中的对象适当染色，我们可以更形象地观察分析出其中蕴含的关系，再经过一定的逻辑推理，便能得出问题的答案。

因此，这里的染色问题指的是一种解题方法。

这类问题不需要太多的数学知识，但技巧性、逻辑性较强，要注意学会集中典型的染色方法。

根据具体题目的研究对象，染色方法大致可以分为对点染色、对线段染色、对方格染色和对区域染色。

对方格染色常用的是黑白方格相间染色，也叫自然染色。

例1如右图，在5×5方格的A格中有一只爬虫，它每次总是朝上下左右方向爬到相邻的方格中。

那么他能否不重复的爬满每个方格再回A到A格中？解：有小虫的爬法，可黑白相间对方格自然染色，于是小虫只能由黑格爬到白格或白格爬到黑格。

所以它由A出发回到A，即黑格爬到黑格，必须经过偶数步。

而小方格为5×5=25个，每格爬过一次，就应该为25步，不是偶数。

于是这只爬虫不可能不重复地爬遍每格再回到A格。

例2 有一次车展有6×6=36个展室，如图。

每格展室与相邻的展室都有门相通，入口和出口如图所示。

参观者能否从入口进去，不重复地参观完每格展室在从出口出来？解：如图，对每个展室黑白相间染色，同样每次只能冲黑格到白格或者从白格到黑格。

入口和出口都是白格，故线路黑白相间，首位都是白格，于是应该白格比合格多1个，而实际上白格、黑格都是18个，故不能做到不重复走遍每个展室。

例3 右图是某一套房子的平面图，共12个房间，每相邻两间房间都有门相通。

请问，你能从某个房间出发，不重复地走完每个房间吗？解：如图所示，将房间黑白相间染色，发现只有5个黑格、7个白格。

因为每次只能从黑到白或者白到黑，路线必然是黑白相间，显然应该从多的白格开始。

但路线上1白1黑......直至5白5黑后还多余2白格，不可能从白到黑。

故无法实现不重复地走遍每个房间。

小结：染色问题的解题技巧主要在于染色具体方案的构造，其基本原则是使题目条件出现一定的规律，以利于解题。

染色问题(1)年级班姓名得分(编者按:由于内容本身的限制,本讲不设填空题)1.某影院有31排,每排29个座位.某天放映了两场电影,每个座位上都坐了一个观众.如果要求每个观众在看第二场电影时必须跟他(前、后、左、右)相邻的某一观众交换座位,这样能办到吗?为什么?2.如图是一所房子的示意图,图中数字表示房间号码,每间房子都与隔壁的房间相通.问能否从1号房间开始,不重复的走遍所有房间又回到1号房间?1 2 34 5 67 8 93.在一个正方形的果园里,种有63棵果树、加上右下角的一间小屋,整齐地排列成八行八列(见图 (a)).守园人从小屋出发经过每一棵树,不重复也不遗漏(不许斜走),最后又回到小屋,行吗?如果有80棵果树,连小屋在内排成九行九列(图(b))呢?(a) (b)4.一个8⨯8国际象棋(下图)去掉对角上两格后,是否可以用31个2⨯1的“骨牌” (形如 )把象棋盘上的62个小格完全盖住?5.如果在中国象棋盘上放了多于45只马,求证:至少有两只马可以“互吃”.6.空间6个点,任三点不共线,对以它们为顶点的线段随意涂以红色或蓝色,是否必有两个同色三角形?7.如图,把正方体分割成27个相等的小正方体,在中心的那个小正方体中有一只甲虫,甲虫能从每个小正方体走到与这个正方体相邻的6个小正方体中的任一个中去.如果要求甲虫能走到每个小正方体一次,那么甲虫能走遍所有的正方体吗?8.中国象棋的马走“日”字,车走横线或竖线,下图是半张中国象棋盘,试回答下面的问题:一只马从起点出发,跳了n 步又回到起点.证明:n 一定是偶数.9.中国象棋的马走“日”字,车走横线或竖线,下图是半张中国象棋盘,试回答下面的问题:一只马能否跳遍这半张棋盘,每一点都不重复,最后一步跳回起点?10.中国象棋的马走“日”字,车走横线或竖线,下图是半张中国象棋盘,试回答下面的问题:ABA B证明:一只马不可能从位置B 出发,跳遍半张棋盘而每个点都只经过一次(不要求最后一步跳回起点).11.中国象棋的马走“日”字,车走横线或竖线,下图是半张中国象棋盘,试回答下面的问题:一只马能否从位置B 出发,用6步跳到位置A ?为什么?12.中国象棋的马走“日”字,车走横线或竖线,下图是半张中国象棋盘,试回答下面的问题:一只车从位置A 出发,在这半张棋盘上走,每步走一格,走了若干步后到了位置B .证明:至少有一个格点没被走过或被走了不止一次.13.8⨯8的国际象棋棋盘能不能被剪成7个2⨯2的正方形和9个4⨯1的长方形?如果可以,请给出一种剪法;如果不行,请说明理由.14.(表1)是由数字0,1交替构成的,(表2)是由(表1)中任选 、 、三种形式组成的图形,并在每个小方格全部加1或减1,如此反复多次进行形成的,试问(表2)中的A 格上的数字是多少?并说明理由.1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1ABABA B表 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 A 11 1 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 1表 2———————————————答案——————————————————————1. 把影院的座位图画成黑白相间的矩形.(29⨯31),共有899个小方格.不妨假定四角为黑格,则共有黑格450个,白格449个.要求看第二场电影,每位观众必须跟他相邻的某一观众交换位置,即要求每一黑白格必须互换,因黑白格的总数不相等,因此是不可能的.2. 将编号为奇数的房间染成黑色,编号为偶数的房间染成白色.从1号房间出发,只能按黑白黑白……的次序,当走遍九个房间时应在黑色房间中,这个房间不与1号房间相邻,故不能不重复地走遍所有房间又回到1号房间.3. 图(a)行,走法如图所示.图(a)图(b)不行,将小屋染成黑色,果树染成黑白相间的颜色,则图(b)中有41个黑色的,40个白色的.从小屋出发,按黑白黑白……的次序,当走遍80棵树后,到达的树的颜色还是黑色,与小屋不相邻,故不可能最后回到小屋.4. 不能.原因是每一个2⨯1的矩形骨牌一定恰好盖住一个黑格和一个白格,31个这样的骨牌恰好盖住31个黑格和31个白格.但是国际象棋棋盘上对角两格的颜色是相同的,把它们去掉后剩下的是30个白格,32个黑格,或32个白格,30个黑格,因此不能盖住.5. 中国象棋棋盘上有90个交叉点,把棋盘分成10个小部分,每部分有3 3=9个交叉点,由抽屉原则知,至少有一个小部分内含有6只马.将这一小部分的9个交叉点分别涂上黑色及白色.总有两只马在不同颜色交叉点上,故一定有两只马“互吃”.6. 设这六个点为A 、B 、C 、D 、E 、F.我们先证明存在一个同色的三角形: 考虑由A 点引出的五条线段AB 、AC 、AD 、AE 、AF,其中必有三条被染成了相同的颜色,不妨设AB 、AC 、AD 三条同为红色.再考虑三角形BCD 的三边:若其中有一条为红色,则存在一个红色三角形;若这三条都不是红色,则三角形BCD 为蓝色三角形.下面再来证明有两个同色三角形,不妨设三角形ABC 的三边同为红色. (1)若三角形DEF 也是红色三角形,则存在两个同色三角形.(2)若三角形DEF 中有一条边为蓝色(不妨设DE),下面考虑DA 、DB 、DC 三 条线段，其中必有两条同色.①若其中有两条是红色的,如DA 、DB 是红色的,则三角形DAB 为第二个同色三角形(图1).②若其中有两条是蓝色的,设DA 、DB 为蓝色(图2).此时在EA 、EB 两条线段中,若有一条为蓝色,则存在一个蓝色三角形;若两条都是红色的,则三角形EAB 为红色三角形.综上所述,一定有两个同色三角形.7. 甲虫不能走遍所有的立方体.我们将大正方体如图分割成27个小正方体,涂上黑白相间的两种颜色,使得中心的小正方体染成白色,再使两个相邻的小正方体染上不同的颜色.显然在27A B DCA BC D E (图1) A BCDE (图2)个小正文体中,14个是黑的,13个是白的.甲虫从中间的白色正方体出发,每走一步,小正方体就改变一种颜色.故它走27步,应该经过14个白色的小正方体,13个黑色的小正方体.因此在27步中至少有一个白色的小正方体,甲虫进去过两次.故若要求甲虫到每个小正方体只去一次,甲虫就不能走遍所有的小正方体.8. 将棋盘上的各点按黑白相间的方式染上黑白二色.由“马步”的行走规则,当“马”从黑点出发,下一步只能跳到白点,以后依次是黑、白、黑、白……要回到原出发点(黑点),它必须跳偶数步.9. 不能.半张象棋盘共有45个格点,马从起点出发跳遍半张棋盘,则起点与最后一步同色.故不可能从最后一步跳回起点.10. 与B 点同色的点(白点)有22个,异色的点(黑色)有23个.马从B 点出发,跳了42步时,已经跳遍了所有的白色,还剩下两个黑点,但是马不能够连续跳过两个黑点.11. 不能.因为A 、B 两点异色,从B 到A 所跳的步数是一个奇数.12. “车”每走一步,所在的格点就会改变一次颜色.因A 、B 两点异色,故从A 到B “车”走的步数是一个奇数.但半张棋盘共有45个格点,不重复地走遍半张棋盘要44步，但44是一个偶数.13. 如图对8⨯8的棋盘染色,则每一个4⨯1的长方形能盖住2白2黑小方格,而每一个2⨯2的正方形能盖住1白3黑或1黑3白小方格,那么7个2⨯2的正方形盖住的黑色小方格数总是一个奇数,但图中黑格数为32是一个偶数.故这种剪法是不存在的.14. 如下图所示,将表(1)黑白相间地染色.+1 +1 +1 +1-1 -1 -1 -1+1 +1 +1 +1 +1 +1-1 -1 -1 -1 -1 -1+1 +1 +1 +1+1 +1-1 -1 -1 -1-1 -1表(1)本题条件允许如图所示的6个操作,这6个操作无论实行在那个位置上,白格中的数字之和减去黑格中的数字之和总是一个常数,所以表1中白格中数字之和与黑格中数字之和的差即32,等于表2中白格中数字之和与黑格中数字之和的差即(31+A)-32,于是(31+A)-32=32,故A=33.。

第9讲 染色问题【知识要点】染色方法是一种对题目所研究的对象用直观形象的染色来进行分类的方法。

象国际象棋的棋盘那样，我们可以把研究的对象染上不同的颜色，使问题变得浅显明了、一目了然，有利于我们观察、分析对象之间的关系，再利用奇偶性、抽屉原理等多种知识对染色图形进行分析，从而达到对原问题的解决。

【典型例题】例1、教室中有7排位子，每排7张，每张位子上坐一个同学，如果一周后，每个同学都必须和他相邻的（前、后、左、右）某一个同学换位子，问：这种交换可能成功吗？为什么？ 解：如右图所示黑白相间涂色，白色共有25个，黑色24个，要实现题意要求，一个白色位置必须和一个黑色位置互换，黑白座位应该一样多才行，所以办不到。

例2、如图是一所房子的示意图,图中数字表示房间号码,每间房子都与隔壁的房间相通.问能否从1号房间开始,不重复的走遍所有房间又回到1号房间? 解：如图所示每一个奇数号房间旁边一定是偶数号房间，反之亦然，那么奇数号房间一定走到偶数号，偶数号一定走到奇数号，从一号开始走奇数步一定是到偶数号房间，走偶数步一定是到奇数号房间，要不重复的走遍所有房间回到1号房间，共要走9步，应该走到偶数号房间，而1是奇数，所以办不到。

例3、一个8⨯8国际象棋(下图)去掉对角上两格后,是否可以用31个2⨯1的“骨牌” (形如 )把象棋盘上的62个小格完全盖住?解：任意一个2⨯1的“骨牌”一定是一白一黑的，所以若要用31个这样的骨牌覆盖这个棋盘，白黑格数应该一样多，而此棋盘中有32个黑格，30个白格，所以办不到。

例4、线段AB 的两个端点，一个标以红色，一个标以蓝色。

在此线段中任意插入2008个分点，每个分点任意涂上红色或蓝色，这样分得2009条不重叠的小线段，如果把两端涂色不同的线段叫做奥运线段，奥运线段的条数是奇数还是偶数？ 解：原本的线段AB 就是一条奥运线段，然后不管中间插入的点是什么颜色的，都会破坏原来的奥运线段从而变成一条两端同色一条奥运线段，再然后如果在一条奥运线段中间插入任意颜色的点，奥运线段会被破坏，但是又会生成一条较短的，那么奥运线段的数量总数不变；如果在一条两端同色的线段中间插入不同色 1 2 3 4 5 6 7 8 9的点，一下就增加2条奥运线段，不改变奥运线段数量的奇偶性。

奥数题小学四年级数学《染色问题》专项训练及
答案
题型：染色问题难度：★★
如图，把A、B、C、D、M这五个部分用5种不同的颜色染色，且相邻的部分不能使用同一种颜色，有的颜色也可以不用，不相邻的部分可以使用同一种颜色，那么这幅图一共有多少种不同的染色方法?
题型：染色问题难度：★★
如图，9条小线段组成了4个小三角形，现在将每条线段分别染上红、黄、蓝三种颜色之一，使得每个三角形三条边的颜色互不相同，那么共有多少种不同的染色方式?
请在下页参考答案
【答案解析】
如果5种颜色全部使用，那么共有5×4×3×2×1=120种染色方法。

如果只使用4种颜色，可以是B和D同色，也可以是A和C 同色，那么共有5×4×3×2×2=240种染色方法。

如果只使用3种颜色，那么有B和D同色并且A和C同色，共有5×4×3=60种染色方法。

120+240+60=420，所以这幅图一共有420种不同的染色方法。

【答案解析】
任选一个小三角形的一条边，当这条边的颜色确定时，这个小三角形的染色方法有2种，同时每种方法都会确定与其相邻的小三角形的一条边的颜色。

24×3=48，所以共有48种不同的染色方式。

染色问题（一）染色问题是一种将题目研究对象分类的形象化方法，通过将问题中的对象适当染色，我们可以更形象地观察分析出其中蕴含的关系，再经过一定的逻辑推理，便能得出问题的答案。

因此，这里的染色问题指的是一种解题方法。

这类问题不需要太多的数学知识，但技巧性、逻辑性较强，要注意学会集中典型的染色方法。

根据具体题目的研究对象，染色方法大致可以分为对点染色、对线段染色、对方格染色和对区域染色。

对方格染色常用的是黑白方格相间染色，也叫自然染色。

例1如右图，在5×5方格的A格中有一只爬虫，它每次总是朝上下左右方向爬到相邻的方格中。

那么他能否不重复的爬满每个方格再回A到A格中？解：有小虫的爬法，可黑白相间对方格自然染色，于是小虫只能由黑格爬到白格或白格爬到黑格。

所以它由A出发回到A，即黑格爬到黑格，必须经过偶数步。

而小方格为5×5=25个，每格爬过一次，就应该为25步，不是偶数。

于是这只爬虫不可能不重复地爬遍每格再回到A格。

例2 有一次车展有6×6=36个展室，如图。

每格展室与相邻的展室都有门相通，入口和出口如图所示。

参观者能否从入口进去，不重复地参观完每格展室在从出口出来？解：如图，对每个展室黑白相间染色，同样每次只能冲黑格到白格或者从白格到黑格。

入口和出口都是白格，故线路黑白相间，首位都是白格，于是应该白格比合格多1个，而实际上白格、黑格都是18个，故不能做到不重复走遍每个展室。

例3 右图是某一套房子的平面图，共12个房间，每相邻两间房间都有门相通。

请问，你能从某个房间出发，不重复地走完每个房间吗？解：如图所示，将房间黑白相间染色，发现只有5个黑格、7个白格。

因为每次只能从黑到白或者白到黑，路线必然是黑白相间，显然应该从多的白格开始。

但路线上1白1黑......直至5白5黑后还多余2白格，不可能从白到黑。

故无法实现不重复地走遍每个房间。

小结：染色问题的解题技巧主要在于染色具体方案的构造，其基本原则是使题目条件出现一定的规律，以利于解题。

1.使学生掌握乘法原理主要内容，掌握乘法原理运用的方法；2.使学生分清楚什么时候用乘法原理，分清有几个必要的步骤，以及各步之间的关系．3.培养学生准确分解步骤的解题能力；乘法原理的数学思想主旨在于分步考虑问题，本讲的目的也是为了培养学生分步考虑问题的习惯．一、乘法原理概念引入 老师周六要去给同学们上课，首先得从家出发到长宁上8点的课，然后得赶到黄埔去上下午1点半的课．如果说申老师的家到长宁有5种可选择的交通工具（公交、地铁、出租车、自行车、步行），然后再从长宁到黄埔有2种可选择的交通工具（公交、地铁），同学们，你们说老师从家到黄埔一共有多少条路线？我们看上面这个示意图，老师必须先的到长宁，然后再到黄埔．这几个环节是必不可少的，老师是一定要先到长宁上完课，才能去黄埔的．在没学乘法原理之前，我们可以通过一条一条的数，把线路找出来，显而易见一共是10条路线．但是要是老师从家到长宁有25种可选择的交通工具，并且从长宁到黄埔也有30种可选择的交通工具，那一共有多少条线路呢？这样数，恐怕是要耗费很多的时间了．这个时候我们的乘法原理就派上上用场了．二、乘法原理的定义完成一件事，这个事情可以分成n 个必不可少的步骤（比如说老师从家到黄埔，必须要先到长宁，那么一共可以分成两个必不可少的步骤，一是从家到长宁，二是从长宁到黄埔），第1步有A 种不同的方法，第二步有B 种不同的方法，……，第n 步有N 种不同的方法．那么完成这件事情一共有A ×B ×……×N 种不同的方法．结合上个例子，老师要完成从家到黄埔的这么一件事，需要2个步骤，第1步是从家到长宁，一共5种选择；第2步从长宁到黄埔，一共2种选择；那么老师从家到黄埔一共有5×2个可选择的路线了，即10条．三、乘法原理解题三部曲1、完成一件事分N 个必要步骤；2、每步找种数（每步的情况都不能单独完成该件事）；3、步步相乘教学目标 知识要点7-2-3乘法原理之染色问题四、乘法原理的考题类型1、路线种类问题——比如说老师举的这个例子就是个路线种类问题；2、字的染色问题——比如说要3个字，然后有5种颜色可以给每个字然后，问3个字有多少种染色方法；3、地图的染色问题——同学们可以回家看地图，比如中国每个省的染色情况，给你几种颜色，问你一张包括几个部分的地图有几种染色的方法；4、排队问题——比如说6个同学，排成一个队伍，有多少种排法；5、数码问题——就是对一些数字的排列，比如说给你几个数字，然后排个几为数的偶数，有多少种排法．【例 1】 地图上有A ，B ，C ，D 四个国家(如下图)，现有红、黄、蓝三种颜色给地图染色，使相邻国家的颜色不同，但不是每种颜色都必须要用，问有多少种染色方法？DC B A【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】 A 有3种颜色可选；当B ，C 取相同的颜色时，有2种颜色可选，此时D 也有2种颜色可选．根据乘法原理，不同的涂法有32212⨯⨯=种；当B ，C 取不同的颜色时，B 有2种颜色可选，C 仅剩1种颜色可选，此时D 也只有1种颜色可选(与A 相同)．根据乘法原理，不同的涂法有32116⨯⨯⨯=种．综上，根据加法原理，共有12618+=种不同的涂法．【答案】18【巩固】 如果有红、黄、蓝、绿四种颜色给例题中的地图染色，使相邻国家的颜色不同，但不是每种颜色都必须要用，问有多少种染色方法？【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】 第一步，首先对A 进行染色一共有4种方法，然后对B 、C 进行染色，如果B 、C 取相同的颜色，有三种方式，D 剩下3种方式，如果B 、C 取不同颜色，有326⨯=种方法，D 剩下2种方法，对该图的染色方法一共有43332284⨯⨯+⨯⨯=（）种方法．【注意】给地图染色问题中有的可以直接用乘法原理解决，有的需要分类解决，前者分类做也可以解决问题．【答案】84【例 2】 在右图的每个区域内涂上A 、B 、C 、D 四种颜色之一，使得每个圆里面恰有四种颜色，则一共有__________种不同的染色方法．7654321【考点】乘法原理之染色问题 【难度】4星 【题型】解答【解析】 因为每个圆内4个区域上染的颜色都不相同，所以一个圆内的4个区域一共有43224⨯⨯=种染色方法．如右图所示，当一个圆内的1、2、3、4四个区域的颜色染定后，由于6号区域的颜色不能与2、3、4三个区域的颜色相同，所以只能与1号区域的颜色相同，同理5号区域只能与4号区域的颜色相同，7号区域只能与2号区域的颜色相同，所以当1、2、3、4四个区域的颜色染定后，其他区例题精讲域的颜色也就相应的只有一种染法，所以一共有24种不同的染法．【答案】24【例 3】 如图，地图上有A ，B ，C ，D 四个国家，现用五种颜色给地图染色，要使相邻国家的颜色不相同，有多少种不同染色方法?DCB A【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】 为了按要求给地图上的这四个国家染色，我们可以分四步来完成染色的工作：第一步：给A 染色，有5种颜色可选．第二步：给B 染色，由于B 不能与A 同色，所以B 有4种颜色可选．第三步：给C 染色，由于C 不能与A 、B 同色，所以C 有3种颜色可选．第四步：给D 染色，由于D 不能与B 、C 同色，但可以与A 同色，所以D 有3种颜色可选．根据分步计数的乘法原理，用5种颜色给地图染色共有5433180⨯⨯⨯=种不同的染色方法．【答案】180【巩固】 如图，一张地图上有五个国家A ，B ，C ，D ，E ，现在要求用四种不同的颜色区分不同国家，要求相邻的国家不能使用同一种颜色，不同的国家可以使用同—种颜色，那么这幅地图有多少着色方法？ED C BA【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】 第一步，给A 国上色，可以任选颜色，有四种选择；第二步，给B 国上色，B 国不能使用A 国的颜色，有三种选择；第三步，给C 国上色，C 国与B ，A 两国相邻，所以不能使用A ，B 国的颜色，只有两种选择；第四步，给D 国上色，D 国与B ，C 两国相邻，因此也只有两种选择；第五步，给E 国上色，E 国与C ，D 两国相邻，有两种选择． 共有4322296⨯⨯⨯⨯=种着色方法．【答案】96【例 4】 如图：将一张纸作如下操作，一、用横线将纸划为相等的两块，二、用竖线将下边的区块划为相等的两块，三、用横线将最右下方的区块分为相等的两块，四、用竖线将最右下方的区块划为相等的两块……，如此进行8步操作，问：如果用四种颜色对这一图形进行染色，要求相邻区块颜色不同，应该有多少种不同的染色方法？【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】 对这张纸的操作一共进行了8次，每次操作都增加了一个区块，所以8次操作后一共有9个区块，我们对这张纸，进行染色就需要9个步骤，从最大的区块从大到小开始染色，每个步骤地染色方法有：4、3、2、2、2……，所以一共有：4322222221536⨯⨯⨯⨯⨯⨯⨯⨯=种．【答案】1536【巩固】用三种颜色去涂如图所示的三块区域，要求相邻的区域涂不同的颜色，那么共有几种不同的涂法？ABC【考点】乘法原理之染色问题【难度】2星【题型】解答【解析】涂三块毫无疑问是分成三步．第一步，涂A部分，那么就有三种颜色的选择；第二步，涂B部分，由于要求相邻的区域涂不同的颜色，A和B相邻，当A确定了一种颜色后，B只有两种颜色可选择了；第三步，涂C部分，C和A、B都相邻，A和B确定了两种不相同的颜色，那么C只有一种颜色可选择了．然后再根据乘法原理．3216⨯⨯=【答案】6【例5】如图，有一张地图上有五个国家，现在要用四种颜色对这一幅地图进行染色，使相邻的国家所染的颜色不同，不相邻的国家的颜色可以相同．那么一共可以有多少种染色方法？【考点】乘法原理之染色问题【难度】3星【题型】解答【解析】这一道题实际上就是例题，因为两幅图各个字母所代表的国家的相邻国家是相同的，如果将本题中的地图边界进行直角化就会转化为原题，所以对这幅地图染色同样一共有4322296⨯⨯⨯⨯=种方法．【讨论】如果染色步骤为----C A BD E,那么应该该如何解答？答案：也是4322296⨯⨯⨯⨯=种方法．如果染色步骤为----C AD B E那么应该如何解答？答案：染色的前两步一共有4×3种方法，但染第三步时需要分类讨论，如果D与A颜色相同，那么B有2种染法，E也有2种方法，如果D与A 染不同的颜色，那么D有2种染法那么B只有一种染法，E有2种染法，所以一共应该有43(122212)96⨯⨯⨯⨯+⨯⨯=种方法，(教师应该向学生说明第三个步骤用到了分类讨论和加法原理，加法原理在下一讲中将会讲授)，染色步骤选择的经验方法：每一步骤所染的区块应该尽量和之前所染的区块相邻．【答案】96【巩固】某沿海城市管辖7个县，这7个县的位置如右图．现用红、黑、绿、蓝、紫五种颜色给右图染色，要求任意相邻的两个县染不同颜色，共有多少种不同的染色方法?【考点】乘法原理之染色问题【难度】4星【题型】解答【解析】为了便于分析，把地图上的7个县分别编号为A、B、C、D、E、F、G(如左下图)．G F D CB AE 为了便于观察，在保持相邻关系不变的情况下可以把左图改画成右图．那么，为了完成地图染色这件工作需要多少步呢?由于有7个区域，我们不妨按A 、B 、C 、D 、E 、F 、G 的顺序，用红、黑、绿、蓝、紫五种颜色依次分7步来完成染色任务．第1步：先染区域A ，有5种颜色可供选择；第2步：再染区域B ，由于B 不能与A 同色，所以区域B 的染色方式有4种；第3步：染区域C ，由于C 不能与B 、A 同色，所以区域C 的染色方式有3种；第4步：染区域D ，由于D 不能与C 、A 同色，所以区域D 的染色方式有3种；第5步：染区域E ，由于E 不能与D 、A 同色，所以区域E 的染色方式有3种；第6步：染区域F ，由于F 不能与E 、A 同色，所以区域F 的染色方式有3种；第7步：染区域G ，由于G 不能与C 、D 同色，所以区域G 的染色方式有3种．根据分步计数的乘法原理，共有54333334860⨯⨯⨯⨯⨯⨯=种不同的染色方法．【答案】4860【例 6】 用3种颜色把一个33⨯的方格表染色，要求相同行和相同列的3个格所染的颜色互不相同，一共有 种不同的染色法．【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】 根据题意可知，染完后这个33⨯的方格表每一行和每一列都恰有3个颜色．用3种颜色染第一行，有336P =种染法；染完第一行后再染第一列剩下的2个方格，有2种染法；当第一行和第一列都染好后，再根据每一行和每一列都恰有3个颜色对剩下的方格进行染色，可知其余的方格都只有唯一一种染法．所以，根据乘法原理，共有326⨯=种不同的染法．【答案】6【例 7】 如右图，有A 、B 、C 、D 、E 五个区域，现用五种颜色给区域染色，染色要求：每相邻两个区域不同色，每个区域染一色．有多少种不同的染色方式？EDC BA 【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】 先采用分步：第一步给A 染色，有5种方法；第二步给B 染色，有4种方式；第三步给C 染色，有3种方式；第四步给D 染色，有3种方式；第五步，给E 染色，由于E 不能与A 、B 、D 同色，但可以和C 同色．此时就出现了问题：当D 与B 同色时，E 有3种颜色可染；而当D 与B 异色时，E 有2种颜色可染．所以必须从第四步就开始分类：第一类，D 与B 同色．E 有3种颜色可染，共有5433180⨯⨯⨯=（种）染色方式；第二类，D 与B 异色．D 有2种颜色可染，E 有2种颜色可染，共有54322240⨯⨯⨯⨯=（种）染色方式．根据加法原理，共有180240420+=（种）染色方式．【注意】给图形染色问题中有的可以直接用乘法原理解决，但如果碰到有首尾相接的图形往往需要分类解决．【答案】420【巩固】如右图，有A，B，C，D四个区域，现用四种颜色给区域染色，要求相邻区域的颜色不同，每个区域染一色．有多少种染色方法？ADBC【考点】乘法原理之染色问题【难度】3星【题型】解答【解析】A有4种颜色可选，然后分类：第一类：B，D取相同的颜色．有3种颜色可染，此时D也有3种颜色可选．根据乘法原理，不同的染法有43336⨯⨯=（种）；第二类：当B，D取不同的颜色时，B有3种颜色可染，C有2种颜色可染，此时D也有2种颜色可染．根据乘法原理，不同的染法有432248⨯⨯⨯=（种）．根据加法原理，共有364884+=(种)染色方法．【答案】84【巩固】用四种颜色对右图的五个字染色，要求相邻的区域的字染不同的颜色，但不是每种颜色都必须要用．问：共有多少种不同的染色方法?学而奥数思【考点】乘法原理之染色问题【难度】3星【题型】解答【解析】第一步给“而”上色，有4种选择；然后对“学”染色，“学”有3种颜色可选；当“奥”，“数”取相同的颜色时，有2种颜色可选，此时“思”也有2种颜色可选，不同的涂法有32212⨯⨯=种；当“奥”，“数”取不同的颜色时，“奥”有2种颜色可选，“数”剩仅1种颜色可选，此时“思”也只有1种颜色可选(与“学”相同)，不同的涂法有32116⨯⨯⨯=种．所以，根据加法原理，共有43(222)72⨯⨯⨯+=种不同的涂法．【答案】72【例8】分别用五种颜色中的某一种对下图的A，B，C，D，E，F六个区域染色，要求相邻的区域染不同的颜色，但不是每种颜色都必须要用．问：有多少种不同的染法？【考点】乘法原理之染色问题【题型】解答【解析】先按A，B，D，C，E的次序染色，可供选择的颜色依次有5，4，3，2，3种，注意E与D的颜色搭配有339⨯=(种)，其中有3种E和D同色，有6种E和D异色．最后染F，当E与D同色时有3种颜色可选，当E与D异色时有2种颜色可选，所以共有542(3362)840⨯⨯⨯⨯+⨯=种染法．【答案】840【例9】将图中的○分别涂成红色、黄色或绿色，要求有线段相连的两个相邻○涂不同的颜色，共有多少种不同涂法？D C BA【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】 如右上图，当A ，B ，C ，D 的颜色确定后，大正方形四个角上的○的颜色就确定了，所以只需求A ，B ，C ，D 有多少种不同涂法．按先A ，再B ，D ，后C 的顺序涂色．按---A B D C 的顺序涂颜色：A 有3种颜色可选；当B ，D 取相同的颜色时，有2种颜色可选，此时C 也有2种颜色可选，不同的涂法有32212⨯⨯=种； 当B ，D 取不同的颜色时，B 有2种颜色可选，D 仅剩1种颜色可选，此时C 也只有1种颜色可选(与A 相同)，不同的涂法有32116⨯⨯⨯=(种)．所以，根据加法原理，共有12618+=种不同的涂法．【答案】18【例 10】 用4种不同的颜色来涂正四面体（如图，每个面都是完全相同的正三角形）的4个面，使不同的面涂有不同的颜色，共有________种不同的涂法.（将正四面体任意旋转后仍然不同的涂色法，才被认为是不同的）【考点】乘法原理之染色问题 【难度】4星 【题型】填空【关键词】迎春杯，中年级，复赛，第9题【解析】 不旋转时共有4×3×2×1=24种染色方式，而一个正四面体有4×3=12种放置方法（4个面中选1个作底面，再从剩余3个面中选1个作正面），所以每种染色方式被重复计算了12次，则不同的染色方法有24÷12=2种。

第十一讲：染色与操作问题一、染色问题这里的染色问题不是要求如何染色，然后问有多少种染色方法的那类题目，它指的是一种解题方法.染色方法是一种将题目研究对象分类的形象化方法，通过将问题中的对象适当染色，我们可以更形象地观察分析出其中所蕴含的关系，再经过一定的逻辑推理，便能得出问题的答案.这类问题不需要太多的数学知识，但技巧性，逻辑性较强，要注意学会几种典型的染色问题.二、操作问题实际操作与策略问题这类题目能够很好的提高学生思考问题的能力，激发学生探索数学规律的兴趣，并通过寻找最佳策略过程，培养学生的创造性思维能力，这也是各类考试命题者青睐的这类题目的原因。

模块一、染色问题【例 1】六年级一班全班有35名同学，共分成5排，每排7人，坐在教室里，每个座位的前后左右四个位置都叫做它的邻座．如果要让这35名同学各人都恰好坐到他的邻座上去，能办到吗?为什么？【解析】划一个5×7的方格表，其中每一个方格表示一个座位．将方格黑白相间地染上颜色，这样黑色座位与白色座位都成了邻座．因此每位同学都坐到他的邻座相当于所有白格的坐到黑格，所有黑格的坐到白格．而实际图中有17个黑格18个白格，个数不等，故不能办到．【巩固】右图是某一湖泊的平面图，图中所有曲线都是湖岸.(1)如果P点在岸上，那么A点是在岸上还是在水中？(2)某人过此湖泊，他下水时脱鞋，上岸时穿鞋.如果他从A点出发走到某点B，他穿鞋与脱鞋的总次数是奇数，那么B点是在岸上还是在水中？为什么？（2）从水中经过一次陆地到水中，脱鞋与穿鞋的次数的和为2，由于A点在水中，所以不管怎么走，走在水中时，脱鞋、穿鞋的次数的和总是偶数.既然题中说“脱鞋的次数与穿鞋的次数的和是个奇数”，那么B点必定在岸上.【巩固】某班有45名同学按9行5列坐好．老师想让每位同学都坐到他的邻座(前后左右)上去，问这能否办到?【解析】将5×9长方形自然染色，发现黑格的邻座都是白格，白格的邻座都是黑格，因此每位同学都坐到他的邻座相当于所有白格的坐到黑格，所有黑格的坐到白格．而实际图中有23个黑格22个白格，个数不等，故不能办到．【例 2】右图是某一套房子的平面图，共12个房间，每相邻两房间都有门相通．请问：你能从某个房间出发，不重复地走完每个房间吗?【解析】如图所示，将房间黑白相间染色，发现只有5个白格，7个黑格．因为每次只能由黑到白或由白到黑，路线必然黑白相问，显然应该从多的白格开始．但路线上1白1黑1白1黑……直到5白5黑后还余2黑，不可能从黑格到黑格，故无法实现不重复走遍．【巩固】有一次车展共6×6=36个展室，如右图，每个展室与相邻的展室都有门相通，入口和出口如图所示．参观者能否从入口进去，不重复地参观完每个展室再从出口出来?【解析】如右下图，对每个展室黑白相间染色，同样每次只能黑格到白格或白格到黑格．入口和出口处都是白格，故路线黑白相间，首尾都是白格，于是应该白格比黑格多1个，而实际上白格、黑格都是18个，故不可能做到不重复走遍每个展室．【例 3】在一个正方形的果园里，种有63棵果树，加上右下角的一间小屋，整齐地排列成八行八列，如图（1）.守园人从小屋出发经过每一棵树，不重复也不遗漏(不许斜走)，最后又回到小屋，行吗？如果有80棵果树，如图（2），连小屋排成九行九列呢？【解析】下图(1)中可以回到小屋，守园人只能黑白相间地走，走到的第奇数棵树是白的，第偶数棵树是黑的，走到第63棵树应是白的，在小屋相邻的树都标注白色，所以可以回到小屋.图(2)不行,从小屋出发,当走到80棵树应是黑色, 而黑树与小木屋不相邻，无法直接回到小木屋.【例 4】右图是半张中国象棋盘，棋盘上已放有一只马. 众所周知，马是走“日”字的. 请问：这只马能否不重复地走遍这半张棋盘上的每一个点，然后回到出发点？【解析】马走“日”字，在中国象棋盘上走有什么规律呢？为方便研究规律，如下图所示，先在棋盘各交点处相间标上○和●，图中共有22个○和23个● . 因为马走“日”字，每步只能从○跳到●，或由●跳到○，所以马从某点跳到同色的点（指○或●），要跳偶数步；跳到不同色的点，要跳奇数步。

1. 如右图，对A,B,C,D,E五个区域分别用红黄绿蓝白五种颜色中的某一种来着色，规定相邻的区域着不同色，问有多少种不同的着色方案？【组合十讲P37】2 用红黄蓝三种颜色涂在右图的圆圈中，每个圆圈中，每个圆圈只涂一种颜色，并且要使每条连线两端的圆圈涂上不同颜色，问一共有多少种不同的涂法？3.某植物园计划在A,B,C,D,E五个地块栽种四种不同颜色的郁金香，每个地块内的郁金香必须同色，相邻的（有公共边界的）地块郁金香不能同色，不相邻可以同色，问共有多少种不同的方案？4.如图对A,B,C,D,E,F,G七个区域分别采用红，黄，绿，蓝，白五种颜色中的某一种来着色，规定相邻的区域不能同色，那么有多少种不同的着色方案？5.用红，黄，蓝，三种颜色把如图的8个小圆圈涂上颜色，每个圆圈只涂一种颜色，并且有连线的两个圆圈不能同色，那么有多少种不同涂色方案？【希望杯P107】6. 一根划分成相等5段的钢管，若要用红，白两种颜色分别对每一段着色，问共有几种不同的涂色方案？（倒置后相同的两种涂色方案视为同种）8. 如图用4种颜色对A,B,C,D,E五个区域涂色，要求相邻的区域涂不同的颜色，那么，共有几种涂法？9. 用三种颜色染正方体的6条边，相邻边不同色，有多少种染法？【教程P133】10. 如图，用红，黄，蓝三种颜色给一个五边形的各个顶点染色，同一边的两段点不能同色，且顶点A 必须染红色，请问：有多少种不同的染色方案？【高斯导引P76】11. 如图一个圆环被分成8部分，先将每一部分染上红，黄，蓝三种颜色之一，要求相邻两部分颜色不同，共有多少种不同染色方案？12. 如图，用4种不同的颜色将图中的圆圈分别涂色，要求有线段连接的两个相邻的圆圈必须涂不同的颜色，共有几种涂法？（不许旋转翻转）13 给一个正四面体的4个面染色，每个面只允许用一种颜色，且4个面的颜色互不相同，现有5种颜色可选，共有多少种不同的染色方案？14. 用4种颜色为一个正方体的6个面染色，要求每个面只能用1种颜色，且乡邻面的颜色必须不同，如果将正方体经过反转后颜色相同视为同一种，那么共有多少种不同的染色方案？17.用红，黄，蓝三种颜色对右图进行染色，要求相邻两块颜色不同，共有多少种不同的染色方案？【简明读本P191】1.某影院有31排,每排29个座位.某天放映了两场电影,每个座位上都坐了一个观众.如果要求每个观众在看第二场电影时必须跟他(前、后、左、右)相邻的某一观众交换座位,这样能办到吗?为什么?2.如图是一所房子的示意图,图中数字表示房间号码,每间房子都与隔壁的房间相通.问能否从1号房间开始,不重复的走遍所有房间又回到1号房间?1 2 34 5 67 8 93.63棵果树、加上右下角的一间小屋,整齐地排列成八行八列(见图 (a)).守园人从小屋出发经过每一棵树,不重复也不遗漏(不许斜走),最后又回到小屋,行吗?如果有80棵果树,连小屋在内排成九行九列(图(b))呢?(a) (b)4.一个8⨯8国际象棋(下图)去掉对角上两格后,是否可以用31个2⨯1的“骨牌” (形如 )把?。

竞赛讲座14-染色问题与染色方法1．小方格染色问题最简单的染色问题是从一种民间游戏中发展起来的方格盘上的染色问题.解决这类问题的方法后来又发展成为解决方格盘铺盖问题的重要技巧.例1 如图29-1(a),3行7列小方格每一个染上红色或蓝色.试证:存在一个矩形,它的四个角上的小方格颜色相同.证明由抽屉原则,第1行的7个小方格至少有4个不同色,不妨设为红色(带阴影)并在1、2、3、4列（如图29-1（b））.在第1、2、3、4列（以下不必再考虑第5，6，7列）中，如第2行或第3行出现两个红色小方格，则这个问题已经得证；如第2行和第3行每行最多只有一个红色小方格（如图29-1（c）），那么在这两行中必出现四角同为蓝色的矩形，问题也得到证明.说明：（1）在上面证明过程中除了运用抽屉原则外，还要用到一种思考问题的有效方法，就是逐步缩小所要讨论的对象的范围，把复杂问题逐步化为简单问题进行处理的方法.（2）此例的行和列都不能再减少了.显然只有两行的方格盘染两色后是不一定存在顶点同色的矩形的.下面我们举出一个3行6列染两色不存在顶点同色矩形的例子如图29-2.这说明3行7列是染两色存在顶点同色的矩形的最小方格盘了.至今,染k色而存在顶点同色的矩形的最小方格盘是什么还不得而知.例2 (第2届全国部分省市初中数学通讯赛题)证明:用15块大小是4×1的矩形瓷砖和1块大小是2×2的矩形瓷砖，不能恰好铺盖8×8矩形的地面.分析将8×8矩形地面的一半染上一种颜色，另一半染上另一种颜色，再用4×1和2×2的矩形瓷砖去盖，如果盖住的两种颜色的小矩形不是一样多，则说明在给定条件不完满铺盖不可能.证明如图29-3，用间隔为两格且与副对角线平行的斜格同色的染色方式，以黑白两种颜色将整个地面的方格染色.显然，地面上黑、白格各有32个.每块4×1的矩形砖不论是横放还是竖盖，且不论盖在何处，总是占据地面上的两个白格、两个黑格，故15块4×1的矩形砖铺盖后还剩两个黑格和两个白格.但由于与副对角线平行的斜格总是同色，而与主对角线平行的相邻格总是异色，所以，不论怎样放置，一块2×2的矩形砖，总是盖住三黑一白或一黑三白.这说明剩下的一块2×2矩形砖无论如何盖不住剩下的二黑二白的地面.从而问题得证.例3 （1986年北京初二数学竞赛题）如图29-4（1）是4个1×1的正方形组成的“L”形，用若干个这种“L”形硬纸片无重迭拼成一个m×n（长为m个单位，宽为n个单位）的矩形如图29-4（2）.试证明mn必是8的倍数.证明∵m×n矩形由“L”形拼成，∴m×n是4的倍数，∴m、n中必有一个是偶数，不妨设为m.把m×n矩形中的m列按一列黑、一列白间隔染色（如图29-4（2）），则不论“L”形在这矩形中的放置位置如何（“L”形的放置，共有8种可能），“L”形或占有3白一黑四个单位正方形（第一种），或占有3黑一白四个单位正方形（第二种）.设第一种“L”形共有p个，第二种“L”形共q个，则m×n矩形中的白格单位正方形数为3p+q，而它的黑格单位正方形数为p+3q.∵m为偶数，∴m×n矩形中黑、白条数相同，黑、白单位正方形总数也必相等.故有3p+q=p+3q，从而p=q.所以“L”形的总数为2p个，即“L”形总数为偶数，所以m×n一定是8的倍数.2．线段染色和点染色下面介绍两类重要的染色问题.(1) 线段染色.较常见的一类染色问题是发样子组合数学中图论知识的所谓“边染色”（或称“线段染色”），主要借助抽屉原则求解.例4 （1947年匈牙利数学奥林匹克试题）世界上任何六个人中，一定有3个人或者互相认识或者互相都不认识.我们不直接证明这个命题，而来看与之等价的下述命题例5（1953年美国普特南数学竞赛题）空间六点，任三点不共线，任四点不共面，成对地连接它们得十五条线段，用红色或蓝色染这些线段（一条线段只染一种颜色）.求证:无论怎样染,总存在同色三角形.证明设A、B、C、D、E、F是所给六点.考虑以A为端点的线段AB、AC、AD、AE、AF，由抽屉原则这五条线段中至少有三条颜色相同，不妨设就是AB、AC、AD，且它们都染成红色.再来看△BCD的三边，如其中有一条边例如BC是红色的，则同色三角形已出现（红色△ABC）；如△BCD三边都不是红色的，则它就是蓝色的三角形，同色三角形也现了.总之,不论在哪种情况下,都存在同色三角形.如果将例4中的六个人看成例5中六点,两人认识的连红线,不认识的连蓝线,则例4就变成了例5.例5的证明实际上用染色方法给出了例4的证明.例6 (第6届国际数学奥林匹克试题)有17位科学家,其中每一个人和其他所有人的人通信,他们的通信中只讨论三个题目.求证:至少有三个科学家相互之间讨论同一个题目.证明用平面上无三点共线的17个点A1,A2,…，A17分别表示17位科学家.设他们讨论的题目为x,y,z,两位科学家讨论x连红线,讨论y连蓝线,讨论z连黄线.于是只须证明以这17个点为顶点的三角形中有一同色三角形. 考虑以A1为端点的线段A1A2,A1A3,…，A1A17，由抽屉原则这16条线段中至少有6条同色，不妨设A1A2，A1A3，…，A1A7为红色.现考查连结六点A2，A3，…，A7的15条线段，如其中至少有一条红色线段，则同色（红色）三角形已出现；如没有红色线段，则这15条线段只有蓝色和黄色，由例5知一定存在以这15条线段中某三条为边的同色三角形（蓝色或黄色）.问题得证.上述三例同属图论中的接姆赛问题.在图论中,将n点中每两点都用线段相连所得的图形叫做n点完全图,记作k n.这些点叫做“顶点”，这些线段叫做“边”.现在我们分别用图论的语言来叙述例5、例6.定理1 若在k6中，任染红、蓝两色，则必有一只同色三角形.定理2 在k17中,任染红、蓝、黄三角，则必有一只同色三角形.（2）点染色.先看离散的有限个点的情况.例7 （首届全国中学生数学冬令营试题）能否把1，1，2，2，3，3，…，1986，1986这些数排成一行，使得两个1之间夹着一个数，两个2之间夹着两个数，…，两个1986、之间夹着一千九百八十六个数？请证明你的结论.证明将1986×2个位置按奇数位着白色，偶数位着黑色染色，于是黑白点各有1986个.现令一个偶数占据一个黑点和一个白色，同一个奇数要么都占黑点，要么都占白点.于是993个偶数，占据白点A1=993个，黑色B1=993个.993个奇数，占据白点A2=2a个，黑点B2=2b个，其中a+b=993.因此，共占白色A=A1+A2=993+2a个.黑点B=B1+B2=993+2b个，由于a+b=993（非偶数！）∴a≠b，从而得A≠B.这与黑、白点各有1986个矛盾.故这种排法不可能.“点”可以是有限个，也可以是无限个，这时染色问题总是与相应的几何问题联系在一起的.例8 对平面上一个点，任意染上红、蓝、黑三种颜色中的一种.证明:平面内存在端点同色的单位线段.证明作出一个如图29-7的几何图形是可能的,其中△ABD、△CBD、△AEF、△GEF都是边长为1的等边三角形，CG=1.不妨设A点是红色，如果B、E、D、F中有红色，问题显然得证.当B、E、D、F都为蓝点或黄点时，又如果B和D或E和F同色，问题也得证.现设B和D异色E和F异色,在这种情况下,如果C或G为黄色或蓝点,则CB、CD、GE、GF中有两条是端点同色的单位线段，问题也得证.不然的话,C、G均为红点，这时CG是端点同色的单位线段.证毕.还有一类较难的对区域染色的问题，就不作介绍了.练习二十九1．6×6的方格盘，能否用一块大小为3格，形如的弯角板与11块大小为3×1的矩形板，不重迭不遗漏地来铺满整个盘面.2．（第49届苏联基辅数学竞赛题）在两张1982×1983的方格纸涂上红、黑两种颜色，使得每一行及每一列都有偶数个方格是黑色的.如果将这两张纸重迭时，有一个黑格与一个红格重合，证明至少还有三个方格与不同颜色的方格重合.3．有九名数学家，每人至多会讲三种语言，每三名中至少有2名能通话，那么其中必有3名能用同一种语言通话.4．如果把上题中的条件9名改为8名数学家，那么，这个结论还成立吗？为什么？5．设n=6（r-2）+3（r≥3），求证：如果有n名科学家，每人至多会讲3种语言，每3名中至少有2名能通话，那么其中必有r名能用同一种语言通话.6．（1966年波兰数学竞赛题）大厅中会聚了100个客人，他们中每人至少认识67人，证明在这些客人中一定可以找到4人，他们之中任何两人都彼此相识.7．（首届全国数学冬令营试题）用任意方式给平面上的每一个点染上黑色或白色.求证：一定存在一个边长为1或的正三角形，它三个顶点是同色的.练习二十九１．将１、４行染红色、２、５行染黄色、３、６行染蓝色，然后就弯角板盖住板面的不同情况分类讨论．２．设第一张纸上的黑格Ａ与第二张纸上的红格Ａ′重合．如果在第一张纸上Ａ所在的列中，其余的黑格（奇数个）均与第二张纸的黑格重合，那么由第二张纸上这一列的黑格个数为偶数，知必有一黑格与第一张纸上的红格重合，即在这一列，第一张纸上有一方格Ｂ与第二张纸上不同颜色的方格Ｂ′重合．同理在Ａ、Ｂ所在行上各有一个方格Ｃ、Ｄ，第二张纸上与它们重合的方格Ｃ′、Ｄ′的颜色分别与Ｃ、Ｄ不同．３．把９名数学家用点Ａ１，Ａ２，…，Ａ９表示．两人能通话，就用线连结，并涂某种颜色，以表示不同语种。

小学奥数--乘法原理之染色法-精选练习例题-含答案解析(附知识点拨及考点)------------------------------------------作者xxxx------------------------------------------日期xxxx7-2-3乘法原理之染色问题教学目标1。

使学生掌握乘法原理主要内容，掌握乘法原理运用的方法;２。

使学生分清楚什么时候用乘法原理，分清有几个必要的步骤,以及各步之间的关系．3。

培养学生准确分解步骤的解题能力;乘法原理的数学思想主旨在于分步考虑问题,本讲的目的也是为了培养学生分步考虑问题的习惯.知识要点一、乘法原理概念引入老师周六要去给同学们上课，首先得从家出发到长宁上8点的课,然后得赶到黄埔去上下午1点半的课．如果说申老师的家到长宁有５种可选择的交通工具(公交、地铁、出租车、自行车、步行）,然后再从长宁到黄埔有２种可选择的交通工具（公交、地铁)，同学们,你们说老师从家到黄埔一共有多少条路线?我们看上面这个示意图，老师必须先的到长宁,然后再到黄埔．这几个环节是必不可少的，老师是一定要先到长宁上完课,才能去黄埔的．在没学乘法原理之前,我们可以通过一条一条的数,把线路找出来，显而易见一共是10条路线．但是要是老师从家到长宁有２5种可选择的交通工具,并且从长宁到黄埔也有３0种可选择的交通工具,那一共有多少条线路呢？这样数,恐怕是要耗费很多的时间了.这个时候我们的乘法原理就派上上用场了．二、乘法原理的定义完成一件事，这个事情可以分成n个必不可少的步骤(比如说老师从家到黄埔，必须要先到长宁，那么一共可以分成两个必不可少的步骤,一是从家到长宁，二是从长宁到黄埔)，第1步有A种不同的方法,第二步有B种不同的方法，……,第n 步有N 种不同的方法.那么完成这件事情一共有A ×B ×……×N 种不同的方法．结合上个例子,老师要完成从家到黄埔的这么一件事,需要2个步骤,第１步是从家到长宁，一共５种选择；第２步从长宁到黄埔，一共2种选择；那么老师从家到黄埔一共有5×2个可选择的路线了，即10条．三、乘法原理解题三部曲1、完成一件事分N 个必要步骤；2、每步找种数(每步的情况都不能单独完成该件事）；3、步步相乘四、乘法原理的考题类型1、路线种类问题-—比如说老师举的这个例子就是个路线种类问题；2、字的染色问题--比如说要３个字,然后有５种颜色可以给每个字然后，问3个字有多少种染色方法;3、地图的染色问题——同学们可以回家看地图,比如中国每个省的染色情况，给你几种颜色，问你一张包括几个部分的地图有几种染色的方法；４、排队问题——比如说６个同学,排成一个队伍，有多少种排法；5、数码问题——就是对一些数字的排列,比如说给你几个数字，然后排个几为数的偶数,有多少种排法.【例 1】 地图上有A ,B ，C ,D 四个国家（如下图）,现有红、黄、蓝三种颜色给地图染色,使相邻国家的颜色不同,但不是每种颜色都必须要用，问有多少种染色方法?DC B A【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】 A 有3种颜色可选;当B ,C 取相同的颜色时，有2种颜色可选,此时D 也有2种颜色可选．根据乘法原理,不同的涂法有32212⨯⨯=种;当B ，C 取不同的颜色时，Ｂ有2种颜色可选,Ｃ仅剩1种颜色可选,此时D 也只有1种颜色可选(与Ａ相同)．根据乘法原理,不同的涂法有32116⨯⨯⨯=种．综上，根据加法原理,共有12618+=种不同的涂法.例题精讲【答案】18【巩固】 如果有红、黄、蓝、绿四种颜色给例题中的地图染色,使相邻国家的颜色不同，但不是每种颜色都必须要用,问有多少种染色方法?【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】 第一步，首先对Ａ进行染色一共有４种方法,然后对B 、Ｃ进行染色，如果B 、Ｃ取相同的颜色，有三种方式,D 剩下3种方式,如果B 、C 取不同颜色，有326⨯=种方法，D 剩下2种方法,对该图的染色方法一共有43332284⨯⨯+⨯⨯=（）种方法.【注意】给地图染色问题中有的可以直接用乘法原理解决,有的需要分类解决，前者分类做也可以解决问题.【答案】84【例 2】 在右图的每个区域内涂上A 、B 、C 、D 四种颜色之一，使得每个圆里面恰有四种颜色，则一共有__＿__＿____种不同的染色方法.7654321【考点】乘法原理之染色问题 【难度】4星 【题型】解答【解析】 因为每个圆内4个区域上染的颜色都不相同，所以一个圆内的4个区域一共有43224⨯⨯=种染色方法.如右图所示，当一个圆内的1、2、3、4四个区域的颜色染定后,由于6号区域的颜色不能与2、3、4三个区域的颜色相同，所以只能与1号区域的颜色相同,同理5号区域只能与4号区域的颜色相同,7号区域只能与2号区域的颜色相同,所以当1、2、3、4四个区域的颜色染定后，其他区域的颜色也就相应的只有一种染法，所以一共有24种不同的染法．【答案】24【例 3】 如图，地图上有A ，B ,C ，D 四个国家,现用五种颜色给地图染色,要使相邻国家的颜色不相同，有多少种不同染色方法?DCB A【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】 为了按要求给地图上的这四个国家染色,我们可以分四步来完成染色的工作:第一步：给A 染色,有5种颜色可选．第二步:给B 染色，由于B 不能与A 同色，所以B 有4种颜色可选．第三步：给C 染色,由于C 不能与A 、B 同色,所以C 有3种颜色可选.第四步：给D 染色,由于D 不能与B 、C 同色,但可以与A 同色,所以D 有3种颜色可选.根据分步计数的乘法原理,用5种颜色给地图染色共有5433180⨯⨯⨯=种不同的染色方法.【答案】180【巩固】 如图,一张地图上有五个国家A ，B ,C ，D ，E ,现在要求用四种不同的颜色区分不同国家，要求相邻的国家不能使用同一种颜色,不同的国家可以使用同-种颜色，那么这幅地图有多少着色方法?ED C BA【考点】乘法原理之染色问题 【难度】3星 【题型】解答【解析】 第一步，给A 国上色，可以任选颜色，有四种选择；第二步,给B 国上色，B 国不能使用A 国的颜色,有三种选择；第三步,给C 国上色，C 国与B ,A 两国相邻，所以不能使用A ，B 国的颜色,只有两种选择;第四步,给D 国上色，D 国与B ，C 两国相邻，因此也只有两种选择； 第五步,给E 国上色,E 国与C ,D 两国相邻,有两种选择. 共有4322296⨯⨯⨯⨯=种着色方法.【答案】96【例 4】 如图:将一张纸作如下操作，一、用横线将纸划为相等的两块,二、用竖线将下边的区块划为相等的两块，三、用横线将最右下方的区块分为相等的两块,四、用竖线将最右下方的区块划为相等的两块……，如此进行8步操作,问:如果用四种颜色对这一图形进行染色,要求相邻区块颜色不同,应该有多少种不同的染色方法？【考点】乘法原理之染色问题【难度】３星【题型】解答【解析】对这张纸的操作一共进行了８次，每次操作都增加了一个区块，所以8次操作后一共有９个区块，我们对这张纸，进行染色就需要9个步骤,从最大的区块从大到小开始染色，每个步骤地染色方法有：４、3、2、２、2……,所以一共有:4322222221536⨯⨯⨯⨯⨯⨯⨯⨯=种．【答案】1536【巩固】用三种颜色去涂如图所示的三块区域,要求相邻的区域涂不同的颜色,那么共有几种不同的涂法?ABC【考点】乘法原理之染色问题【难度】2星【题型】解答【解析】涂三块毫无疑问是分成三步．第一步，涂A部分,那么就有三种颜色的选择;第二步,涂B部分,由于要求相邻的区域涂不同的颜色,A和B相邻，当A确定了一种颜色后，Ｂ只有两种颜色可选择了；第三步,涂C部分，C和A、B都相邻，A和B确定了两种不相同的颜色,那么C只有一种颜色可选择了.然后再根据乘法原理．3216⨯⨯=【答案】6【例 5】如图,有一张地图上有五个国家，现在要用四种颜色对这一幅地图进行染色,使相邻的国家所染的颜色不同，不相邻的国家的颜色可以相同．那么一共可以有多少种染色方法？【考点】乘法原理之染色问题【难度】３星【题型】解答【解析】这一道题实际上就是例题,因为两幅图各个字母所代表的国家的相邻国家是相同的,如果将本题中的地图边界进行直角化就会转化为原题,所以对这幅地图染色同样一共有4322296⨯⨯⨯⨯=种方法.【讨论】如果染色步骤为----C A BD E，那么应该该如何解答?答案：也是4322296⨯⨯⨯⨯=种方法.如果染色步骤为----C AD B E那么应该如何解答？答案:染色的前两步一共有４×３种方法，但染第三步时需要分类讨论,如果D与A颜色相同，那么B有2种染法,E也有2种方法,如果D与A染不同的颜色，那么D有２种染法那么B只有一种染法，E有2种染法，所以一共应该有43(122212)96⨯⨯⨯⨯+⨯⨯=种方法,（教师应该向学生说明第三个步骤用到了分类讨论和加法原理，加法原理在下一讲中将会讲授），染色步骤选择的经验方法：每一步骤所染的区块应该尽量和之前所染的区块相邻．【答案】96【巩固】某沿海城市管辖７个县，这7个县的位置如右图．现用红、黑、绿、蓝、紫五种颜色给右图染色,要求任意相邻的两个县染不同颜色,共有多少种不同的染色方法？【考点】乘法原理之染色问题【难度】4星【题型】解答【解析】为了便于分析，把地图上的7个县分别编号为A、B、C、D、E、F、G (如左下图).GF DC B AE为了便于观察,在保持相邻关系不变的情况下可以把左图改画成右图.那么,为了完成地图染色这件工作需要多少步呢?由于有7个区域，我们不妨按A、B、C、D、E、F、G的顺序，用红、黑、绿、蓝、紫五种颜色依次分7步来完成染色任务．第1步：先染区域A,有5种颜色可供选择;第2步：再染区域B,由于B不能与A同色,所以区域B的染色方式有４种；第3步:染区域C,由于C不能与B、A同色,所以区域C的染色方式有３种；第４步:染区域D，由于D不能与C、A同色，所以区域D的染色方式有3种;第5步：染区域E,由于E不能与D、A同色,所以区域E的染色方式有３种;第6步：染区域F，由于F不能与E、A同色,所以区域F的染色方式有3种;第７步：染区域G ，由于G 不能与C 、D 同色,所以区域G 的染色方式有3种.根据分步计数的乘法原理，共有54333334860⨯⨯⨯⨯⨯⨯=种不同的染色方法．【答案】4860【例 6】用3种颜色把一个33⨯的方格表染色,要求相同行和相同列的3个格所染的颜色互不相同，一共有 种不同的染色法.【考点】乘法原理之染色问题 【难度】３星 【题型】解答【解析】 根据题意可知,染完后这个33⨯的方格表每一行和每一列都恰有３个颜色．用3种颜色染第一行,有336P =种染法；染完第一行后再染第一列剩下的2个方格，有２种染法；当第一行和第一列都染好后,再根据每一行和每一列都恰有3个颜色对剩下的方格进行染色，可知其余的方格都只有唯一一种染法．所以,根据乘法原理,共有326⨯=种不同的染法.【答案】6【例 7】 如右图,有A 、Ｂ、C 、D 、Ｅ五个区域,现用五种颜色给区域染色,染色要求:每相邻两个区域不同色,每个区域染一色．有多少种不同的染色方式?ED C BA【考点】乘法原理之染色问题 【难度】３星 【题型】解答【解析】 先采用分步:第一步给A 染色，有5种方法;第二步给B 染色,有4种方式；第三步给C 染色，有3种方式;第四步给D 染色,有3种方式；第五步，给Ｅ染色，由于Ｅ不能与Ａ、B 、D 同色，但可以和C 同色．此时就出现了问题：当Ｄ与B 同色时,E 有３种颜色可染；而当D 与B 异色时，E 有2种颜色可染.所以必须从第四步就开始分类：第一类,D 与B 同色．E 有3种颜色可染，共有5433180⨯⨯⨯=(种)染色方式;第二类,Ｄ与B 异色.D 有２种颜色可染，E 有２种颜色可染，共有54322240⨯⨯⨯⨯=（种)染色方式.根据加法原理,共有180240420+=（种）染色方式．【注意】给图形染色问题中有的可以直接用乘法原理解决,但如果碰到有首尾相接的图形往往需要分类解决.【答案】420【巩固】 如右图,有Ａ，B ，C ，D 四个区域,现用四种颜色给区域染色,要求相邻区域的颜色不同，每个区域染一色．有多少种染色方法？DACB【考点】乘法原理之染色问题【难度】3星【题型】解答【解析】A有4种颜色可选，然后分类:第一类：B，D取相同的颜色.有3种颜色可染，此时D也有3种颜色可选．根据乘法原理，不同的染法有43336⨯⨯=(种）；第二类：当B,D取不同的颜色时,B有3种颜色可染，C有2种颜色可染，此时D也有２种颜色可染．根据乘法原理,不同的染法有⨯⨯⨯=(种).432248根据加法原理,共有364884+=(种）染色方法．【答案】84【巩固】用四种颜色对右图的五个字染色,要求相邻的区域的字染不同的颜色,但不是每种颜色都必须要用.问:共有多少种不同的染色方法?学而奥数思【考点】乘法原理之染色问题【难度】3星【题型】解答【解析】第一步给“而"上色,有4种选择；然后对“学”染色，“学”有3种颜色可选;当“奥”，“数”取相同的颜色时,有2种颜色可选，此时“思＂也有２种颜色可选,不同的涂法有32212⨯⨯=种;当“奥”,“数”取不同的颜色时,“奥”有2种颜色可选，“数”剩仅1种颜色可选,此时“思＂也只有１种颜色可选（与“学”相同),不同的涂法有32116⨯⨯⨯=种.所以，根据加法原理,共有43(222)72⨯⨯⨯+=种不同的涂法.【答案】72【例 8】分别用五种颜色中的某一种对下图的A,B，C,D,E，F六个区域染色,要求相邻的区域染不同的颜色,但不是每种颜色都必须要用.问:有多少种不同的染法?【考点】乘法原理之染色问题【难度】4星【题型】解答【解析】先按A，B,D,C，E的次序染色,可供选择的颜色依次有５,4，3，２，３种,注意E与D的颜色搭配有339⨯=（种)，其中有3种E和D同色,有6种E 和D异色．最后染F，当E与D同色时有3种颜色可选,当E与D异色时有2种颜色可选,所以共有542(3362)840⨯⨯⨯⨯+⨯=种染法．【答案】840【例 9】将图中的○分别涂成红色、黄色或绿色，要求有线段相连的两个相邻○涂不同的颜色,共有多少种不同涂法？D CBA【考点】乘法原理之染色问题【难度】３星【题型】解答【解析】如右上图，当A，B,C，D的颜色确定后,大正方形四个角上的○的颜色就确定了，所以只需求A，B，C,D有多少种不同涂法.按先A，再B,D，后C的顺序涂色.按---A B D C的顺序涂颜色:A有3种颜色可选;当B，D取相同的颜色时，有2种颜色可选,此时C也有2种颜色可选,不同的涂法有32212⨯⨯=种；当B，D取不同的颜色时，B有2种颜色可选，D仅剩1种颜色可选，此时C也只有1种颜色可选(与A相同），不同的涂法有32116⨯⨯⨯=（种）．所以,根据加法原理,共有12618+=种不同的涂法．【答案】18【例 10】用4种不同的颜色来涂正四面体(如图,每个面都是完全相同的正三角形)的4个面,使不同的面涂有不同的颜色，共有_____＿__种不同的涂法。