魔方與“上帝之數(shù)”

盧昌海

1974年春天，匈牙利布達佩斯應用藝術學院的建筑學教授魯比克萌生了一個有趣的念頭，那就是設計一個教學工具來幫助學生直觀地理解空間幾何中的各種轉動。經(jīng)過思考，他決定制作一個由一些小方塊組成的，各個面能隨意轉動的3×3×3的立方體。魯比克為這一制作向匈牙利專利局申請了專利。這就是我們熟悉的魔方，也叫魯比克方塊。

6年后，魯比克的魔方經(jīng)過一位匈牙利商人兼業(yè)余數(shù)學家的牽頭，打進了西歐及美國市場，并以驚人的速度成為風靡全球的新潮玩具。

魔方之暢銷，最大的魔力就在于其數(shù)目驚人的顏色組合。一個魔方出廠時每個面各有一種顏色，總共有6種顏色，但這些顏色被打亂后，所能形成的組合數(shù)卻多達4325億億個。如果我們將這些組合中的每一種都做成一個魔方，這些魔方排在一起，可以從地球一直排到250光年外的遙遠星空——也就是說，如果我們在這樣一排魔方的一端點上一盞燈，那么燈光要在250年后才能照到另一端！如果哪位勤勉的玩家想要嘗試所有的組合，哪怕他不吃、不喝、不睡，每秒鐘轉出十種不同的組合，也要花1500億年的時間才能如愿。與這樣的組合數(shù)相比，廣告商們常用的“成千上萬”、“數(shù)以億計”、“數(shù)以十億計”等虛張聲勢、忽悠顧客的形容詞反倒變成了難得的謙虛。

魔方的玩家多了，比賽自然是少不了的。自1981年起，魔方愛好者們開始舉辦世界性的魔方大賽，從而開始締造自己的世界紀錄。截至2013年，復原魔方的最快紀錄已經(jīng)達到了令人吃驚的5.55秒。當然，單次復原的紀錄存在一定的偶然性。為了減少這種偶然性，自2003年起，魔方大賽的冠軍改由多次復原的平均成績來決定，截至2013年，這一平均成績的世界紀錄為6.54秒。這些紀錄的出現(xiàn)，表明魔方雖有天文數(shù)字般的顏色組合，但只要掌握竅門，將任何一種給定的顏色組合復原所需的轉動次數(shù)卻很可能并不多。

那么，最少需要多少次轉動，才能確保無論什么樣的顏色組合都能被復原呢？這個問題引起了很多人尤其是數(shù)學家們的興趣。這個復原任意組合所需的最少轉動次數(shù)被數(shù)學家們戲稱為“上帝之數(shù)”，而魔方這個玩具世界的寵兒則由于 “上帝之數(shù)”而一舉侵入了學術界。

要研究“上帝之數(shù)”，當然首先要研究魔方的復原方法。在玩魔方的過程中，將任何一種給定的顏色組合復原都是很容易的，不過魔方玩家們所用的復原方法是便于人腦掌握的方法，卻不是轉動次數(shù)最少的，因此無助于尋找“上帝之數(shù)”。尋找轉動次數(shù)最少的方法是一個有一定難度的數(shù)學問題。早在20世紀90年代中期，人們就有了較實用的算法，可以用平均15分鐘左右的時間找出復原一種給定的顏色組合的最少轉動次數(shù)。從理論上講，如果有人能對每一種顏色組合都找出這樣的最少轉動次數(shù)，那么這些轉動次數(shù)中最大的一個無疑就是“上帝之數(shù)”了。但可惜的是，“4325億億”這個巨大數(shù)字成了人們窺視“上帝之數(shù)”的攔路虎。如果采用上面提到的算法，哪怕用一億臺計算機同時進行，也要用超過1000萬年的時間才能完成。

看來蠻干是行不通的。數(shù)學家們于是求助于他們的老本行——數(shù)學。魔方的顏色組合雖然千變萬化，其實都是由一系列基本操作——轉動——產(chǎn)生的。對于那些操作，數(shù)學家們的“武器庫”中有一種非常有效的工具來對付它，這工具叫作群論，在它的幫助下，巧妙的思路出現(xiàn)了。

1992年，德國數(shù)學家科先巴提出了一種尋找魔方復原方法的新思路。他發(fā)現(xiàn)，在魔方的基本轉動方式中，有一部分可以自成系列，通過這部分轉動可以形成將近200億種顏色組合。利用這200億種顏色組合，科先巴將魔方的復原問題分解成兩個步驟：第一步是將任意一種顏色組合轉變?yōu)槟?00億種顏色組合之一，第二步則是將那200億種顏色組合復原。如果我們把魔方的復原比作是讓一條汪洋大海中的小船駛往一個固定目的地，那么科先巴提出的那200億種顏色組合就好比是一片特殊水域——一片比那個固定目的地大了200億倍的特殊水域。他提出的兩個步驟就好比是讓小船首先駛往那片特殊水域，然后再從那里駛往那個固定目的地。在汪洋大海中尋找一片巨大的特殊水域，顯然要比直接尋找那個小小的目的地容易得多，這就是科先巴新思路的巧妙之處。

3年之后，有人利用科先巴的新思路給出了第一個估算結果。此人名叫里德，是美國佛羅里達大學的數(shù)學家。1995年，里德通過計算發(fā)現(xiàn)，最多經(jīng)過12次轉動，就可以將魔方的任意一種顏色組合轉變?yōu)榭葡劝托滤悸分心?00億種顏色組合之一;而最多經(jīng)過18次轉動，就可以將那200億種顏色組合中的任意一種復原。這表明，最多經(jīng)過12+18=30次轉動，就可以將魔方的任意一種顏色組合復原。

在得到上述結果后，里德很快對自己的估算作了改進，將結果從30減少為29，這表明“上帝之數(shù)”不會超過29。此后隨著計算機技術的發(fā)展，數(shù)學家們對里德的結果又作出了進一步改進。2006年，奧地利開普勒大學符號計算研究所的博士生拉杜將結果推進到了27。2007年，美國東北大學的計算機科學家孔克拉和庫伯曼又將結果推進到了26。

這些計算表明，“上帝之數(shù)”不會超過26。但是，所有這些計算的最大優(yōu)點——利用科先巴新思路中那片特殊水域——同時也成了它最致命的弱點，因為它們給出的復原方法都必須經(jīng)過那片特殊水域?？墒聦嵣?，很多顏色組合的最佳復原方法根本就不經(jīng)過那片特殊水域。因此，用科先巴新思路得到的復原方法未必是最佳的，由此對“上帝之數(shù)”所做的估計也極有可能是高估。

可是，如果不引進科先巴新思路中的特殊水域，計算量又實在太大，怎么辦呢？數(shù)學家們決定采取折中手段，即擴大那片特殊水域的面積。因為特殊水域越大，最佳復原路徑恰好經(jīng)過它的可能性也就越大（當然，計算量也會有相應的增加）。2008年，研究“上帝之數(shù)”長達15年之久的計算機高手羅基奇運用了相當于將科先巴新思路中的特殊水域擴大幾千倍的巧妙方法，在短短幾個月的時間內對“上帝之數(shù)”連續(xù)發(fā)動了四次猛烈攻擊，將它的估值從25一直壓縮到了22。

由此我們進一步知道，“上帝之數(shù)”一定不會超過22。但是，羅基奇雖然將科先巴新思路中的特殊水域擴展得很大，終究仍有一些顏色組合的最佳復原方法是無需經(jīng)過那片特殊水域的，因此，“上帝之數(shù)”很可能比22更小。那么，它究竟是多少呢？種種跡象表明，它極有可能是20。這是因為，人們在過去這么多年的所有努力，其中包括羅基奇直接計算過的大約4000萬億種顏色組合中，都從未遇到過任何必須用20次以上轉動才能復原的顏色組合，這表明“上帝之數(shù)”很可能不大于20;同時，人們已經(jīng)發(fā)現(xiàn)了幾萬種顏色組合，它們必須要用20次轉動才能復原，這表明“上帝之數(shù)”不可能小于20。將這兩方面綜合起來，數(shù)學家們普遍相信，“上帝之數(shù)”的真正數(shù)值就是20。

2010年8月，這個游戲與數(shù)學交織而成的神秘的“上帝之數(shù)”終于水落石出：研究“上帝之數(shù)”的元老科先巴、新秀羅基奇，以及另兩位合作者——戴維森和德斯里奇——宣布了對“上帝之數(shù)”是20的證明。

因此，現(xiàn)在我們可以用數(shù)學特有的確定性來宣布“上帝之數(shù)”的數(shù)值了，那就是：20。 □endprint