竞赛研究专题染色问题研究.doc

染色问题研究
§1 基本问题
先看两个例子。
例1 证明任意六个人中,总有三个人相互认识,或者相互不认识。
例2 空间六个点,任三点不共线,任四点不共面,两两连线且用红蓝两色去染这些线段(一条线段只染一色)。求证:无论如何染,恒存在同色的三角形。
由此可引出几个思考题。
思考题1. 若例2中改为五个点,结论还成立吗?
思考题2. 若恒存在四点两两连线皆同色,那么点数需要增加到多少呢?
思考题3. 若改用三种颜色来染,为了仍要恒存在同色三角形,点数需要增加到多少呢?
为了回答思考题2,需要先解决下一例题。
例3 空间九个点两两连线,用红蓝两色染边,证明:必存在红色三角形或存在四点两两连线皆蓝色。
下面的例4例5,又将例2引申了一步。
例4:例2中的同色三角形至少有几个?
例5 空间七个点两两连线,二染色其边,则恒存在两个无公共边的同色三角形。
例6 在直角坐标平面里,取区域,用红蓝两色去染D上(包括边界)的整点,每点染且只染一色。证明:不论如何染色,区域D上总含有这样的矩形,它的顶点为同色整点,边平行于坐标轴。
思考题4 若区域改为,是否还恒存在单色矩形?
思考题5 不恒存在单色矩形的最大矩形区域是什么?
§2 染色问题中的构造法
在染色问题中,常用构造法探索问题的结论,也常用构造法证明问题的结论。下面介绍在染色问题中常用的两种构造法。

例1 空间八个点两两连线二染色共边,证明:必存在三条无公共端点的同色线段。
例2 用三种颜去染平面上所有的点,每点一色。证明:不论如何染色,总存在两个距离为1的同色点。
例3 用红蓝两色染平面上的点,证明:一定存在三个同色点,它们是边长为1或的等边三角形的顶点。
例4 回答§1中的思考题5,并证明结论。

例5 空间六条直线,其中每三条直线都不共面。证明必存在三条直线,满足下列条件之一:(1)两两异面;(2)互相平行;(3)交于同一点。
§3 数学竞赛中的染色问题
上两节已讲了有关染色的基本问题及一般解决染色问题的构造法,其中有些例题是数学竞赛中曾经出现过的。在这一节中,我们再介绍一些历年各类数学竞赛中出现过的题目,解决这类问题,一般先要建立一个染色模型。
例1 有17位科学家,其中每一人和其他所有人通信,他们通信中只讨论三个题目,且每两个科学家之间只讨论一个题目。求证:至少有三个科学家相互之间讨论同一个题目(国际数学竞赛题)。
思考题1 若将科学家个数改成16,结论如何?
思考题2 若有65位科学家,每两位之间讨论一个题目,共讨论四个题目,是否还恒存在三个科学家相互讨论同一个题目?
例2 设S是等边三角形ABC的三条边上所有点(包括顶点A,B,C)的集合,对于把S分成两个不相重叠的子集的每一种分法,是否总能在分得的两个子集中至少找到一个子集,它含有某个直角三角形的三个顶点?证明你的