9512.net
甜梦文库
当前位置:首页 >> 幼儿读物 >>

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



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

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 色而存在顶点同色的 矩形的最小方格盘是什么还不得而知.

- 1 -

例 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. 线段染色和点染色 下面介绍两类重要的染色问题.

- 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.
- 3 -

定理 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
- 4 -

异色,在这种情况下,如果 C 或 G 为黄色或蓝点,则 CB、CD、GE、GF 中有两条是端点同色 的单位线段,问题也得证.不然的话,C、G 均为红点,这时 CG 是端点同色的单位线段.证 毕. 还有一类较难的对区域染色的问题,就不作介绍了. 练习 1. 6×6 的方格盘,能否用一块大小为 3 格,形如的弯 3×1 的矩形板,不重迭不遗漏地来铺满整个盘面. 角板与 11 块大小为

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不同.
- 5 -

的正三角形,它三个顶点是同色的.

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中一点异 色,这样的线段找到.

- 6 -



更多相关文章:
染色问题与染色方法
染色问题与染色方法_基础医学_医药卫生_专业资料。竞赛专题贾老师数学教学网 贾老师...2. 线段染色和点染色 下面介绍两类重要的染色问题. - 2 - 贾老师数学教学...
染色问题
染色问题_理学_高等教育_教育专区。高中数学竞赛辅导资料高中数学竞赛讲座二试内容...问题,染色可以使分类更直观、更形象. 染色问题主要有两类: 一类使借助染色方法...
小学奥数专题15:染色问题
小学奥数专题15:染色问题_学科竞赛_小学教育_教育专区。专题 14 染色问题 1....2. 不能.对展室进行染色,使相邻两房间分别是黑色白色的.此时入口处 展室...
染色问题
染色问题_学科竞赛_小学教育_教育专区。数学染色问题时间: 开发人员 课程名称 适应...1.通过游戏的方式解释染色问题 2.问题:为什么要将椅子间隔染色课程框架 3.问题...
小学奥数专题:黑白染色问题
小学奥数专题:黑白染色问题_学科竞赛_小学教育_教育专区。专题:黑白染色问题 1....2.展览会有 36 专题:黑白染色问题 1.下图是一套房子的平面图,图中的方格...
棋盘染色问题-网上
染色问题 知识网络 数学竞赛中的“染色”一般包括两个方面:染色问题和染色方法。...第种颜色染在 C 和 E 上,用第 三种颜色染在 B 和 D 上即可满足题意...
高中竞赛数学讲义第14讲染色问题
第14 讲 染色问题本节主要讲述用染色的方法解有关的竞赛题.染色,是一种辅助...故不可能. 说明 用不同的染色方法解决不同的问题. 例 2 用若干个由四个...
江苏省数学竞赛提优教案:第14讲 染色问题
第14 讲 染色问题 本节主要讲述用染色的方法解有关的竞赛题. 染色, 是一种...故不可能. 说明 用不同的染色方法解决不同的问题. 例 2 用若干个由四个...
《高中竞赛教程》教案:第14讲 染色问题
第14 讲 染色问题本节主要讲述用染色的方法解有关的竞赛题.染色,是一种辅助...故不可能. 说明 用不同的染色方法解决不同的问题. 例 2 用若干个由四个...
六年级奥数专题01:染色问题
六年级奥数专题01:染色问题_学科竞赛_小学教育_教育专区。二十 染色问题(1) ...6. 如图的方式对棋盘染色.那么一个田字形盖住 1 个或 3 个白格,而一个 4...
更多相关标签:

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

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