《竞赛研究专题染色问题研究》由会员分享，可在线阅读，更多相关《竞赛研究专题染色问题研究（2页珍藏版）》请在金锄头文库上搜索。
1、山东 王峰 2011 年 1 月 26 日 1染色问题研究 1 基本问题 先看两个例子。 例 1 证明任意六个人中，总有三个人相互认识，或者相互不认识。 例 2 空间六个点，任三点不共线，任四点不共面，两两连线且用红蓝两色去染这 些线段（一条线段只染一色） 。求证：无论如何染，恒存在同色的三角形。 由此可引出几个思考题。 思考题 1. 若例 2 中改为五个点，结论还成立吗？ 思考题 2. 若恒存在四点两两连线皆同色，那么点数需要增加到多少呢？ 思考题 3. 若改用三种颜色来染，为了仍要恒存在同色三角形，点数需要增加到多少 呢？ 为了回答思考题 2，需要先解决下一例题。 例 3 空间九个点两两连
2、线，用红蓝两色染边，证明：必存在红色三角形或存在四 点两两连线皆蓝色。 下面的例 4 例 5，又将例 2 引申了一步。 例 4：例 2 中的同色三角形至少有几个？ 例 5 空间七个点两两连线，二染色其边，则恒存在两个无公共边的同色三角形。 例 6 在直角坐标平面里，取 区域 ，用红蓝两色 7 3 7 1 , 3 1 | ) , ( y x y x D 去染 D 上（包括边界）的整点，每点染且只染一色。证明：不论如何染色，区域 D 上 总含有这样的矩形，它的顶点为同色整点，边平行于坐标轴。 思考题 4 若区域改为 ，是否还恒存在单色矩形？ 6 3 思考题 5 不恒存在单色矩形的最大矩形区域是什么
3、？ 2 染色问题中的构造法 在染色问题中，常用构造法探索问题的结论，也常用构造法证明问题的结论。下面 介绍在染色问题中常用的两种构造法。 1构造特例 例 1 空间八个点两两连线二染色共边，证明：必存在三条无公共端点的同色线段。 例 2 用三种颜去染平面上所有的点，每点一色。证明：不论如何染色，总存在两 个距离为 1 的同色点。 例 3 用红蓝两色染平面上的点，证明：一定存在三个同色点，它们是边长为 1 或 的等边三角形的顶点。 3 例 4 回答1 中的思考题 5，并证明结论。 2构造模型山东 王峰 2011 年 1 月 26 日 2 例 5 空间六条直线，其中每三条直线都不共面。证明必存在三条
4、直线，满足下列 条件之一：（1）两两异面；（2）互相平行；（3）交于同一点。 3 数学竞赛中的染色问题 上两节已讲了有关染色的基本问题及一般解决染色问题的构造法，其中有些例题是 数学竞赛中曾经出现过的。在这一节中，我们再介绍一些历年各类数学竞赛中出现过的 题目，解决这类问题，一般先要建立一个染色模型。 例 1 有 17 位科学家，其中每一人和其他所有人通信，他们通信中只讨论三个题目， 且每两个科学家之间只讨论一个题目。求证：至少有三个科学家相互之间讨论同一个题 目（国际数学竞赛题） 。 思考题 1 若将科学家个数改成 16，结论如何？ 思考题 2 若有 65 位科学家，每两位之间讨论一个题目，
5、共讨论四个题目，是否还 恒存在三个科学家相互讨论同一个题目？ 例 2 设 S 是等边三角形 ABC 的三条边 上所有点（包括顶点 CA BC AB , , A，B ，C ）的集合，对于把 S 分成两个不相重叠的子集的每一种分法，是否总能在分得 的两个子集中至少找到一个子集，它含有某个直角三角形的三个顶点？证明你的结论 （国际数学竞赛题） 。 思考题 3 若将此例中“等边三角形 ABC”改为“直角三角形 ABC” ，结论如何？ 思考题 4 若将“等边三角形 ABC”改为“锐角三角形 ABC”或“钝角三角形 ABC” ，则结论如何？ 例 3 平面上六点，任何三点都是一个不等腰三角形的顶点，求证这些
6、三角形中有 一个的最短边同时是另一三角形的最大边（波兰数学竞赛题） 。 例 4 平面直角坐标系中，设计一方面将所有整点染白、红、黑中一色，使 （1）每色出现在无穷多条平行于横轴的直线上； （2）对任意白点 A 、红点 B 和黑点 C，总可找到一红色点 D，使 ABCD 为一平行 四边形 思考题 5 如果将条件（2）改为“对任意白点 A、红点 B 及 D ，总可找到黑点 C ，使 ABCD 为一平 行四边形” ，那么与原题有什么不同呢？分析中的染 法还适用吗？ 例 5 九名数学家在一次国际数学会议上相遇， 他们当中任何三个人中至少有二人能讲同一种语言， 而且每人最多能讲三种语言。试证明：至少有三个数 学家能讲同一种语言（美国数学竞赛试题） 例 6 在 的棋盘上，马从某一格出发，证 n 4 明：不可能走遍全棋盘回到出发点，且每格经过一次。 x y D C A B
