9512.net
甜梦文库
当前位置:首页 >> 一年级语文 >>

数学奥林匹克竞赛讲座 14染色问题与染色方法



竞赛讲座 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,…,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 若在 k6 中,任染红,蓝两色,则必有一只同色三角形. 定理 2 在 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,A3每一个点与其它的 点都以红色的线段相连,于是客人A1,A2,A3,A4彼此两两相识. 7.先利用右图证明"若平面上有两个异色的点距离为2,地么必定可以找到符合题意的三角形".再找长 为2端点异色的线段.以O(白色)为圆心,4为半径作圆.如圆内皆白点,问题已证.否则圆内有一黑点 P,以OP为底作腰长为2的三角形OPR,则R至少与O,P中一点异色,这样的线段找到.


更多相关文章:
华杯赛赛前专题讲座-染色问题_图文
华杯赛赛前专题讲座-染色问题_学科竞赛_小学教育_教育专区 暂无评价|0人阅读|0次下载|举报文档华杯赛赛前专题讲座-染色问题_学科竞赛_小学教育_教育专区。华杯...
六年级奥数专题01:染色问题
六年级奥数专题01:染色问题_学科竞赛_小学教育_教育专区。二十 染色问题(1) ...14. 用两种方法对超级棋盘染色. 首先,将棋盘黑白相间染色 ,则马每跳一步,它...
初中数学染色问题及答案
初中数学染色问题及答案_学科竞赛_小学教育_教育专区。1. (1)用 1×1,2×2...对这五个区域,我们分五步依次给予着色: (1)区域 A 共有 5 种着色方式; (...
2012江苏省数学竞赛《提优教程》教案:第14染色问题
14染色问题本节主要讲述用染色方法解有关的竞赛题.染色,是一种辅助...(2000 第 26 届俄罗斯数学奥林匹克) 本节“情景再现”解答: 1.解将(A)的...
竞赛讲座14_5
竞赛讲座 14 -染色问题与染色方法 1. 小方格染色问题 最简单的染色问题是从一...(1947 年匈牙利数学奥林匹克试题)世界上任何六个人中,一定有 3 个人或者互相...
思科数学【提优教程】江苏省2012高中数学竞赛14讲 ...
竞赛题.染色,是一种辅助解题的手段,通过染 色,...用不同的染色方法解决不同的问题. 例 2 用若干个...(2000 第 26 届俄罗斯数学奥林匹克) 本节“情景...
组合数学第7讲 染色问题
组合数学第7讲 染色问题_学科竞赛_高中教育_教育专区。数学联赛辅导讲义组合...个小方格所染的颜色互不相同.(第 26 届俄罗斯数学奥林匹克) 2 解设 4 种...
初中数学奥林匹克竞赛方法与试题大全
初中数学奥林匹克竞赛方法与试题大全_初中教育_教育专区。初中数学奥林匹克竞赛必...6、逻辑推理问题 抽屉原则(概念),分割图形造抽屉、按同余类造抽屉、利用染色造...
染色问题
高中数学竞赛讲座二试内容 19 染色问题 (一)一....染色方法解决问题; 二类是问题的条件是用染色的方式...必有三条直线两两异面. 例14.在平面上放置六个...
染色问题模拟试卷
数学奥林匹克模拟试卷 ___年级___班 姓名___得分...14.(表 1)是由数字 0,1 交替构成的,(表 2)...染色问题与染色方法 暂无评价 9页 免费 棋盘的染色...
更多相关标签:

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

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