棋盘染色问题-网上

《棋盘染色问题-网上》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、学科：奥数教学内容：第7讲  简单染色问题 知识网络数学竞赛中的“染色”一般包括两个方面：染色问题和染色方法。如果染色作为题目的条件给出，那么一般要考虑的是存在与否，有何性质以及有多少种染法等，这就是染色问题。如果题目中没有提到染色，在解题中运用形象、直观的染色来进行分类，帮助解决问题这就是染色方法。 重点·难点我们在前面几讲中也涉及到染色问题。一般来说，染色问题涉及分类、奇偶性、排列组合等多方面的知识。因此如何应用这些相关的知识点解题，是很关键的。在下面的例题中也可以看出，这些知识在解题中的应用

2、。 学法指导染色作为一种数学思维方法，可以用来推证说理，使一些难以讲清楚的问题一目了然。有时染色题可能很难想清楚，比如“四色问题”，但可以运用上面的知识点解决一些比较简单的染色问题。 经典例题[例1]如图1所示，一个长方形被分成6块区域，若给每一块区域都染色，并且要求相邻的区域颜色不同，请问至少需要多少种不同的颜色？ 思路剖析由于A、B、C两两相邻，所以要使相邻的区域颜色不同，至少A、B、C的颜色不能相同。但是，仅有3种颜色够不够呢？对于区域较少的情形可以逐一试验，如果区域较多时，可以考虑取有多相

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]用红、黄、蓝三种颜色涂一个正方体的六个面，两个面涂一种颜色，那么共有几种

4、涂法？ 思路剖析本题要用到分类和组合的一些思想，同进，在解题时要注意，如果两种所谓不同涂法的正方体经翻转或旋转之后得到同样的效果，它只能是一种涂法。所以，我们可以取定一种颜色，就它所涂的两个面相对或相邻来分类。 解答我们将染红的两个面分为相对和相邻的两种情形来考虑：（1）红色的两面相对，不妨设上面和下面是红色的，那么由于黄色的两面可以相对也可以相邻，并且一旦黄色的面确定后蓝色的面也随即确定。因此，这种情形有两种涂法。（2）红色的两面相邻，不妨设后面和下面是红色的，则黄色可相对为一种，蓝色可相对也为

5、一种。若黄色的面相邻，可以有左面和上面两面的这一种（图2b），也可以有左面与前面两面的这一种（图2c），这两种是否可以经过翻转而重合呢？不行的。我们可将图2b的红色两面调换位置，使后面成为底面，底面成为后面，则图2b的黄色分别位于前面和右面，和图2c是不一样的，所以它们是两种不同的涂法。综上所述，符合题意的染色法共有6种。[例3]有一个7×7的棋盘，每一个小方格中有一只小甲虫，假定在同一时刻，所有的小甲虫都爬到相邻的格子中（横向或纵向的格，不能斜爬），问此时能否出现空格？ 思路剖析初看题，似乎无从

6、下手，但是我们可以利用“染色”的手段，使问题得到简化。我们用的手段同前面所讲的奇偶性很类似。 解答将7×7棋盘用黑白两种颜色相间染色，如图3所法，此时，共有黑格25个，白格24个。因此，当每个小格中的甲虫同时爬向邻格时，即黑格中的甲虫爬到白格中，白格中的甲虫爬到黑格中，由于黑格比白格多一格，则原来白格中的甲虫爬到黑格后必定至少有一个黑格是空的。所以此时肯定会出现空格。[例4]对世界上任何六个人来说，其中至少有三个人，他们要么互相认识，要么互相都不认识，请说明其中的理由。 思路剖析将这个问题换一种叙

7、述方式：在纸上画出六个点，表示六个人，如果两个人互相认识，就在代表这两个人的两点间连一条红色直线；如果两个人互相认识，就在代表两个人的两点间连一条蓝色直线。这样，六个点中的任意两点之间总能连一条直线，要么红线要么蓝线。因此问题就转化为，以A、B、C、D、E、F这六个顶点中，必然存在一个三角形，它的三条边颜色是一样的。 解答在六点中任取其中一点A，如图4所示，它与其他五点有五条连线，每一条连线要么红要么蓝，而根据抽屉原理，其中至少有三条线颜色相同，不妨设AC、AD和AE是在条蓝色的连线。而CD、CE

8、和DE三条连线中，只要有一点蓝色的，就会有一个三边都是蓝色的三角形出现。这说明有三个人互相都不认识。而如果CD、CE和DE三条连线均不是蓝色的，那么三角形CDE三边颜色都是红色，这说明有三个人互相都认识。[例5]如图5所示，将圆分成4个互不相同的扇形，每个扇形用红、黄、蓝三种颜色中一种颜色染色，要求相邻扇形所染的颜色不同，请问共有多少种染色方法？ 思路剖析我们将四个扇形分别用表示。在一般情形下，有三种染法，有两种，有两种，而要根据和的颜色是否相同来确定。 解答当染红色时，列表如下。