第二章6
62難鋪的瓷磚
布朗先生的院子裏鋪有40塊四方瓷磚，這些瓷磚已經破損老化，他想予以更新，他為修整院子選購新的瓷磚。可惜，目前商店裏隻供應長方形的瓷磚，每塊等於原來的兩塊。店主：“布朗先生，您需要幾塊？”布朗先生：“嗯，我要更換40塊方瓷磚，所以我估計需要20塊。”
布朗先生試著用剛買的新瓷磚鋪院子，結果弄得煩悶不堪。不管他怎樣努力，總是無法鋪好。
貝特西：“出了什麼問題？爸爸？”布朗先生：“這些該死的瓷磚，真叫人惱火。最後總是剩下兩個方格沒法鋪上瓷磚。”
布朗先生的女兒畫了一張院子的平麵圖，並且塗上了顏色，看上去好似一張棋盤。然後她沉思了幾分鍾。
貝特西：“啊哈！我看出症結的所在了。請設想每塊長方形瓷磚必定蓋住一個紅色的格子和一個白色的格子，問題就清楚了。”
這裏麵有什麼奧妙，你理解貝特西的意思嗎？
共有19個白色的格子和21個紅色的格子，所以鋪了19塊瓷磚後，總要剩下2個紅格沒有鋪，而一塊長方形瓷磚是無法蓋住2個紅格的。唯一的辦法是把最後一塊長方形瓷磚斷為兩塊。
布朗先生的女兒利用所謂“奇偶校驗”解答了鋪瓷磚問題。如果兩個數都是奇數或都是偶數，則稱其為具有相同的奇偶性，如果一個數是奇數，另一個數是偶數，則稱其具有相反的奇偶性，在組合幾何中，經常會遇到類似的情況。
在這個問題中，同色的兩個格子具有相同的奇偶性，異色的兩個格子具有相反的奇偶性。長方形瓷磚顯然隻能覆蓋具有相反奇偶性的一對格子。布朗小姐首先說明，把19塊長方形瓷磚在院子內鋪上後，隻有在剩下的兩個方格具有相反的奇偶性時，才能把最後一塊長方形瓷磚鋪上。由於剩下的兩個方格具有相同的奇偶性，因此無法鋪上最後一塊長方形瓷磚。所以用20塊長方形瓷磚來鋪滿院子是不可能的。
數學中許多著名的不可能性的證明都建立在奇偶校驗上，也許你很熟悉歐幾裏德的著名證明，2的平方根不可能是一個有理數，證明是這樣進行的：首先假設此平方根可以表示成一個既約的有理分數，則分子和分母不可能都是偶數，否則它就不是一個既約分數。分子，分母可能都是奇數或者一個是奇數，另一個是偶數。歐幾裏德證明接著論證此分數不可能屬於上述兩種情況，換句話說，分子和分母不可能具有相同的奇偶性或相反的奇偶性。而任何有理分數是兩者必居其一,因而反證了2的平方根不可能是一個有理數。
在鋪砌理論中，有許多必定要用奇偶校驗才能論證其不可能性的問題。上述問題隻是個極其簡單的例子，因為它僅僅涉及用多米諾骨牌，即簡單的，不平凡的波利米諾來鋪砌。布朗小姐的不可能性證明適用於符合下列要求的單位方格矩陣：這種矩陣若按照棋盤那樣塗色後，一種顏色的方格要比另一種顏色的方格至少多一個。
在上述問題中，可以把院子看作缺少兩個同色方格的一個6X7矩陣。顯然，如果缺少的兩個方格同色，20個多米諾骨牌無法覆蓋其餘的40個方格。一個有趣的並與此有關的問題是：如果缺少兩個顏色不同的方格，20個多米諾骨牌是否能夠覆蓋住那缺格的6X7矩陣？雖然奇偶校驗沒有證明其不可能性，但著並不意味著一定可以覆蓋。通過擦去一對異色的方格，可以生成所有可能的圖形。但若逐一加以研究則不勝其煩，因為各種可能的情況太多，以至於無法分析。對於所有的情況來說，是否有一種簡單的可能性證明？
有的，此證明既簡單又巧妙，為拉爾夫?戈莫裏妙手偶得之，他同樣也是利用了奇偶原理。假設此6X7矩陣有一條波及整個內部的閉合回路，寬度為一格。假設把閉合回路上任何兩個異色方格擦去，於是該閉合回路就一斷為二，每一部分都是由格數成偶數的異色方格組成。顯然，這兩部分的路總是能夠用多米諾骨牌覆蓋，你也許願意嚐試一下，把這個巧妙的證明應用於尺寸，形狀與此不同的矩陣，也可以考慮擦去不止兩個方格的情況。
鋪砌理論作為組合幾何中的一個範圍廣泛的領域,越來越受到人們的注目，要鋪砌的平麵可以是任何形狀，“有限的或無限的”，瓷磚也可以形形色色,而且問題可能會涉及不同形狀的集合，而並非要求單一模式。不可能性證明還經常涉及以某種規定的方式，用兩種或兩種以上的顏色為某一平麵著色。