培训体系竞赛培训专题染色问题与染色方法.doc

培训体系）竞赛培训 专题染色问题与染色 方法竞赛培训专题 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 色而存于顶点同色的矩 形的最小方格盘是什么仍不得而知 .例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×4 n的倍数， mn、中必有壹个是偶数， 不妨设为 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 ，且它们均染成红色 .再来见 BC的D三边，如其中有壹条边例如 BC 是红色的，则同色三角形已出现（红色ABC）三；边如均不是BCD红色的，则它就是蓝色的三角形，同色三角形也现了.总之 ,不论于哪种情况下 ,均存于同色三角形 .如果将例 4 中的六个人见成例 5 中六点 ,俩人认识的连红线 ,不认识的连蓝线 , 则例 4 就变成了例 5. 例 5 的证明实际上用染色方法给出了例4 的证明 .例6（第6届国际数学奥林匹克试题 ）有17位科学家 ,其中每壹个人和其他所 有人的人通信 ,他们的通信中只讨论三个题目 .求证 :至少有三个科学家相互之 间讨论同壹个题目 .证明用平面上无三点共线的 17 个点 A1 ,A2, ，A17 分别表示 17 位科学家 .设 他们讨论的题目为 x,y,z,俩位科学家讨论 x连红线,讨论y连蓝线,讨论 z连黄 线 .于是只须证明以这 17 个点为顶点的三角形中有壹同色三角形 .考虑以 A 1为端点的线段 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 个偶数，占据白点 A 1=993 个，黑色 B1=993 个.993 个奇数，占据白点 A2=2a 个，黑点 B2=2b 个，其中 a+b=993.因此，共占白色 A=A 1+A 2=993+2a 个.黑点 B=B 1+B 2=993+2b 个，由于 a+b=993 （非偶数！）a b ，从A而得B. 这和黑、白点各有 1986个矛盾 .故这种排法不可能“点”能够是有限个，也能够是无限个，这时染色问题总是和相应的几何问 题联系于壹起的 .例 8 对平面上壹个点，任意染上红、蓝、黑三种颜色中的 壹种 .证明 :平面内存于端点同色的单位线段 .证明作出壹个如图 29-7 的几何图形是可能的 ,其中 ABD、 CBD、 AEF 、均是GE边F长为 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 或的正三角形，它三个顶点是同色的练习答案将、行染红色、行染黄色、行染蓝色，然后就弯角板 盖住板面的不同情况分类讨论设第壹张纸上的黑格和第二张纸上的红格重合 如果于第壹张纸上所于的列中，其余的黑格（奇数个）均和第二张纸的黑格重合，那么由第 二张纸上这壹列的黑格个数为偶数，知必有壹黑格和第壹张纸上的红格重 合，即于这壹列，第壹张纸上有壹方格和第二张纸上不同颜色的方格 重合同理于、所于行上各有壹个方格、，第二张纸上和它们重合 的方格、的颜色分别和、不同把名数学家用点 ， ， 表示俩人能通话，就用线连结，且涂某种颜色，以表示不同语种。俩人不通话，就不连线（）果任俩点均有连线且涂有颜色，那么必有壹点如，以其为壹端点的条线段中至少有俩条同色，比如、可见 ， ，之间可用同壹语言通话如情况不发生，则至少有俩点不连线，比如 、 由题设任三点必有壹条连线知，其余七点必和或 有连线这时七条线中，必有四条是从某壹点如引出的而这四条线中又必有二条同色，则问题得证结论不成立， 如图所示 （图中每条线旁均有壹个数字， 以表示不同语种） 类似于第题证明用点 、 、 表示客人，红、蓝的连线分别表示俩人相识 或不相识，因为由壹个顶点引出的蓝色的线段最多有条，所以其中至少 有三点之间连红线这三个点（设为 、 、 ）引出的蓝色线段最多 为条 去掉所有这些蓝色的线段 （连同每条线段上的壹个端点 ， ，），这样，于图中至少仍剩下四个点，除、 、 外，设第四点为 ，这四个点中 ， ， 每壹个点和其它的点均以红色的 线段相连，于是客人 、 、 、 彼此俩俩相识先利用右图证明若平面上有俩个异色的点距离为，地么必定能够找 到符合题意的三角形 再找长为端点异色的线段 以（白色） 为圆心， 为半径作圆如圆内皆白点，问题已证否则圆内有壹黑点，以为 底作腰长为的三角形，则至少和、中壹点异色，这样的线段 找到