数学竞赛-染色问题及染色方法.pdf

染色问题与染色方法 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的三边，如其中有一条边例