初中奥数竞赛培优专题讲座：专题二十七 染色问题（PDF版）

十七、染色问颋 十七、染色问题 [竞赛要点] 我们把要求作出或者证明存在满足某种染色性质的点列、格点、直线、四边形区域 和图形等问题叫做染色问题.把用染色作为一种数学工具去分析问题、解决问题的思维 方法叫做染色方法 [方法述要] 染色问题是一类与抽屉原理和图论知识联系在一起的数学问题根据染色的对象 (点、线段或区域)不同,我们把它分为点染色线段染色和区域染色三类不论是哪类染 色问题,它们大都围绕同色点或同色三角形展开分析讨论 染色方法处理数学问题的思维模式为;通过对点线或区域进行合理的染色建立数 原问题的染色模型,然后对染色模型进行研究,获得原问题的解 [赛题精析] 例1证明:在任何6个人中,总有3个人相互认识或者互不认识 学竞赛培优教程 证法1用点v1,v2,…,v6表示6个人.如果2个人相识,则相应的两点之间连 条红边否则就连一条蓝边由此得到双色完全图K6,要证明的结论转化为双色完全专 题 图K6中必有1个同色三角形,这是显然的,事实上,从v1引出的5条边只添有2种颜讲 色其中总有3条边是同色的,不妨设v1v2,v1v3,v1v4都是红边,现在考虑三角形座 v2v3v4,若其中至少有1条红边,例如v273,则v1v2v3就是红色的三角形,否则 v2v304就是蓝色的三角形.总之,K6中必有同色的三角形 证法2设A是6个人中的1个,假定A和3个人互相认识.如果这3个人中有 B、C相互认识,那么A,B,C这3个人便满足条件,如果和A认识的3个火彼此都不 认识,那么这3个人也满足条件 现在假设A认识的人数少于3人,那么有3个人不认识A,如果他们之中有B、C 彼此不认识,那么A,B,C满足条件.如果和A不相识的3个人中,任意2个人彼此相 识,那么这3人也满足条件 例2某班有49名学生,坐成七行七列,每个座位的前后左右均称为它的邻座,要 使全班每个同学都离开自己的位子坐到邻座上去,问这种方案能否实现? 十七、染色问华 解把七行七列的座位转化成7×7的方格表,每个格子代 表一个座位,然后对此7×7方格表的第一格染上白色和蓝色之 满足相邻两格不同色,如图27-1,则所谓每个人离开自己的 座位坐到邻座上去,即要从白格进入蓝格或从蓝格进人白格,而 实际上图中的白格为25格,蓝格为24格,所以白格的人不可能 都进入蓝格,也就是原方案是不可能实现的 例3某班有22名同学,男女各占一半