染色问题的求解方法

染色问题的求解方法某伞厂所生产的伞品种齐全，其中品牌为〃太阳伞〃的伞的伞蓬都由太阳光的七种颜色组成，这七种颜色分别涂在伞蓬的八个区域内，且恰有一种颜色涂在相对的区域内，则不同颜色图案的此类太阳伞至多有（）种（A）40320（B）5040一、区域染色问题

（C）20160（D）2520答案：B对区域的染色问题一般是（1）直接根据两个基本原理求解；（2）根据所用的颜色的种数分类；（3）根据某两个区域同色或不同色分类；（4）根据相间区域使用的种类分类。用四种颜色给四川、青海、西藏、云南四省（区）的地图染色，每一省（区）一种颜色，只要求相邻的省（区）不同色，则不同的染色方法有多少种？分析：给四川染色有4种方法，给青海染色有3种方法，给西藏染色有2种方法，给云南染色有2种方法，根据分步计数原理共有4x3x2x2=48种方法。点评：本例是直接利用两个基本原理来解决。（2003全国）16.如图，一个地区分为5个行政区域，现给地图着色，要求相邻区域不得使用同一颜色，现有4种颜色可供选择，则不同的着色方法共有种。（以数字作答）答案：72解法一:合并单元格法分析：颜色相同的区域可能是②④，③⑤。下面分情况讨论：（i）当②④颜色相同且③⑤颜色不同时，

将②④合并成一个单元格，此时不同的着色方法相当于四个元素②④、①、③、⑤的全排列数A4。4（ii）当②④颜色不同且③⑤颜色相同时同情形（i）有A4种着色方法。4（iii）当②④及③⑤分别同色时，分别将②④及③⑤合并，这样仅有三个单元格，即②④、③⑤、①，从4种颜色中选3种来着色这三个单元格，即有C3A3种方法。43由分类计数原理知，不同的着色方法共有2A4+C3A3=48+24=72（种）。解法二：由题意可知至少要选三种颜色，依着色的种数分类：（i）当选用三种颜色时，区域②与④必须同色，区域③与⑤必须同色，故有A3种。4（ii）当用四种颜色时，若区域仅②与④同色有A：种，若区域仅③与⑤同色有A4种，故用四种颜色时共有2A4种。444由分类计数原理知，不同的着色方法共有2A4+C3A3=48+24=72（种）。解法三：依某两个不相邻的区域同色与不同色分类4：43（i）当区域②与④同色时，区域①有4种着色方法，区域②有3种着色方法，区域③有2种着色方法，区域④有1种着色方法，区域⑤有2种着色方法，故有4x3x2xlx2=48种。（ii）当区域②与④不同色时，区域&有4种着色方法，区域②有3种着色方法，区域③

有2种着色方法，区域④有1种着色方法，区域⑤有种着色方法，故有4x3x2xlxl=24种。综上可知，满足题意的着色方法共有48+24=72种。点评：解法一：合并单元格法；解法二：依使用颜色的种数进行分类；解法三：是根据某两个不相邻的区域是否同色进行讨论的。12345（2003新课程文）将3种作物种植在如图的5块试验田里，每块种植一种作物且相邻的试验田不能种植同一作物，不同的种植方法共有种。（以数字作答）答案：42分析：种植同种作物的试验田可能是：①③，①④，①⑤，②④，②⑤，③⑤，①③⑤。注意到：5=2+2+1或5=3+1+1，所以必有两对区域的颜色分别相同或有且仅有三个区域同色的不同搭配方式有：①③、②④、⑤，①③、②⑤、④，①④、②⑤、③，①④、③⑤、②，①⑤、②④、③，②④、③⑤、①，①③⑤、②、④。所以不同的种植方法共有7xA3=42（种）3点评：本例是先合并单元格，然后再重新组合涂色。（2003新课程）某城市在中心广场建造一个花圃，花圃分为6个部分（如图）。现要栽种4种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法有种。（以数字作答）答案：120分析：颜色相同的部分可能有：⑥③、⑥④、⑤②、⑤③、④②。经分析至少用四种颜色且不可能出现三个区域同色的情形，注意到6=2+2+1+1，所以必有两对区域同色，不同的搭配情形有：⑥③、⑤②、①、④；⑥③、④②、①、⑤；⑥④、⑤②、①、③；⑥④、⑤③、①、②；⑤③、④②、①、⑥。・.・共有5xA4=120种栽种方法。点评：本例也是先合并单元格，然后再重新组合涂色。用红、黄、蓝、白、黑5种颜色涂在“田”字形的4个小方格内，每格涂一种颜色，相邻的两格涂不同的颜色，如果颜色可以反复使用，共有多少种涂色方法？解析：如图，把问题分成三类：（i）四格涂不同的颜色，方法有A4种；5（ii）有且仅有两格涂相同的颜色，即一组对角小方格涂相同的颜色涂法种数为2C1A2；54（iii）两组对角小方格分别涂相同的颜色，涂法种数为A;。因此，所求得涂法种数为：A4+2C1A2+A2=260。'点评：本例是根据某两个不相邻的区域是否同色进行讨论的。如图一个正六边形的6个区域①②③④⑤⑥，现给这六个区域着色，要求同一区域染同一种颜色，相邻的两个区域不得使用同一种颜色，现有4种颜色可供选择，则有多少种不同的着色方法？解：（i）当相间区域①③⑤着同一颜色时，有4种着色方法，此时②④⑥各有三种着色方法，故有4x3x3x3=108种方法。（ii）当相间区域①③⑤着两种不同的颜色时，有C2A2种着色方法，34此时，②④⑥有3x2x2种着色方法，故有C2A2x3x2x2=432种方法。34（i）当相间区域①③⑤着三种颜色时，有A3种着色方法，此时的②④⑥各有2种着色方法，故有A3x2x2x2=192种方法。4综上共有108+432+192=732种方法。点评：本题是根据相间区域使用的颜色的种类来讨论的。

二、对点染色的问题对点染色问题，要注意对各点依次染色。主要方法有：(1)根据共用了多少种颜色的分类讨论法；(2)根据相对顶点是否同色分类讨论法。将一个四棱锥S—ABCD的每个顶点染上一种颜色，并使同一条棱上的两个端点不同色，如果只有5种颜色可供使用，那么不同的染色方法的总数是多少？解法一：满足条件的染色至少要用3种颜色。若恰用三种颜色，可先从5种颜色中任选一种染顶点S，再从余下的4种颜色中任选2种染A、B、C、D四点，此时只能A与C、B与D分别同色，故有CiC2C1=60种方法。542若恰用四种颜色染色，可以先从5种颜色中任选一种染顶点S，再从余下的四种颜色中任选2种染A与B，由于A、B颜色可以交换，故有A2种染色方法；再从余下的2种颜色中任选1种染D或C，而D与4C中另一个只需染与其相对顶点同色即可，故有。5人：。2。2=240种方法。(iii)若恰用5种颜色染色，有A5=120种方法：225综上所知，满足题意的染色方法数为60+240+120=420种。解法二：设想染色按S—A—B—C—D的顺序进行，对S、A、B染色，有5x4x3=60种染色方法。由于C点的颜色可能与A点同色或不同色，这影响到D点的颜色的选取方法数，故分类讨论：C与A同色时(此时C对颜色的选取方法唯一)，D应与A(C)、S不同色，有3种选择；C与A不同色时，C有2种选择的颜色，D也有2种颜色可供选择，从而对C、D染色有1x3+2x2=7种染色方法。根据分步计数原理。染色方法种数共有60x7=420种。点评：本题同以下两个题目本质相同：用5种颜色给图中的5个车站候车牌(A、B、C、D、E)染色，要求相邻的两个车站间的候车牌颜色不同，有多少种不同的染色方法？如图为一张有5个行政区划分的地图，今要用5种颜色给地图着色要求相邻的区域不同色(B与E，C与D不算相邻区域)，有多少种方案？三、对线段的染色问题对线段的染色问题，要注意对各条线段依次染色，主要方法有：根据共用了多少种颜色的分类讨论；根据相对的线段是否同色分类讨论。用红、黄、蓝、白4种颜色染矩形ABCD的四条边，每一条边只染一种颜色，且使相邻两边染不同的颜色。如果颜色可以反复使用，共有多少种不同的染色方法。解法一：(i)使用四种颜色有A4种；4(ii)使用三种颜色染色，则必须将一组对边染成同色，故有C1C1A2种；423(i)使用两种颜色时，则必须两组对边分别同色，故有A2种。4因此所求的染色方法数为：A4+C1C1A2+A2=84种。解法二：设想染色按AB—BC—cD—Da的顺序进行，对AB、BC染色有4x3=12种方法。由于CD的颜色可能与AB相同，这影响着DA的颜色的选取方法，故分类讨论：当CD与AB同色时，这时CD对颜色的选取方法唯一，则DA有3种颜色可供选择；当CD与AB不同色时，CD有2种可供选择的颜色，DA也有2种可供选择的颜色，从而对CD、DA的染色有1x3+2x2=7种染色方法。由分步计数原理，总的染色方法种数为12x7=84种。反思：以下题目与本题类似：中央电视台“正大综艺”节目的现场观众来自四个单位，分别在图中的4个区域内坐定。有4种不同颜色的服装，每个区域的观众必须穿同种颜色的服/\装且相邻两个区域的颜色不相同，不相邻的区域的颜色相同与否不受限制，那Nn\么不同的着色方法共有多少种？—Q—用6种颜色给正四面体A—BCD的每条棱染色，要求每条棱只染一种颜色且共\mW顶点的棱染不同的颜色，问有多少种不同的染色方法。分析：正四面体有三组对棱AB与CD，AC与BD，AD与BC。满足条件的染色至少要用3种颜色。解：（i）若恰用3种颜色，则每组对棱必须染同一种颜色，而这三组对棱间的颜色不同，故有A3种方法；6（ii）若恰用4种颜色，则三组对棱中有两组对棱同色但组与组间不同色，故有C2A4种方36法；（iii）若恰用5种颜色，则三组对棱中有一组对棱同色，故有CiA5种方法；36（iv）若恰用6种颜色，则有A6种方法。6综上，符合条件的染色方法总数为A3+C2A4+CiA5+A6=4080种。四、对面染色问题636366从给定的6种不同颜色中选用若干种颜色，将一个正方体的6个面染色，每两个具有公共棱的面染成不同的颜色，则有不同的染色方案共有多少种？（注：我们对两个相同的正方体染色后，可以通过适当的翻转，使得两个正方体上、下、左、右、前、扁个面对应面的染色都相同，那么，我们就说这两个正方体的染色方案相同）。（1996年全国高中数学联赛题）。分析：显然，至少需要3种颜色。解：（i）恰用6种颜色。确定某种颜色（如红色）所染面为下底面（根据题注，对此处的两种不同的染色方案，这里“第一面”总是相同的）则上底面的染色可有5种选择，在上、下底面已染好后，再确定其余4种颜色的某一种所染面为左侧面，则余下的三面有A3种染3色方