4.2　瓷砖覆盖地板

某年夏天，位于希格玛大厦四层的微软亚洲研究院对办公楼的天井进行了一次大规模的装修。原来的地板铺有N×M块正方形瓷砖，这些瓷砖都已经破损老化了，需要予以更新。装修工人们在前往商店选购新的瓷砖时，发现商店目前只供应长方形的瓷砖，现在的一块长方形瓷砖相当于原来的两块正方形瓷砖，工人们拿不定主意该买多少了，读者朋友们请帮忙分析一下：能否用1×2的瓷砖去覆盖N×M的地板呢？

分析与解法

N×M的地板有如下几种可能：

1．如果N＝1，M为偶数的话，显然，1×2的瓷砖可以覆盖1×M的地板，在这种情况下，共需要M/2块瓷砖。

2．如果N×M为奇数，也就是N和M都为奇数，则肯定不能用1×2的瓷砖去覆盖它。证明：假设能够用k块1×2的瓷砖去覆盖N×M（N、M都为奇数）的地板，设每块瓷砖的面积为1×2，那么总的地板面积就为2k——必为偶数，又因为N、M都为奇数，也就是N×M的地板面积肯定为奇数，与1×2的瓷砖所能覆盖的面积相矛盾，所以肯定不能用1×2的瓷砖去覆盖它。

3．N和M中至少有一个为偶数，不妨设M为偶数，那么既然我们可以用1×2的地板覆盖1×M的地板，也就可以简单地重复N次覆盖1×M的地板的做法，即可覆盖N×M的地板。

扩展问题

求用1×2的瓷砖覆盖2×M的地板有几种方式？

设用1×2的瓷砖覆盖2×M的地板有F（M）种方式，其中F为M的函数，那么第一块瓷砖的放法如图4-1、图4-2所示：

图4-1　第一块瓷砖竖着放，如图中阴影部分所示

图4-2　第一块瓷砖横着放，如图中阴影部分所示

通过对图4-1、图4-2的简单分析，我们知道第一块瓷砖的放法，要么是竖着放，要么是横着放。

当第一块瓷砖竖着放的时候，问题转换成求用1×2的瓷砖覆盖剩下的2×（M－1）的方式，即F（M－1）。

当第一块瓷砖横着放的时候（必有另一块瓷砖放在其正下方，如图中阴影所示），问题转换成求用1×2的瓷砖覆盖剩下的2×（M－2）的方式，即F（M－2）。

在求F（M－1）和F（M－2）时，由于第一列地板的覆盖方式已经不同，F（M－1）种覆盖方式和F（M－2）中覆盖方式没有重叠，故F（M）＝F（M－1）＋F（M－2），其中，F（1）＝1，F（2）＝2。

读者朋友们不妨思考一下这个问题的推广形式又该如何解答：

1．用1×2的瓷砖覆盖8×8的地板，有多少种方式呢？如果是N×M的地板呢？

2．用p×q的瓷砖能够覆盖M×N的地板吗？