竞赛辅导六年级下学期 　 第四讲 奇妙的方格表

[url=]第四讲 奇妙的方格表 　　方格表是人们最熟悉最简单的图形之一，但这个简单的图形却可以说是一个广阔的数学天地，其中包含着许许多多奇妙的数学问题．许多问题看起来非常简单非常有趣，但却要用到许多数学方法，蕴含着许多深刻的道理．这些方法和道理在我们以后的学习中将经常用到．

一、计数问题

　

　　例1 下图中共有多少个矩形？

　　分析 如果直接数，很容易遗漏或者重复．为了避免遗漏或重复，可以将图形中的各种矩形按形状大小分类，分别计数后再相加．在分类计数中如果能发现规律，那就更简单了．
　　解法1：在已知的方格表中，“□”共有5×3=15个，“□□”共有4×3=12个，“□□□”共有3×3＝9个，…如此进行下去，把各类矩形的个数相加，可得矩形总数为90个．
　　解法2：将各类矩形列出表来（如下页图），分析各类矩形个数的算式，很容易发现规律，于是可得矩形总个数为：（1＋2+3＋4+5）×（3＋2＋1）=90个．

　　

　　格组成的正方形中都含有4个L形．因此为了求L形的个数，只需先求“田”字形的个数．
　　解：在上页的方格表的第1、2行中含有“田”字形 4个，第2、3行中也含4个，共有“田”字形8个，每个“田”字形对应4个L形，因此共有L形4×8=32个．
　　说明：计数最基本的方法是分类讨论．如果在分类讨论中发现规律，就可以改进算法．例2中的计数方法利用了对应的思想．当直接计算某一事物的个数有困难时，往往可以先转化成计算另一事物的个数，然后再研究这两个数，可以先计算2×3的矩形共有多少个，然后由每个2×3的矩形中都10×4=40个．在例1中计算矩形个数还有一些更高明的方法，这些方法将在中学里学到．
8×8的方格表，结果如何？
　　解：如图，在4×4的方格表中放下3个L形，即不能再放下一个L形了．

　　如果只放了两个L形，那么可以证明总还能再放下一个L形．因为每个“田”字形内至少盖住两格后才不再能放下L形，而4×4的方格表中共有4个不相重叠的“田”字形，至少应盖住2×4=8格后，才不再能放一个L形，如果只放了两个L形，仅仅盖住6格，所以总还能再放一个L形．
　　从以上两步，可以看出4×4的方格表中至少放上3个L形后，才能使这一表中不再能放下一个L形．
　　在6×6的方格表中有9个不相重叠的“田”字形，每个“田”字形至少盖住两格，才不再能放下一个L形，这样至少应盖住18格，也就是至少要放上6个L形．如右图，已放了6个L形，确实已不能再放下一个L形了，因此6个是最少的数目．

　　用同样的方法可以得到在8×8的方格表中至少放上11个L形后，就不再能放下一个L形了．

二、染色方法

　　
　　染色方法实际上是一种分类方法，不过对有些问题来说，通过染色能使问题比较直观，解决起来更方便．
　　例4 如图是半张象棋盘，一只马能否从A处出发，跳遍半张象棋盘而使每个格点只经过一次？

　　解：把半张象棋盘的格点（共45个）相间地涂上黑、白两色（黑色用“×”表示，如图共有22个黑点，23个白点．按照马走步的规则，每步走“日”字的对角线，不论马在何处也不论往哪个方向跳，起点和终点的颜色总是不同的．由于A处是黑格点，如果马从A处出发跳遍每个格点且每个格点只经过一次，那么需经过21个黑点，23个白点，黑、白格点数相差2，故这样的走法是不可能的．
　　例5 正方体形的房子共分27个小房间，每相邻两个房间都有门相通（上、下两间也有门相通）．每个房间里都有一块奶酪，右下角的房间有一门通向外面．一只耗子从最中间的房间出发，想走遍各个房间，且每个房间只经过一次，最后从右下角出来，这样是可否能？如果可能，该怎么走？

　　解：将27个小正方体相间染成黑、白两色（如图），共13个房黑间，14个白房间，中间房间是黑色．如果从中间房间出发，每个房间经过一次，共需经过12个黑房间（除中间房间外）、14个白房间．但是与黑房间相邻的都是白房间，与白房间相邻的都是黑房间，路线只能是：黑—白—黑—白…这是不可能实现的．
　　如果改从任一个（不是右下角的）白房间出发，就能达到目的．请自己设计路线．

三、抽屉原理

　　
　　例6 能否在8×8的方格表的每个方格中写上0、1、2中的一个数，使每行、每列以及两条对角线上各数之和都互不相等？
　　解：8行、8列及两条对角线共有18个和数，将这18个和数作为“苹果”．8个数（每个数是0、1、2中的一个）的和最小是0，最大是16，共有17种不同的和，将这17个不同的和作为“抽屉”．根据抽屉原理，必有一个“抽屉”中存在2个或2个以上的“苹果”，这就是说，在18个和数中至少有2个相等，不可能都互不相等．
　　例7 在5×5的方格表中，任意挖去一个方格后，是否总能用8个

　

　　解法1：如右图，将5×5的方格表挖去一格（阴影）后，剩下的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 在4×4的方格表中任意挖去一格，是否总能用5个
　　分析 对于4×4的方格表，由挖去一格的位置不同，可分三种情况讨论．这种分类讨论的方法，对于4×4的方格表来说，由于试验次数较少，还比较容易得到结论．但对于8×8的方格表，需要分10种情况，分别去试验；对于16×16的方格表，则需要分36种情况．对于每种情况，由于表格较大，试验起来也很繁琐．如果运用数学上称为“递推”的方法，问题就简单得多了，不仅能轻易地解决8×8、16×16的方格表的问题，还能解决 32×32、64×64、…等方格表中的类似问题．
　　解法1：对于4×4的方格表，由挖去一格的不同位置，可分三种情况，每种情况都能运用5个L形盖住，因此在4×4的方格表中任意挖去一格，总能用5个L形盖住（如下图）．

　　对于8×8及16×16的方格表，由于分类情况较多，这里从略．
　　解法2：先考虑2×2的方格表，任意挖去一格，剩下3格总是恰好能用1个L形盖住．
　　对于4×4的方格表，挖去的一格总在某个角上的2×2小方格表内，不妨设在左上角，那么左上角的2×2小方格表中剩下3格能用1个L形盖住．在右上、右下、左下的3个2×2方格表中，先各挖去靠中间的一格（如图），剩下的各能用1个L形盖住，而挖去的3格也恰能用1个L形盖住．

　　对于8×8的方格表，挖去的一格总在某个角上的4×4方格表内，不妨设在左上角，那么左上角剩下的部分总能用5个L形盖住．在右上、右下、左下的3个4×4方格表中，先各挖去靠中央的一格（如右图），由上述结论，各4×4方格表中剩下部分总能分别用5个L形盖住．而挖去的3格也恰能用1个L形盖住，所以，8×8方格表中任意挖去一格，总能用21个L形完全盖住．

　　同样，对于16×16的方格表，任意挖去一格后，总可以用85个L形完全盖住．
　　例9 在一个6×6的方格表中，任选5个方格涂黑，然后再逐步将凡是与两个或两个以上黑格相邻的方格涂黑，不断按这个法则做下去，证明：无论怎样选择最初的5个方格，都不可能按这样的法则将所有方格全部涂黑．

　　分析 先试验一下，在上图的方格表中选5格涂黑，然后按给定法则涂黑另一些格，直到上图（4），已无法再将其余的方格涂黑．如果改变最初5格的位置，虽然最后涂黑的部分会不同，但都不能将所有方格全部涂黑．为了证明这一结论，如果将最初5格的不同位置一一列举出来，再逐个证明，当然也是可以的（这种方法叫枚举法），不过过于繁琐．因此，应该在试验中寻求规律，不被表面现象迷惑．
　　证明：考虑涂黑过程中黑色区域的周界总长度．设小方格的边长为1，则开始有5个黑格，黑色区域总长度不大于20．按照题设的涂黑法则，每格在涂黑前后，黑色区域的周界不会变长（此方格至少有两边是原来黑色区域的周界，当此格涂黑后，这两边已不再是边界，而另两边可能成为边界）．如果能将所有方格都涂黑，那么黑色边界的总长度应为24，由以上分析，这是不可能的，因此，无论怎样选择最初的5个方格，都不可能按照题设的法则将全部方格涂黑．
[/url]