第四讲 奇妙的方格表.doc

第四讲 奇妙的方格表方格表是人们最熟悉最简单的图形之一，但这个简单的图形却可以说是一个广阔的数学天地，其中包含着许许多多奇妙的数学问题许多问题看起来非常简单非常有趣，但却要用到许多数学方法，蕴含着许多深刻的道理这些方法和道理在我们以后的学习中将经常用到一、计数问题例1 下图中共有多少个矩形？分析 如果直接数，很容易遗漏或者重复为了避免遗漏或重复，可以将图形中的各种矩形按形状大小分类，分别计数后再相加在分类计数中如果能发现规律，那就更简单了解法1：在已知的方格表中，“”共有53=15个，“”共有43=12个，“”共有339个，如此进行下去，把各类矩形的个数相加，可得矩形总数为90个解法2：将各类矩形列出表来（如下页图），分析各类矩形个数的算式，很容易发现规律，于是可得矩形总个数为：（12+34+5）（321）=90个格组成的正方形中都含有4个L形因此为了求L形的个数，只需先求“田”字形的个数 解：在上页的方格表的第1、2行中含有“田”字形 4个，第2、3行中也含4个，共有“田”字形8个，每个“田”字形对应4个L形，因此共有L形48=32个说明：计数最基本的方法是分类讨论如果在分类讨论中发现规律，就可以改进算法例2中的计数方法利用了对应的思想当直接计算某一事物的个数有困难时，往往可以先转化成计算另一事物的个数，然后再研究这两个数，可以先计算23的矩形共有多少个，然后由每个23的矩形中都104=40个在例1中计算矩形个数还有一些更高明的方法，这些方法将在中学里学到88的方格表，结果如何？解：如图，在44的方格表中放下3个L形，即不能再放下一个L形了如果只放了两个L形，那么可以证明总还能再放下一个L形因为每个“田”字形内至少盖住两格后才不再能放下L形，而44的方格表中共有4个不相重叠的“田”字形，至少应盖住24=8格后，才不再能放一个L形，如果只放了两个L形，仅仅盖住6格，所以总还能再放一个L形从以上两步，可以看出44的方格表中至少放上3个L形后，才能使这一表中不再能放下一个L形在66的方格表中有9个不相重叠的“田”字形，每个“田”字形至少盖住两格，才不再能放下一个L形，这样至少应盖住18格，也就是至少要放上6个L形如右图，已放了6个L形，确实已不能再放下一个L形了，因此6个是最少的数目用同样的方法可以得到在88的方格表中至少放上11个L形后，就不再能放下一个L形了二、染色方法染色方法实际上是一种分类方法，不过对有些问题来说，通过染色能使问题比较直观，解决起来更方便例4 如图是半张象棋盘，一只马能否从A处出发，跳遍半张象棋盘而使每个格点只经过一次？解：把半张象棋盘的格点（共45个）相间地涂上黑、白两色（黑色用“”表示，如图共有22个黑点，23个白点按照马走步的规则，每步走“日”字的对角线，不论马在何处也不论往哪个方向跳，起点和终点的颜色总是不同的由于A处是黑格点，如果马从A处出发跳遍每个格点且每个格点只经过一次，那么需经过21个黑点，23个白点，黑、白格点数相差2，故这样的走法是不可能的例5 正方体形的房子共分27个小房间，每相邻两个房间都有门相通（上、下两间也有门相通）每个房间里都有一块奶酪，右下角的房间有一门通向外面一只耗子从最中间的房间出发，想走遍各个房间，且每个房间只经过一次，最后从右下角出来，这样是可否能？如果可能，该怎么走？解：将27个小正方体相间染成黑、白两色（如图），共13个房黑间，14个白房间，中间房间是黑色如果从中间房间出发，每个房间经过一次，共需经过12个黑房间（除中间房间外）、14个白房间但是与黑房间相邻的都是白房间，与白房间相邻的都是黑房间，路线只能是：黑白黑白这是不可能实现的如果改从任一个（不是右下角的）白房间出来，就能达到目的请自己设计路线三、抽屉原理例6 能否在88的方格表的每个方格中写上0、1、2中的一个数，使每行、每列以及两条对角线上各数之和都互不相等？解：8行、8列及两条对角线共有18个和数，将这18个和数作为“苹果”8个数（每个数是0、1、2中的一个）的和最小是0，最大是16，共有17种不同的和，将这17个不同的和作为“抽屉”根据抽屉原理，必有一个“抽屉”中存在2个或2个以上的“苹果”，这就是说，在18个和数中至少有2个相等，不可能都互不相等例7 在55的方格表中，任意挖去一个方格后，是否总能用8个解法1：如右图，将55的方格表挖去一格（阴影）后，剩下的24住a格，需要用一个L形盖住a、d、e或a、b、c三格，由于两边对称，不妨设盖住a、b、c三格，这样，x格就不可能被任何一个L形盖住（否则就重叠了），所以这24格不可能被完全盖住解法 2：如图，标上“”的格共有 9个，如果挖去的一格不是标上“”的格，那么剩下的24格不可能被8个L形盖住这是因为任意两个“”格不可能被同一个L形盖住，这9个“”格若都能被盖住，至少需要9个L形，因此不能用8个L形盖住剩下的24格说明：解法1虽然很简单，但要想到这种解法，需要做多次试验（当挖去的一格在某些位置时，题目的要求是可以成立的）解法2实际上用了抽屉原理，“”格看作“苹果”，8个L形看成“抽屉”用抽屉原理的关键是要设计好“抽屉”和“苹果”四、分类、试验、递推、寻求规律例8 在44的方格表中任意挖去一格，是否总能用5个分析 对于44的方格表，由挖去一格的位置不同，可分三种情况讨论这种分类讨论的方法，对于44的方格表来说，由于试验次数较少，还比较容易得到结论但对于88的方格表，需要分10种情况，分别去试验；对于1616的方格表，则需要分36种情况对于每种情况，由于表格较大，试验起来也很繁琐如果运用数学上称为“递推”的方法，问题就简单得多了，不仅能轻易地解决88、1616的方格表的问题，还能解决 3232、6464、等方格表中的类似问题解法1：对于44的方格表，由挖去一格的不同位置，可分三种情况，每种情况都能运用5个L形盖住，因此在44的方格表中任意挖去一格，总能用5个L形盖住（如下图）对于88及1616的方格表，由于分类情况较多，这里从略解法2：先考虑22的方格表，任意挖去一格，剩下3格总是恰好能用1个L形盖住对于44的方格表，挖去的一格总在某个角上的22小方格表内，不妨设在左上角，那么左上角的22小方格表中剩下3格能用1个L形盖住在右上、右下、左下的3个22方格表中，先各挖去靠中间的一格（如图），剩下的各能用1个L形盖住，而挖去的3格也恰能用1个L形盖住对于88的方格表，挖去的一格总在某个角上的44方格表内，不妨设在左上角，那么左上角剩下的部分总能用5个L形盖住在右上、右下、左下的3个44方格表中，先各挖去靠中央的一格（如右图），由上述结论，各44方格表中剩下部分总能分别用5个L形盖住而挖去的3格也恰能用1个L形盖住，所以，88方格表中任意挖去一格，总能用21个L形完全盖住同样，对于1616的方格表，任意挖去一格后，总可以用85个L形完全盖住例9 在一个66的方格表中，任选5个方格涂黑，然后再逐步将凡是与两个或两个以上黑格相邻的方格涂黑，不断按这个法则做下去，证明：无论怎样选择最初的5个方格，都不可能按这样的法则将所有方格全部涂黑分析 先试验一下，在上图的方格表中选5格涂黑，然后按给定法则涂黑另一些格，直到上图（4），已无法再将其余的方格涂黑如果改变最初5格的位置，虽然最后涂黑的部分会不同，但都不能将所有方格全部涂黑为了证明这一结论，如果将最初5格的不同位置一一列举出来，再逐个证明，当然也是可以的（这种方法叫枚举法），不过过于繁琐因此，应该在试验中寻求规律，不被表面现象迷惑证明：考虑涂黑过程中黑色区域的周界总长度设小方格的边长为1，则开始有5个黑