教学随笔 谈染色法解题的几种类型.doc

《教学随笔 谈染色法解题的几种类型.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、教学随笔浅谈染色法解题的几种类型春晖中学钟建新先看下面的一道竞赛题和它的证法。弗明斯克城的每一条道路均连接着两个十字路口，且都限定为单向行车线。市政当局为布列加油站网点开展了一次设计竞赛，要求自每一个十字路口均可不违反行车规则地到达加油站之一，但由任何一个加油站都不可以抵达另外任何一个加油站。证明：在所有应征的设计方案中，全都布列了相同数目的加油站。（列宁格勒数学奥林匹克试题1998年）证明：任取两个设计方案，将其中一方案中的加油站网点染上红色，将另一方案中的加油站网点染上蓝色。由题设知：在任一十字路口，必可到达两种设计方案中相应的加油

2、站。设由某个“蓝色”加油站B可抵达某两个“红色”加油站A和C，即由某一“红色”加油站A，可抵达某“蓝色”加油站B，反之，由B又可抵达某个“红色”加油站C，故由“红色”加油站A，可抵达“红色”加油站C，由题意知，这只有在A与C重合时才有可能。即由某个“蓝色”加油站，只能到达某一个“红色”加油站。同理可证：由某一个“红色”加油站也只能抵达某一个“蓝色”加油站。由上可知，“红色”加油站与“蓝色”加油站间可以一一搭配成对，每一对中的两个加油站可以互相抵达，故“红色”加油站与“蓝色”加油站数目相等。在这道竞赛题的证明中，我们借助了一种解题思想方法

3、——染色法。那么，什么是染色法呢？所谓染色法，即是指根据问题的情境，把问题中的对象适当地染上若干种颜色，从而把问题转化为熟悉的或易于解决的问题这样一种解题思想方法。用染色法解题，其关键是根据问题的特点，选取适当的对象进行染色，这里染色的范围很广泛，例如可以对点染色，对边染色，也可对区域染色。下面就关于用染色法解题的几种类型和大家作一探讨。类型一：对点染色MXAPRCZQYB例1设ΔABC是等边三角形，S是其三边AB、BC、CA上所有点（包括A，B，C）的集合，若把集合S任意分成两个不相交的子集，其中是否至少有一个子集中含有某直角三角形的

4、三个顶点？证明你的结论。（1983IMO24-4）分析：若把集合S中的点染成红、蓝两色，则本题可转述为：一定存在一个顶点颜色全相同的直角三角形。证明：如右图，在AB、BC、CA上分别取点P、Q、R，使BP=2PA，CQ=2QB，AR=2RC，则PQ⊥BC，QR⊥AC，RP⊥AB。现将S中的点染成红、蓝二色，则P、Q、R中至少有两点同色，不妨设Q、R为红色。若AC边上除R外还有红点X，则ΔQRX组成红色顶点的直角三角形，现设AC上除R外均为蓝色，这时：如果AB边上除A外还有蓝点Y，则作YM⊥AC于M，有AMAC

5、为蓝色顶点的直角三角形；如果AB边上除A点外全为红点，则作QZ⊥AB于Z，得ΔQZB为红色顶点直角三角形。综上所述，顶点同色的直角三角形一定存在。类型二：对边染色例2有17位科学家，其中每一个人和其他所有的人通信。他们的通信中只讨论三个题目。求证：至少有三个科学家相互之间讨论同一个题目。（1964第6届IMO）分析：此题我们可以把每一个科学家抽象为一个点，把两位科学家讨论一个题目的这种关系抽象为两点间连接的一条线段。根据科学家讨论题目的不同，采用不同种颜色对这些线段进行染色。证明：用平面上无三点共线的17个点，，…，分别表示17位科学家

6、，接着17点间两两连线。两位科学家若讨论第一个题目，则把对应两点间连线染上红色；若讨论第二个题目，则把对应两点间连线染上黄色；若讨论第三个题目，则把对应两点间连线染上蓝色，于是只需证明以这17个点为顶点的三角形中存在同色三角形。考虑以为端点的线段，，…，。由抽屉原理可知，在这16条线段中至少有6条同色，不妨设，，…，这6条都为红色，现考察连接，，，…，的15条线段：若其中至少有一条红色线段（如），则同色三角形已出现（红色Δ）；若没有红色线段，则这15条线段中只有黄色和蓝色，故也一定存在同色三角形（黄色或蓝色三角形），综上所述，至少有三个

7、科学家相互之间讨论同一个题目。类型三：对区域染色例3某班有49个座位，排成一个7行7列的正方形，假使开始时每个座位都坐着一位学生，问是否可能改变学生的座位，使得每个学生换到紧靠他原座位的前面、后面、左面或右面的座位上去？分析：区域染色的对象主要是一些平面区域，如方格、三角形等。此题若能对每个学生座位所在区域进行染色，就有利于问题的解决。解：把7行7列的座位转化为7×7的方格表，每个格子代表一个座位，然后对此7×7的方格表的每一格染上白色和蓝色之一，染色时要满足相邻的两格是不同的颜色（如上表）。则所谓每个人离开自己的座位坐到邻座上去即要从

8、白格进入蓝格或从蓝格进入白格。而实际上图中的白格为25格而蓝格为24格，所以，白格中的人不可能都进入蓝格，也就是说不可能使全班每个同学都离开自己的位子坐到邻座上去。