第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就是一条奥运线段，然后不管中间插入的点是什么颜色的，都会破坏原来的奥运线段从而变成一条两端同色一条奥运线段，再然后如果在一条奥运线段中间插入任意颜色的点，奥运线段会被破坏，但是又会生成一条较短的，那么奥运线段的数量总数不变；如果在一条两端同色的线段中间插入不同色的点，一下就增加2条奥运线段，不改变奥运线段数量的奇偶性。如果插入的点和两端同色，则奥运线段数量不改变；综上所述奥运线段一开始是1条为奇数，后面不管怎样插入点要么奥运线段数量不变要么增加2条，都不改变奥运线段条数的奇偶性，所以奥运线段的条数最后还是奇数。

例5、1、能否用一个田字和15个4 1矩形覆盖8 8棋盘?

解：把棋盘进行如图这样的超级染色，田字一定有1白3黑或者3白1黑，直条一定有2白2黑，一个田字和15个直条，应该共有31个白格33个黑格或者33个白格31个黑格，而棋盘中黑白格数一样多，所以办不到。

【课后分层练习】

A组：入门级

1、某影院有31排,每排29个座位.某天放映了两场电影,每个座位上都坐了一个观众.如果要求每个观众在看第二场电影时必须跟他(前、后、左、右)相邻的某一观众交换座位,这样能办到吗?为什么?

解：把各座位黑白相间涂色，要实现题意要求，一个白色位置必须和一个黑色位置互换，黑白座位应该一样多才行，而座位总数是31×29一定是个奇数，不可能黑白座位一样多，所以办不到。

2、在一个正方形的果园里,种有63棵果树、加上右下角的一间小屋,整齐地排列成八行八列.守园人从小屋出发经过每一棵树,不重复也不遗漏(不许斜走),最后又回到小屋,行吗?

解：如右图所示黑白相间染色，小屋也当做“白树”，每一棵“黑树”旁边一定是“白树”，反之亦然，那么“黑树”一定走到“白树”，“白树”一定走到“黑树”，从“白树”走奇数步一定是到“黑树”，走偶数步一定是到“白树”，要不重复的走遍每一棵树回到小屋，共要走64步，应该走到“白树”所以可以办到。如图所示即为一种走法。

3、展览会有36个展室(如图),每两相邻展室之间均有门相通.能不能从入口

进去,不重复地参观完全部展室后,从出口出来呢?

解：不能.对展室进行染色,使相邻两房间分别是黑色和白色的.此时入口处展室的颜色与出口处展室的颜色是相同的,而不重复参观完36个展室,入口与出口展室的颜色应该不相同.

4、棋牌活动室有一种怪异飞行棋棋盘，如图5，想用6个这样的小长方形覆盖，行吗？为什么？9个行吗？

图5 图6—1 图6—2

6个不行，9个行

5、如图6—1和6—2，哪个怪异飞行棋棋盘能用9个小长方形覆盖？

6-1不行 ，6-2行

B组：进阶级

1、下图是由4个小方格组成的“L”形硬纸片,用若干个这种纸片无重叠地拼成一个4 n的长方形,试证明:n一定是偶数.

解：如图,对4 n长方形的各列分别染上黑色和白色.任一L形纸片所占的方格只有两类:第一类占3黑1白,第二类占3白1黑.

设第一类有a个,第二类有b个,因为涂有两种颜色的方格数相等,故有3b+a=3a+b,即a=b,也就是说第一类与第二类相等,因此各种颜色的方格数都是4的倍数,总数是8的倍数,从而n是偶然.

2、能否用1个田字和15个T字纸片,拼成一个8 8的正方形棋盘?

解：将棋盘里黑白相间涂色.一个田字形盖住2个白格,一个T字形盖住3个或1个白格.故1个田字和15个T字盖住的白格数是一个奇数,但棋盘上的白格数是一个偶数.因此一个田字形和15个T字形不能盖住8 8的棋盘.

C组：挑战级

1、如图,把正方体分割成27个相等的小正方体,在中心的那个小正方体中有一只甲虫,甲虫能从每个小正方体走到与这个正方体相邻的6个小正方体中的任一个中去.如果要求甲虫能走到每个小正方体一次,那么甲虫能走遍所有的正方体吗?

解：我们将大正方体如图分割成27个小正方体,涂上黑白相间的两种颜色,使得中心的小正方体染成白色,再使两个相邻的小正方体染上不同的颜色.显然在27个小正文体中,14个是黑的,13个是白的.甲虫从中间的白色正方体出发,每走一步,小正方体就改变一种颜色.故它走27步,应该经过14个白色的小正方体,13个黑色的小正方体.所以办不到。

2、把三行七列的21个小格组成的矩形染色,每个小格染上红、蓝两种色中的一种.求证:总可以找到4个同色小方格,处于某个矩形的4个角上(如图)

解：在第一行的7格中必有4格同色,不妨设这4格位于前4个位置,且均为红色.然后考虑前4列构成的3 4矩形.若第二行和第3行中出现2个或2个以上的红色格子.则该行的两个红色格子与第一行的红色格子就组成一个4角同为红色格子的矩形.若不然,则第2、3行中都至少有3个蓝格在前4列中,不妨设第2行前3格为蓝色,显然第三行中的前3格中至少有2个蓝格，故在二、三行的前4列中必存在四角都是蓝色的矩形.

小学奥数 - 染色问题（答案）