9512.net
甜梦文库
当前位置:首页 >> 理学 >>

高中竞赛专题:染色问题与染色方法



竞赛讲座 14 -染色问题与染色方法 染色问题与染色方法
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,…, 17 分别表示 17 位科学家.设他们讨 A 论的题目为 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 是端点同色的单位线段.证毕. 还有一类较难的对区域染色的问题,就不作介绍了.


更多相关文章:
竞赛研究专题染色问题研究
高中竞赛专题:染色问题与... 2页 8财富值 竞赛讲座 13-染色问题与染... 8页 免费 竞赛讲座 14染色问题与染色... 8页 免费喜欢此文档的还喜欢 ...
染色问题与染色方法
百度文库 教育专区 高中教育 学科竞赛1/2 相关文档...数学奥林匹克专题讲座 第... 12页 1下载券 搏击...染色问题与染色方法例 1、世界上任何六个人中,一定...
六年级奥数专题01:染色问题
六年级奥数专题01:染色问题_学科竞赛_小学教育_教育专区。二十 染色问题(1) ...但是对于一种满足要求跳法,在两种染色方式下第奇数步跳入的格子的全体 是不同...
小学奥数专题:黑白染色问题
小学奥数专题:黑白染色问题_学科竞赛_小学教育_教育专区。专题:黑白染色问题 1.下图是一套房子的平面图,图中的方格代表房间,每个房间都有通向任何 一个邻室的门...
小学奥数专题15:染色问题
小学奥数专题15:染色问题_学科竞赛_小学教育_教育专区。专题 14 染色问题 1....14. 用两种方法对超级棋盘染色. 首先,将棋盘黑白相间染色,则马每跳一步,它...
华杯赛赛前专题讲座-染色问题_图文
华杯赛赛前专题讲座-染色问题_学科竞赛_小学教育_教育专区 暂无评价|0人阅读|0次下载|举报文档华杯赛赛前专题讲座-染色问题_学科竞赛_小学教育_教育专区。华杯...
2015年高考排列组合专题染色问题
2015年高考排列组合专题染色问题_高考_高中教育_教育专区。2015年高考排列组合...(以数字作答) 1 【分析】首先栽种第 1 部分,有 C4 种栽种方法; 然后问题...
染色问题的求解方法
故有 A42 种染色方法;再从余下的 2 种颜色中任选 1 种染 D 或 C,而 D...那么,我们就说这两个正方体的染色方案相同)(1996 年全国高中数学联赛题) 。。...
高中数学《排列组合染色问题》典例讲解
高中数学《排列组合染色问题》典例讲解_高二数学_数学...(m ? 1) ? (?1) (m ? 1) 种染色方法。 ...排列组合专题染色问题... 3页 免费 高考数学中涂色...
29(高中竞赛讲座)涂色问题
介绍,只是中学数学竞赛中的有关问题。 1. 小方格染色问题 最简单的染色问题是...就变成了习题 3.习题 3 的证明实际上用染色方法给出了习题 5 的证明. ,…...
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图