难铺的瓷砖

    布朗先生的院子里铺有40块四方瓷砖.这些瓷砖已经破损老化,他想予以更新.他为修整院子选购新的瓷砖.可惜,目前商店里只供应长方形的瓷砖,每块等于原来的两块.店主:"布朗先生,您需要几块?".布朗先生:"嗯,我要更换40块方瓷砖,所以我估计需要20块."
    布朗先生试着用刚买的新瓷砖铺院子,结果弄得烦闷不堪.不管他怎样努力,总是无法铺好.
    贝特西:"出了什么问题?爸爸?" 布朗先生:"这些该死的瓷砖,真叫人恼火.最后总是剩下两个方格没法铺上瓷砖."
    布朗先生的女儿画了一张院子的平面图,并且涂上了颜色,看上去好似一张棋盘.然后她沉思了几分钟.
    贝特西:"啊哈!我看出症结的所在了.请设想每块长方形瓷砖必定盖住一个红色的格子和一个白色的格子,问题就清楚了."
这里面有什么奥妙,你理解贝特西的意思吗?
    共有19个白色的格子和21个红色的格子,所以铺了19块瓷砖后,总要剩下2个红格没有铺,而一块长方形瓷砖是无法盖住2个红格的.唯一的办法是把最后一块长方形瓷砖断为两块.

    布朗先生的女儿利用所谓"奇偶校验"解答了铺瓷砖问题.如果两个数都是奇数或都是偶数,则称其为具有相同的奇偶性,如果一个数是奇数,另一个数是偶数,则称其具有相反的奇偶性.在组合几何中,经常会遇到类似的情况.
  在这个问题中,同色的两个格子具有相同的奇偶性,异色的两个格子具有相反的奇偶性.长方形瓷砖显然只能覆盖具有相反奇偶性的一对格子.布朗小姐首先说明,把19块长方形瓷砖在院子内铺上后,只有在剩下的两个方格具有相反的奇偶性时,才能把最后一块长方形瓷砖铺上.由于剩下的两个方格具有相同的奇偶性,因此无法铺上最后一块长方形瓷砖.所以用20块长方形瓷砖来铺满院子是不可能的.
    数学中许多著名的不可能性的证明都建立在奇偶校验上.也许你很熟悉欧几里德的著名证明:2的平方根不可能是一个有理数.证明是这样进行的:首先假设此平方根可以表示成一个既约的有理分数,则分子和分母不可能都是偶数,否则它就不是一个既约分数.分子,分母可能都是奇数或者一个是奇数,另一个是偶数.欧几里德证明接着论证此分数不可能属于上述两种情况,换句话说,分子和分母不可能具有相同的奇偶性或相反的奇偶性.而任何有理分数是两者必居其一,因而反证了2的平方根不可能是一个有理数.
  在铺砌理论中,有许多必定要用奇偶校验才能论证其不可能性的问题.上述问题只是个极其简单的例子,因为它仅仅涉及用多米诺骨牌,即简单的,不平凡的波利米诺来铺砌.(一个波利米诺是一些边沿相连的单位正方形的集合)布朗小姐的不可能性证明适用于符合下列要求的单位方格矩阵:这种矩阵若按照棋盘那样涂色后,一种颜色的方格要比另一种颜色的方格至少多一个.
  在上述问题中,可以把院子看作缺少两个同色方格的一个6X7矩阵.显然,如果缺少的两个方格同色,20个多米诺骨牌无法覆盖其余的40个方格.一个有趣的并与此有关的问题是:如果缺少两个颜色不同的方格,20个多米诺骨牌是否能够覆盖住那缺格的6X7矩阵?虽然奇偶校验没有证明其不可能性,但着并不意味着一定可以覆盖.通过擦去一对异色的方格,可以生成所有可能的图形.但若逐一加以研究则不胜其烦,因为各种可能的情况太多,以至于无法分析.对于所有的情况来说,是否有一种简单的可能性证明?
  有的,此证明既简单又巧妙,为拉尔夫.戈莫里妙手偶得之.他同样也是利用了奇偶原理.假设此6X7矩阵有一条波及整个内部的闭合回路,宽度为一格.假设把闭合回路上任何两个异色方格擦去,于是该闭合回路就一断为二,每一部分都是由格数成偶数的异色方格组成.显然,这两部分的路总是能够用多米诺骨牌覆盖(把骨牌看作可以停在弯曲车道上的篷车).你也许愿意尝试一下,把这个巧妙的证明应用于尺寸,形状与此不同的矩阵,也可以考虑擦去不止两个方格的情况.