tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

数学竞赛-染色问题与染色方法


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

例2 (第 2 届全国部分省市初中数学通讯赛题)证明:用 15 块大小 是 4×1 的矩形瓷砖和 1 块大小是 2×2 的矩形瓷砖, 不能恰好铺盖 8×8 矩形的地面. 分析 将 8×8 矩形地面的一半染上一种颜色,另一半染上另一种颜色,再用 4×1 和 2×2 的矩形瓷砖去盖,如果盖住的两种颜色的小矩形不是一样多,则说明在给定 条件不完满铺盖不可能. 证明 如图 29-3,用间隔为两格且与副对角线平行的斜格同色的染色方式,以黑 白两种颜色将整个地面的方格染色.显然,地面上黑、白格各有 32 个. 每块 4×1 的矩形砖不论是横放还是竖盖,且不论盖在何处,总是占据地面上的两个 白格、两个黑格,故 15 块 4×1 的矩形砖铺盖后还剩两个黑格和两个白格.但由于与 副对角线平行的斜格总是同色,而与主对角线平行的相邻格总是异色,所以,不论 怎样放置,一块 2×2 的矩形砖,总是盖住三黑一白或一黑三白.这说明剩下的一块 2×2 矩形砖无论如何盖不住剩下的二黑二白的地面.从而问题得证.

例3 (1986 年北京初二数学竞赛题)如图 29-4(1)是 4 个 1×1 的正方形组成的“L”形,用若干个这种“L”形硬纸片无重迭拼成一个 m×n(长为 m 个单位,宽为 n 个单位)的矩形如图 29-4(2).试证明 mn 必是 8 的倍数.

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

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 定理 2 若在 k6 中,任染红、蓝两色,则必有一只同色三角形. 在 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 是端点同色的单位线段.证毕. 还有一类较难的对区域染色的问题,就不作介绍了.

练习二十九

1.

6×6 的方格盘,能否用一块大小为 3 格,形如

的弯角板与 11

块大小为 3×1 的矩形板,不重迭不遗漏地来铺满整个盘面. 2. (第 49 届苏联基辅数学竞赛题)在两张 1982×1983 的方格纸涂上红、黑两 种颜色,使得每一行及每一列都有偶数个方格是黑色的.如果将这两张纸重迭时,有 一个黑格与一个红格重合,证明至少还有三个方格与不同颜色的方格重合. 3. 有九名数学家,每人至多会讲三种语言,每三名中至少有 2 名能通话,那么 其中必有 3 名能用同一种语言通话. 4. 如果把上题中的条件 9 名改为 8 名数学家,那么,这个结论还成立吗?为什 么? 5. 设 n=6(r-2)+3(r≥3),求证:如果有 n 名科学家,每人至多会讲 3 种语 言, 每 3 名中至少有 2 名能通话, 那么其中必有 r 名能用同一种语言通话. 6. (1966 年波兰数学竞赛题)大厅中会聚了 100 个客人,他们中每人至少认识 67 人,证明在这些客人中一定可以找到 4 人,他们之中任何两人都彼此相识. 7. (首届全国数学冬令营试题)用任意方式给平面上的每一个点染上黑色或白 的正三角形,它三个顶点是同色的.

色.求证:一定存在一个边长为 1 或

练习二十九

1.将1、4行染红色、2、5行染黄色、3、6行染蓝色,然后就弯角板盖住板 面的不同情况分类讨论. 2.设第一张纸上的黑格A与第二张纸上的红格A′重合.如果在第一张纸上A所 在的列中,其余的黑格(奇数个)均与第二张纸的黑格重合,那么由第二张纸上这 一列的黑格个数为偶数,知必有一黑格与第一张纸上的红格重合,即在这一列,第 一张纸上有一方格B与第二张纸上不同颜色的方格B′重合.同理在A、B所在行 上各有一个方格C、D,第二张纸上与它们重合的方格C′、D′的颜色分别与C、 D不同. 3.把9名数学家用点A1,A2,…,A9表示.两人能通话,就用线连结,并涂某 种颜色,以表示不同语种。两人不通话,就不连线. (1)果任两点都有连线并涂有颜色,那么必有一点如A1,以其为一端点的8条线 段中至少有两条同色,比如A1A2、A1A3.可见A1,A2,A3之间可用同一语 言通话.②如情况①不发生,则至少有两点不连线,比如A1、A2.由题设任三点 必有一条连线知,其余七点必与A1或A2有连线.这时七条线中,必有四条是从某 一点如A1引出的.而这四条线中又必有二条同色,则问题得证. 4.结论不成立,如图所示(图中每条线旁都有一个数字,以表示不同语种).

5.类似于第3题证明. 6.用点A1、A2、…、A100表示客人,红、蓝的连线分别表示两人相识或不相识, 因为由一个顶点引出的蓝色的线段最多有32条,所以其中至少有三点之间连红 线.这三个点(设为A1、A2、A3)引出的蓝色线段最多为96条.去掉所有这些 蓝色的线段(连同每条线段上的一个端点AI,I≠1,2,3),这样,在图中至 少还剩下四个点,除A1、A2、A3外,设第四点为A4,这四个点中A1,A2,A 3每一个点与其它的点都以红色的线段相连,于是客人A1、A2、A3、A4彼此两两 相识. 7.先利用右图证明"若平面上有两个异色的点距离为2,地么必定可以找到符合 题意的三角形".再找长为2端点异色的线段.以O(白色)为圆心,4为半径作 圆.如圆内皆白点,问题已证.否则圆内有一黑点P,以OP为底作腰长为2的三 角形OPR,则R至少与O、P中一点异色,这样的线段找到.


推荐相关:

高中数学竞赛 染色问题与染色方法

第二专题 染色问题与染色方法一、区域染色 例 1、有一个 3× 7 的棋盘,用黑色或白色两种颜色去染棋盘上的方 格,每个方格只染一种颜色。证明:无论怎样染色,...


第25讲 染色问题与染色方法

第25讲 染色问题与染色方法_学科竞赛_初中教育_教育专区。让我们为全力打造甘肃名校—甘肃省华亭县皇甫学校而共同努力吧! 第 25 讲 染色问题与染色方法数学家像画...


初中数学染色问题及答案

初中数学染色问题及答案_学科竞赛_小学教育_教育专区。1. (1)用 1×1,2×2...种颜色中的某一种来着色,规定相邻的区域着不同的颜色.那么有 着色方法. 种不...


染色问题与染色方法

染色问题与染色方法_初三数学_数学_初中教育_教育专区。数学 竞赛 题目染色问题与染色方法 1. 小方格染色问题 最简单的染色问题是从一种民间游戏中发展起来的方格盘...


思科数学【提优教程】江苏省2012高中数学竞赛 第14讲 染色问题教案

思科数学【提优教程】江苏省2012高中数学竞赛 第14讲 染色问题教案_金融/投资_...故不可能. 说明 用不同的染色方法解决不同的问题. 例 2 用若干个由四个...


染色问题

染色问题_学科竞赛_小学教育_教育专区。数学染色问题时间: 开发人员 课程名称 适应...当时,我们用 了“间隔染色”的方法。那么我们来试试看,是不是在这里也能用“...


组合数学第7讲 染色问题

组合数学第7讲 染色问题_学科竞赛_高中教育_教育专区。数学联赛辅导讲义组合...常用抽屉原理或设置两难命题的方法解. 证明 ⑴取边长为 1 的等边三角形,其三...


数学奥林匹克专题讲座 第12讲 染色和赋值

数学奥林匹克专题讲座 第12讲 染色和赋值_初三数学_数学_初中教育_教育专区。数学奥林匹克专题讲座 第 12 讲 染色和赋值染色方法和赋值方法是解答数学竞赛问题的两...


染色问题

高中数学竞赛讲座二试内容 19 染色问题 (一)一.基本方法 染色问题的本质是对...( 染色问题染色方法(三)解答一.基本方法染色问题的本质是对集合的元素进行...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com