难铺的瓷砖


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

 

A A B B C
K K L L M C D
J T S U M N D
J Q S R R N E
I Q P P O O E
I H H G G F F

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

  铺砌理论作为组合几何中的一个范围广泛的领域,越来越受到人们的注目.要铺砌的平面可以是任何形状----"有限的或无限的",瓷砖也可以形形色色,而且问题可能会涉及不同形状的集合,而并非要求单一模式.不可能性证明还经常涉及以某种规定的方式,用两种或两种以上的颜色为某一平面着色.
  与多米诺骨牌相似的三维物体是砖块,其单位尺寸为1X2X4.用这种砖块"堆"成(空间铺砌)一个4X4X4的箱体并不困难,但是用这种砖块可否堆成一个6X6X6的箱体?这个问题完全可以应用布朗先生铺砌院子的问题的解法.设想把该立方体分成27个小立方体,每个为2X2X2.把这些阶为2的立方体交替涂上黑白两种颜色,好似一个三维的国际象棋棋盘.如果你把每种颜色的单位立方体的个数数一下,就会发现,一种颜色的立方体比另一种颜色的多八个.
  在那大立方体中,无论怎样放置砖块,不多不少总是恰恰"盖住"相同的数目的黑色和白色的单位立方体,但一种颜色的单位立方体比另一种颜色的多八个,最初的26块砖无论怎样放置,总会剩下同样颜色的八个单位立方体.因此无法安置第27块砖.如果不厌其烦地探讨所有可能的堆砌方式,以求证明这一点,这样做显然极其费事.
  堆砌理论仅是三维空间堆砌理论的一部分.关于空间堆砌问题,各种资料文献正日趋增多.它们提出了大量悬而未决,引人入胜的问题,有许多问题的解法可应用于商品的纸箱包装和堆仓等等.
  奇偶性在粒子物理学方面也起着很重要的作用.1957年,两名中国血统的美国物理学家(指杨振宁,李政道)因为他们在推翻著名的"宇称守恒定律"方面的贡献而获得诺贝尔奖金.但由于这一题目专业性太强,故此不做详述.但可以举一个有趣的硬币戏法的例子来说明奇偶性守恒的一种方式.
  往桌子上抛一把硬币,数一下正面朝上的有多少,若是偶数,则称正面朝上的硬币具有偶数性;若是奇数,则称其具有奇数性.现在把一对硬币翻身,再翻第二对,第三对,任你翻转多少对.你将惊奇地发现,无论翻转多少对,正面朝上的硬币的奇偶性始终不变.如果原来是奇数性,那么还是保持奇数性;如果原先是偶数性,则始终保持偶数性.
  利用这一点可以耍一个巧妙的魔术.你背过身去,请人随心所欲地把硬币一对一对地翻转,再请他用手盖住其中任何一枚.然后,你回过身来,瞧一瞧硬币,即可正确地说出他手掌下的硬币是正面朝上还是反面朝上.秘诀是开始时数一下正面朝上的硬币有多少,记住是奇数还是偶数.由于一对一对地将硬币翻转并不会影响其原来的奇偶性,所以你只要在最后再把正面朝上的硬币数一下,就可确定被盖住的那枚硬币是正面朝上还是反面朝上了.
  还有一个变相的问题:请他用手盖住两枚硬币,你再说出盖住的那一对硬币其朝上一面是否相同.许多心算扑克牌花样的巧妙魔术都是利用奇偶校验来设计的.