2011年中招考试：《初中数学》竞赛讲座(14)

　　2. 线段染色和点染色

　　下面介绍两类重要的染色问题.

　　(1) 线段染色.较常见的一类染色问题是发样子组合数学中图论知识的所谓“边染色”(或称“线段染色”)，主要借助抽屉原则求解.

　　例4 (1947年匈牙利数学奥林匹克试题)世界上任何六个人中，一定有3个人或者互相认识或者互相都不认识.

　　我们不直接证明这个命题，而来看与之等价的下述命题

　　例5 (1953年美国普特南数学竞赛题)空间六点，任三点不共线，任四点不共面，成对地连接它们得十五条线段，用红色或蓝色染这些线段(一条线段只染一种颜色).求证:无论怎样染,总存在同色三角形.

　　证明 设A、B、C、D、E、F是所给六点.考虑以A为端点的线段AB、AC、AD、AE、AF，由抽屉原则这五条线段中至少有三条颜色相同，不妨设就是AB、AC、AD，且它们都染成红色.再来看△BCD的三边，如其中有一条边例如BC是红色的，则同色三角形已出现(红色△ABC);如△BCD三边都不是红色的，则它就是蓝色的三角形，同色三角形也现了.总之,不论在哪种情况下,都存在同色三角形.

　　如果将例4中的六个人看成例5中六点,两人认识的连红线,不认识的连蓝线,则例4就变成了例5.例5的证明实际上用染色方法给出了例4的证明.

　　例6 (第6届国际数学奥林匹克试题)有17位科学家,其中每一个人和其他所有人的人通信,他们的通信中只讨论三个题目.求证:至少有三个科学家相互之间讨论同一个题目.

　　证明 用平面上无三点共线的17个点A1,A2,…，A17分别表示17位科学家.设他们讨论的题目为x,y,z,两位科学家讨论x连红线,讨论y连蓝线,讨论z连黄线.于是只须证明以这17个点为顶点的三角形中有一同色三角形.

　　考虑以A1为端点的线段A1A2,A1A3,…，A1A17，由抽屉原则这16条线段中至少有6条同色，不妨设A1A2，A1A3，…，A1A7为红色.现考查连结六点A2，A3，…，A7的15条线段，如其中至少有一条红色线段，则同色(红色)三角形已出现;如没有红色线段，则这15条线段只有蓝色和黄色，由例5知一定存在以这15条线段中某三条为边的同色三角形(蓝色或黄色).问题得证.

　　上述三例同属图论中的接姆赛问题.在图论中,将n点中每两点都用线段相连所得的图形叫做n点完全图,记作kn.这些点叫做“顶点”，这些线段叫做“边”.现在我们分别用图论的语言来叙述例5、例6.

　　定理1 若在k6中，任染红、蓝两色，则必有一只同色三角形.

　　定理2 在k17中,任染红、蓝、黄三角，则必有一只同色三角形.

　　(2)点染色.先看离散的有限个点的情况.

　　例7 (首届全国中学生数学冬令营试题)能否把1，1，2，2，3，3，…，1986，1986这些数排成一行，使得两个1之间夹着一个数，两个2之间夹着两个数，…，两个1986、之间夹着一千九百八十六个数?请证明你的结论.

　　证明 将1986×2个位置按奇数位着白色，偶数位着黑色染色，于是黑白点各有1986个.

　　现令一个偶数占据一个黑点和一个白色，同一个奇数要么都占黑点，要么都占白点.于是993个偶数，占据白点A1=993个，黑色B1=993个.

　　993个奇数，占据白点A2=2a个，黑点B2=2b个，其中a+b=993.

　　因此，共占白色A=A1+A2=993+2a个.

　　黑点B=B1+B2=993+2b个，

　　由于a+b=993(非偶数!)∴a≠b，从而得A≠B.这与黑、白点各有1986个矛盾.

　　故这种排法不可能.

　　“点”可以是有限个，也可以是无限个，这时染色问题总是与相应的几何问题联系在一起的.

　　例8 对平面上一个点，任意染上红、蓝、黑三种颜色中的一种.证明:平面内存在端点同色的单位线段.

　　证明 作出一个如图29-7的几何图形是可能的,其中△ABD、△CBD、△AEF、△GEF都是边长为1的等边三角形，CG=1.不妨设A点是红色，如果B、E、D、F中有红色，问题显然得证.当B、E、D、F都为蓝点或黄点时，又如果B和D或E和F同色，问题也得证.现设B和D异色E和F异色,在这种情况下,如果C或G为黄色或蓝点,则CB、CD、GE、GF中有两条是端点同色的单位线段，问题也得证.不然的话,C、G均为红点，这时CG是端点同色的单位线段.证毕.

　　还有一类较难的对区域染色的问题，就不作介绍了.

　　2011年中考数学备考辅导：选择题精选汇总

　　名师解读南京2011年中考数学命题趋势