高中数学竞赛讲座 14染色问题与染色方法
上传者:麻贵峰|上传时间:2015-04-15|密次下载
高中数学竞赛讲座 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是端点同色的单位线段.证毕.
还有一类较难的对区域染色的问题,就不作介绍了.
下载文档
热门试卷
- 2016年四川省内江市中考化学试卷
- 广西钦州市高新区2017届高三11月月考政治试卷
- 浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
- 浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
- 辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
- 广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
- 广西钦州市钦州港区2017届高三11月月考政治试卷
- 广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
- 广西钦州市高新区2016-2017学年高二11月月考政治试卷
- 广西钦州市高新区2016-2017学年高一11月月考政治试卷
- 山东省滨州市三校2017届第一学期阶段测试初三英语试题
- 四川省成都七中2017届高三一诊模拟考试文科综合试卷
- 2017届普通高等学校招生全国统一考试模拟试题(附答案)
- 重庆市永川中学高2017级上期12月月考语文试题
- 江西宜春三中2017届高三第一学期第二次月考文科综合试题
- 内蒙古赤峰二中2017届高三上学期第三次月考英语试题
- 2017年六年级(上)数学期末考试卷
- 2017人教版小学英语三年级上期末笔试题
- 江苏省常州西藏民族中学2016-2017学年九年级思想品德第一学期第二次阶段测试试卷
- 重庆市九龙坡区七校2016-2017学年上期八年级素质测查(二)语文学科试题卷
- 江苏省无锡市钱桥中学2016年12月八年级语文阶段性测试卷
- 江苏省无锡市钱桥中学2016-2017学年七年级英语12月阶段检测试卷
- 山东省邹城市第八中学2016-2017学年八年级12月物理第4章试题(无答案)
- 【人教版】河北省2015-2016学年度九年级上期末语文试题卷(附答案)
- 四川省简阳市阳安中学2016年12月高二月考英语试卷
- 四川省成都龙泉中学高三上学期2016年12月月考试题文科综合能力测试
- 安徽省滁州中学2016—2017学年度第一学期12月月考高三英语试卷
- 山东省武城县第二中学2016.12高一年级上学期第二次月考历史试题(必修一第四、五单元)
- 福建省四地六校联考2016-2017学年上学期第三次月考高三化学试卷
- 甘肃省武威第二十三中学2016—2017学年度八年级第一学期12月月考生物试卷
网友关注
网友关注视频
- 《空中课堂》二年级下册 数学第一单元第1课时
- 《小学数学二年级下册》第二单元测试题讲解
- 北师大版数学 四年级下册 第三单元 第二节 小数点搬家
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 3
- 外研版英语七年级下册module1unit3名词性物主代词讲解
- 二年级下册数学第一课
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 8
- 二年级下册数学第二课
- 【部编】人教版语文七年级下册《泊秦淮》优质课教学视频+PPT课件+教案,天津市
- 人教版二年级下册数学
- 苏科版数学八年级下册9.2《中心对称和中心对称图形》
- 外研版英语三起5年级下册(14版)Module3 Unit2
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 4
- 沪教版八年级下册数学练习册20.4(2)一次函数的应用2P8
- 【部编】人教版语文七年级下册《泊秦淮》优质课教学视频+PPT课件+教案,湖北省
- 沪教版牛津小学英语(深圳用) 六年级下册 Unit 7
- 冀教版小学数学二年级下册第二周第2课时《我们的测量》宝丰街小学庞志荣.mp4
- 七年级英语下册 上海牛津版 Unit9
- 3.2 数学二年级下册第二单元 表内除法(一)整理和复习 李菲菲
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 2
- 飞翔英语—冀教版(三起)英语三年级下册Lesson 2 Cats and Dogs
- 冀教版小学英语五年级下册lesson2教学视频(2)
- 第五单元 民族艺术的瑰宝_16. 形形色色的民族乐器_第一课时(岭南版六年级上册)_T1406126
- 化学九年级下册全册同步 人教版 第25集 生活中常见的盐(二)
- 【部编】人教版语文七年级下册《逢入京使》优质课教学视频+PPT课件+教案,安徽省
- 七年级英语下册 上海牛津版 Unit3
- 六年级英语下册上海牛津版教材讲解 U1单词
- 北师大版数学四年级下册第三单元第四节街心广场
- 小学英语单词
- 二次函数求实际问题中的最值_第一课时(特等奖)(冀教版九年级下册)_T144339
精品推荐
- 2016-2017学年高一语文人教版必修一+模块学业水平检测试题(含答案)
- 广西钦州市高新区2017届高三11月月考政治试卷
- 浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
- 浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
- 辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
- 广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
- 广西钦州市钦州港区2017届高三11月月考政治试卷
- 广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
- 广西钦州市高新区2016-2017学年高二11月月考政治试卷
- 广西钦州市高新区2016-2017学年高一11月月考政治试卷
分类导航
- 互联网
- 电脑基础知识
- 计算机软件及应用
- 计算机硬件及网络
- 计算机应用/办公自动化
- .NET
- 数据结构与算法
- Java
- SEO
- C/C++资料
- linux/Unix相关
- 手机开发
- UML理论/建模
- 并行计算/云计算
- 嵌入式开发
- windows相关
- 软件工程
- 管理信息系统
- 开发文档
- 图形图像
- 网络与通信
- 网络信息安全
- 电子支付
- Labview
- matlab
- 网络资源
- Python
- Delphi/Perl
- 评测
- Flash/Flex
- CSS/Script
- 计算机原理
- PHP资料
- 数据挖掘与模式识别
- Web服务
- 数据库
- Visual Basic
- 电子商务
- 服务器
- 搜索引擎优化
- 存储
- 架构
- 行业软件
- 人工智能
- 计算机辅助设计
- 多媒体
- 软件测试
- 计算机硬件与维护
- 网站策划/UE
- 网页设计/UI
- 网吧管理