竞赛培训专题 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 的正方...
