培训体系竞赛培训专题染色问题与染色方法.doc
《培训体系竞赛培训专题染色问题与染色方法.doc》由会员分享,可在线阅读,更多相关《培训体系竞赛培训专题染色问题与染色方法.doc(18页珍藏版)》请在三一文库上搜索。
1、培训体系)竞赛培训 专题染色问题与染色 方法竞赛培训专题 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、格, 则这个问题已经得证;如第 2 行和第 3 行每行最多 只有壹个红色小方格(如图 29-1 ( c),那么于这俩行中必出现四角同为 蓝色的矩形,问题也得到证明 .说明:( 1 )于上面证明过程中除了运用抽屉原则外,仍要用到壹种思考问 题的有效方法,就是逐步缩小所要讨论的对象的范围,把复杂问题逐步化为 简单问题进行处理的方法2 )此例的行和列均不能再减少了 .显然只有俩行的方格盘染俩色后是不壹定存于顶点同 色的矩形的 .下面我们举出壹个 3 行 6 列染俩 色不存于顶点同色矩形的例子如图 29-2. 这说 明3 行7 列是染俩色存于顶点同色的矩形的最 小方格盘了 .至今 ,染 k 色而存于顶
3、点同色的矩 形的最小方格盘是什么仍不得而知 .例2(第2届全国部分省市初中数学通讯赛题)证明:用 15块大小是 4×1的矩形瓷砖和 1 块大小是 2 ×2的矩形瓷砖,不能恰好铺盖 8 ×8矩形的地面 .分析将 8 ×8矩形地面的壹半染上壹种颜色,另壹半染上另壹种颜色,再用4 ×1和 2 ×2的矩形瓷砖去盖,如果盖住的俩种颜色的小矩形不是壹样多, 则说明于给定条件不完满铺盖不可能 .证明如图 29-3 ,用间隔为俩格且和副对角线平行的斜格同色的染色方式, 以 黑白俩种颜色将整个地面的方格染色 .显然,地面上黑、白格各有 32 个 .每块
4、 4 ×1的矩形砖不论是横放仍是竖盖, 且不论盖于何处, 总是占据地面上 的俩个白格、俩个黑格,故 15 块 4 ×1的矩形砖铺盖后仍剩俩个黑格和俩个白格 .但由于和副对角线平行的斜格总是同色, 而和主对角线平行的相邻格总是异色, 所以,不论怎样放置,壹块 2 ×2的矩形砖,总是盖住三黑壹白或壹 黑三白 .这说明剩下的壹块 2 ×2矩形砖无论如何盖不住剩下的二黑二白的地 面 .从而问题得证 .例 3( 1986 年北京初二数学竞赛题)如图29-4 ( 1)是 4 个 1×1的正方形组成的“ L ”形,用若干个这种L”形硬纸片无重迭拼成m壹
5、15;个n(长为m 个单位,宽为 n 个单位)的矩形如图29-4 (2) .试证明 mn 必是 8 的倍数.证明 m×n矩形由“ L”形拼成,是m×4 n的倍数, mn、中必有壹个是偶数, 不妨设为 m. 把 m×n 矩形中的 m 列按壹列黑、 壹列白间隔染色 (如图 29-4 ( 2),则不论“L”形于这矩形中的放置位置如何(“L”形的放置,共有 8 种可能),“L ”形或占3有白壹黑四个单位正方形(第壹种),或占有 3 黑壹白四个单位正方形(第二种) .设第壹种“L”形共有p 个,第二种“L”形q共个,则 m×n 矩形中的白格单位正方形数为 3p+q
6、 ,而它的黑格单位正方形数为 p+3q.m 为偶数,m×矩n形中黑、白条数相同,黑、白单位正方形总数也必相等故有 3p+q=p+3q ,从而 p=q. 所以“ L”形的总数为 2p 个,即“ L”形总数为偶数,所以m×n壹定是 8 的倍 数.2 线段染色和点染色下面介绍俩类重要的染色问题 .(1) 线段染色 .较常见的壹类染色问题是发样子组合数学中图论知识的所谓 “边染色”(或称“线段染色”),主要借助抽屉原则求解 .例 4( 1947 年匈牙利数学奥林匹克试题)世界上任何六个人中,壹定有 3 个人或者互相认识或者互相均不认识 .我们不直接证明这个命题,而来见和之等价的下述
7、命题例 5( 1953 年美国普特南数学竞赛题) 空间六点, 任三点不共线, 任四点不 共面,成对地连接它们得十五条线段,用红色或蓝色染这些线段(壹条线段 只染壹种颜色) .求证 :无论怎样染 ,总存于同色三角形 .证明设 A、B、C、D、E、F是所给六点 .考虑以 A 为端点的线段 AB、AC、AD 、AE、 AF,由抽屉原则这五条线段中至少有三条颜色相同,不妨设就是 AB、AC、AD ,且它们均染成红色 .再来见 BC的D三边,如其中有壹条边例如 BC 是红色的,则同色三角形已出现(红色ABC)三;边如均不是BCD红色的,则它就是蓝色的三角形,同色三角形也现了.总之 ,不论于哪种情况下 ,
8、均存于同色三角形 .如果将例 4 中的六个人见成例 5 中六点 ,俩人认识的连红线 ,不认识的连蓝线 , 则例 4 就变成了例 5. 例 5 的证明实际上用染色方法给出了例4 的证明 .例6(第6届国际数学奥林匹克试题 )有17位科学家 ,其中每壹个人和其他所 有人的人通信 ,他们的通信中只讨论三个题目 .求证 :至少有三个科学家相互之 间讨论同壹个题目 .证明用平面上无三点共线的 17 个点 A1 ,A2, ,A17 分别表示 17 位科学家 .设 他们讨论的题目为 x,y,z,俩位科学家讨论 x连红线,讨论y连蓝线,讨论 z连黄 线 .于是只须证明以这 17 个点为顶点的三角形中有壹同色三
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 培训 体系 竞赛 专题 染色 问题 方法
链接地址:https://www.31doc.com/p-13110555.html