染色问题与染色方法
摘要:染色问题与染色方法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的矩形瓷砖去盖,如果盖住的两种颜色的小矩形不是一样多,则说明在给定条件不完满铺盖不可能.证明如图2
温馨提示:当前文档最多只能预览
5 页,若文档总页数超出了
5 页,请下载原文档以浏览全部内容。
本文档由 匿名用户 于 2022-07-05 23:38:45上传分享