竞赛培训专题2----染色问题与染色方法

《竞赛培训专题2----染色问题与染色方法》由会员分享，可在线阅读，更多相关《竞赛培训专题2----染色问题与染色方法（6页珍藏版）》请在金锄头文库上搜索。

1、- 1 -竞赛培训专题竞赛培训专题 2-2-染色问题与染色方法染色问题与染色方法1 1 小方格染色问题小方格染色问题最简单的染色问题是从一种民间游戏中发展起来的方格盘上的染色问题.解决这类问题 的方法后来又发展成为解决方格盘铺盖问题的重要技巧.例 1 如图 29-1(a),3 行 7 列小方格每一个染上红色或蓝色.试证:存在一个矩形,它的四 个角上的小方格颜色相同.证明 由抽屉原则,第 1 行的 7 个小方格至少有 4 个不同色,不妨设为红色(带阴影)并在 1、2、3、4 列（如图 29-1（b）.在第 1、2、3、4 列（以下不必再考虑第 5，6，7 列）中，如第 2 行或第 3 行出现两个

2、 红色小方格，则这个问题已经得证；如第 2 行和第 3 行每行最多只有一个红色小方格 （如图 29-1（c），那么在这两行中必出现四角同为蓝色的矩形，问题也得到证明.说明：（1）在上面证明过程中除了运用抽屉原则外，还要用到一种思考问题的有效方 法，就是逐步缩小所要讨论的对象的范围，把复杂问题逐步化为简单问题进行处理的方 法.（2）此例的行和列都不能再减少了.显然只 有两行的方格盘染两色后是不一定存在顶点 同色的矩形的.下面我们举出一个 3 行 6 列染 两色不存在顶点同色矩形的例子如图 29-2. 这说明 3 行 7 列是染两色存在顶点同色的矩 形的最小方格盘了.至今,染 k 色而存在顶点 同

3、色的矩形的最小方格盘是什么还不得而知.- 2 -例 2 (第 2 届全国部分省市初中数学通讯赛题)证明:用 15 块大小是 41 的矩形瓷砖和 1 块大小是 22 的矩形瓷砖，不能恰好铺盖 88 矩形的地面.分析 将 88 矩形地面的一半染上一种颜色，另一半染上另一种颜色，再用 41 和 22 的矩形瓷砖去盖，如果盖住的两种颜色的小矩形不是一样多，则说明在给定条件不 完满铺盖不可能.证明 如图 29-3，用间隔为两格且与副对角线平行的斜格同色的染色方式，以黑白两种 颜色将整个地面的方格染色.显然，地面上黑、白格各有 32 个.每块 41 的矩形砖不论是横放还是竖盖，且不论盖在何处，总是占据地面

4、上的两个白 格、两个黑格，故 15 块 41 的矩形砖铺盖后还剩两个黑格和两个白格.但由于与副对 角线平行的斜格总是同色，而与主对角线平行的相邻格总是异色，所以，不论怎样放置， 一块 22 的矩形砖，总是盖住三黑一白或一黑三白.这说明剩下的一块 22 矩形砖无 论如何盖不住剩下的二黑二白的地面.从而问题得证. 例 3 （1986 年北京初二数学竞赛题）如图 29-4（1）是 4 个 11 的正方形组成的“L” 形，用若干个这种“L”形硬纸片无重迭拼成一个 mn（长为 m 个单位，宽为 n 个单位）的矩形如图 29- 4（2）.试证明 mn 必是 8 的倍数.证明mn 矩形由“L”形拼成，mn

5、是 4 的倍数， m、n 中必有一个是偶数，不妨设为 m.把 mn 矩形中的 m 列按一列黑、一列白间隔染色（如图 29-4（2），则不 论“L”形在这矩形中的放置位置如何（“L”形的放置， 共有 8 种可能），“L”形或占有 3 白一黑四个单位正方形 （第一种），或占有 3 黑一白四个单位正方形（第二种）.设第一种“L”形共有 p 个，第二种“L”形共 q 个，则 mn 矩形中的白格单位正方形 数为 3p+q，而它的黑格单位正方形数为 p+3q.m 为偶数，mn 矩形中黑、白条数相同，黑、白单位正方形总数也必相等.故有 3p+q=p+3q，从而 p=q.所以“L”形的总数为 2p 个，即“L

6、”形总数为偶数，所以 mn 一定是 8 的倍数. 2 2 线段染色和点染色线段染色和点染色下面介绍两类重要的染色问题.- 3 -(1) 线段染色.较常见的一类染色问题是发样子组合数学中图论知识的所谓“边染色” （或称“线段染色”），主要借助抽屉原则求解.例 4 （1947 年匈牙利数学奥林匹克试题）世界上任何六个人中，一定有 3 个 人或者互相认识或者互相都不认识.我们不直接证明这个命题，而来看与之等价的下述命题例 5 （1953 年美国普特南数学竞赛题）空间六点，任三点不共线，任四点不共面，成 对地连接它们得十五条线段，用红色或蓝色染这些线段（一条线段只染一种颜色）.求 证:无论怎样染,总存

7、在同色三角形.证明 设 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 届国际

8、数学奥林匹克试题)有 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 条线段

9、，如其中至少有一条红色线段，则同色（红色）三角形已出 现；如没有红色线段，则这 15 条线段只有蓝色和黄色，由例 5 知一定存在以这 15 条线 段中某三条为边的同色三角形（蓝色或黄色）.问题得证.上述三例同属图论中的接姆赛问题.在图论中,将 n 点中每两点都用线段相连所得的图形 叫做 n 点完全图,记作 kn.这些点叫做“顶点”，这些线段叫做“边”.现在我们分别用 图论的语言来叙述例 5、例 6.- 4 -定理 1 若在 k6中，任染红、蓝两色，则必有一只同色三角形.定理 2 在 k17中,任染红、蓝、黄三角，则必有一只同色三角形.（2）点染色.先看离散的有限个点的情况.例 7 （首届全国中

10、学生数学冬令营试题）能否把 1，1，2，2，3，3，1986，1986 这些数排成一行，使得两个 1 之间夹着一个数，两个 2 之间夹着两个数，两个 1986、之间夹着一千九百八十六个数？请证明你的结论.证明 将 19862 个位置按奇数位着白色，偶数位着黑色染色，于是黑白点各有 1986 个.现令一个偶数占据一个黑点和一个白色，同一个奇数要么都占黑点，要么都占白点.于 是 993 个偶数，占据白点 A1=993 个，黑色 B1=993 个.993 个奇数，占据白点 A2=2a 个，黑点 B2=2b 个，其中 a+b=993.因此，共占白色 A=A1+A2=993+2a 个. 黑点 B=B1+

11、B2=993+2b 个，由于 a+b=993（非偶数！）ab，从而得 AB.这与黑、白点各有 1986 个矛盾.故这种排法不可能.“点”可以是有限个，也可以是无限个，这时染色问题总是与相应的几何问题联系在一 起的.例 8 对平面上一个点，任意染上红、蓝、黑三种颜色中 的一种.证明:平面内存在端点同色的单位线段.证明 作出一个如图 29-7 的几何图形是可能的,其中 ABD、CBD、AEF、GEF 都是边长为 1 的等边三角形， CG=1.不妨设 A 点是红色，如果 B、E、D、F 中有红色， 问题显然得证.当 B、E、D、F 都为蓝点或黄点时，又如- 5 -果 B 和 D 或 E 和 F 同色

12、，问题也得证.现设 B 和 D 异色 E 和 F 异色,在这种情况下,如果 C 或 G 为黄色或蓝点,则 CB、CD、GE、GF 中有两条是端点同色的单位线段，问题也得证. 不然的话,C、G 均为红点，这时 CG 是端点同色的单位线段.证毕.还有一类较难的对区域染色的问题，就不作介绍了.练习练习1 66 的方格盘，能否用一块大小为 3 格，形如的弯角板与 11 块大小为 31 的矩形板，不重迭不遗漏地来铺满整个盘面.2 （第 49 届苏联基辅数学竞赛题）在两张 19821983 的方格纸涂上红、黑两种颜 色，使得每一行及每一列都有偶数个方格是黑色的.如果将这两张纸重迭时，有一个黑 格与一个红格

13、重合，证明至少还有三个方格与不同颜色的方格重合.3 有九名数学家，每人至多会讲三种语言，每三名中至少有 2 名能通话，那么其中 必有 3 名能用同一种语言通话.4 如果把上题中的条件 9 名改为 8 名数学家，那么，这个结论还成立吗？为什么？5 设 n=6（r-2）+3（r3），求证：如果有 n 名科学家，每人至多会讲 3 种语言， 每 3 名中至少有 2 名能通话，那么其中必有 r 名能用同一种语言通话.6 （1966 年波兰数学竞赛题）大厅中会聚了 100 个客人，他们中每人至少认识 67 人， 证明在这些客人中一定可以找到 4 人，他们之中任何两人都彼此相识.7 （首届全国数学冬令营试题

14、）用任意方式给平面上的每一个点染上黑色或白色.求证：一定存在一个边长为 1 或的正三角形，它三个顶点是同色的.练习答案练习答案将、行染红色、行染黄色、行染蓝色，然后就弯角板盖住板面的 不同情况分类讨论设第一张纸上的黑格与第二张纸上的红格重合如果在第一张纸上所在的 列中，其余的黑格（奇数个）均与第二张纸的黑格重合，那么由第二张纸上这一列的黑 格个数为偶数，知必有一黑格与第一张纸上的红格重合，即在这一列，第一张纸上有一 方格与第二张纸上不同颜色的方格重合同理在、所在行上各有一个方格 、，第二张纸上与它们重合的方格、的颜色分别与、不同- 6 -把名数学家用点，表示两人能通话，就用线连结，并涂某种 颜

15、色，以表示不同语种。两人不通话，就不连线（）果任两点都有连线并涂有颜色，那么必有一点如，以其为一端点的条线段 中至少有两条同色，比如、可见，之间可用同一语言通 话如情况不发生，则至少有两点不连线，比如、由题设任三点必有一条 连线知，其余七点必与或有连线这时七条线中，必有四条是从某一点如引 出的而这四条线中又必有二条同色，则问题得证结论不成立，如图所示（图中每条线旁都有一个数 字，以表示不同语种）类似于第题证明用点、表示客人，红、蓝的连 线分别表示两人相识或不相识，因为由一个顶点引出的 蓝色的线段最多有条，所以其中至少有三点之间连红线这三个点（设为 、）引出的蓝色线段最多为条去掉所有这些蓝色的线段（连同每条 线段上的一个端点，），这样，在图中至少还剩下四个点，除 、外，设第四点为，这四个点 中，每一个点与其它的点都以红色 的线段相连，于是客人、彼 此两两相识先利用右图证明若平面上有两个异色的点 距离为，地么必定可以找到符合题意的三角形 再找长为端点异色的线段以（白色）为 圆心，为半径作圆如圆内皆白点，问题已 证否则圆内有一黑点，以为底作腰长为 的三角形，则至少与、中一点异色，这样的线段找到