让人烦恼的瓷砖
奇偶检验
布朗先生的女儿应用所谓“奇偶检验”解决了铺砖问题。
如果两个数字都是奇数或都是偶敷,它们被称为同奇偶:如果一个是奇数而另一个是偶数,则称为相对奇偶。在组合几何中也要经常遇到相同的情况。
在本问题中,两块同颜色是同奇偶,两块不同颜色是相对奇偶。显然一块矩形砖只覆盖一对相对奇偶方砖。这个姑娘让我们看到,当19块矩形砖铺上后,剩余的两块只有是相对奇偶才能被矩形砖覆盖,由于剩下的两块必然是同奇偶,它们不能被矩形砖覆盖。所以院子铺矩形砖是不可能的。
数学中许多不可能性证明也依赖奇偶检验。你熟悉的著名欧几里德证明;2的平方根不可能是有理数。这个证明的获得首先假设根可以用最简有理分式来表示,分子和分母不可能都是偶数,否则分式就不是最简式。所以,它们只能是奇数,或一个是奇数、另一个是偶数。欧几里德的证明显示,这个分式二者都不是,既不都是奇数,又不相对奇偶。而每—个有理分式都应是二者之一,所以2的平方根不是有理数。假如不是应用奇偶检验,很难证明铺砖的不可能性问题。
这个问题尤其简单是因为它包括在多米诺(domino)骨牌中最简单的一种polyomino(把一系列单位块拼在一起),这个姑娘的不可能性证明可以适用于任何由单位块构成的矩阵中,当矩阵被棋盘似地涂色后,一种颜色的单位块比另一种颜色的至少多一块。在我们的问题中,院子可以看做6X7的矩阵,缺了2个同颜色的块。显然,剩下的40块木船由20块“多米诺骨牌”覆盖。一个有趣的相关问题是:如果移去的2块是不同颜色的,20块“多米诺骨牌”就可以檀盖了吗?奇偶检验不能证明其不可能性,但这并不意味着可能性永远存在着。无疑要移动一对对的不同颜色的块来检查每一种可能的模式,这要分析过多的可能情况。有没有简单的可能性证明呢?有。它简洁,奇巧,是由Ralph.Gomory的灵感解决的。
假设6X7长方形中有一个封闭路径,一小格宽。见图5.现在将路径中任意两个不同颜色的小块移走,这将路径分为两部分,每部分都包括偶数个颜色相同的小格,很明显这部分能被“多米诺骨脾”覆盖,所以这个问题总是有解的。你或许很想应用一下这个巧妙的证明于任意大小、形状的矩阵且缺两个以上的小块。
“铺砖”理论是一种有趣的大面积的组合几何,铺设的区域可以是任意形状的——有限的或无限的,砖的形状同样也可以变化。问题中砖的形状也可以不是同一形状的,不可能性证明中经常用两种以上颜色标记特定区域。
三维多米诺骨牌是lX2X4的块,用这种块很容易装一个4X4X4的盒子,但用这种块能装6X6X6的盒子吗?这个问题也用布朗先生庭院问题方式来解答。假如把这个立方体分为27个小立方体,每个是2X2X2,黑白相间的标识这些2度立方体,你会发现,一种颜色比另一颜色多8个立方体。
不论一个块用这种颜色的小块怎样堆积。它总是占据同样数量的黑块和白块,但由于一种颜色的块比另一种颜色的多8立方,不论前26块怎样放总要剩8立方同颜色块,所以它们不能被第27块覆盖,若要通过详尽检查每种可能的拼装方式来证明其不可能性将会是超乎寻常的困难。
块拼装理论仅仅是三维空间堆积理论的一部分。在空间拼装课题上,尽管有许多悬而未解的问题,但已有大量的论文产生。许多问题已应用到商品的包装及仓库商品的贮存等等方面。
奇偶性在核物理方面起着重要作用。1957年两名华裔美国物理学家获得诺贝尔奖就是由于他们的工作推翻了著名的“奇偶守恒‘’定律。由于其太高的科技水平而不在此引入。但这里有一个简单的硬币小戏法,可以说明奇偶的守恒。
在桌上扔一把硬币,然后数一下呈现正面的硬币数。若是偶数。我们说正面具有偶数性,若是奇数,我们说正面具有奇数性。然后翻转一对硬币,再一对,再一对,随意选择。你可以发现,不管翻转多少对,正面的奇偶性是守恒的。如果开始是奇数,结束时还是奇数:如果开始时是偶数,结束时仍是偶数。
这就是这个聪明的小魔术的基础。你转过身去,让一个人随意一对对翻转硬币,再让他用手盖上任何一个硬币,你转过来,看一下这些硬币,就能准确地告诉他手下的硬币是正面还是反面。秘密就是最初数一下正面的数量并记下来。不管正面数是偶数还是奇数,固为成对翻转不影响其奇偶性,你只要在最后查一下正面敷就能知道掩藏的硬币是正面还是反面。
作为一种推广,还可以让某人用手盖上两个硬币,你可以说出被掩盖的硬币是同面还是互为反面。
许多明面的纸牌戏法都可由这种奇偶检验变化得来。