魔方與上帝之?dāng)?shù)

2008年7月，來(lái)自世界各地的很多最優(yōu)秀的魔方玩家聚集在捷克共和國(guó)中部的帕爾杜比采，參加魔方界的重要賽事：捷克公開(kāi)賽。在這次比賽上，荷蘭玩家阿克斯迪杰克創(chuàng)下了一個(gè)驚人的紀(jì)錄：只用7.08秒就復(fù)原了一個(gè)顏色被徹底打亂的魔方。無(wú)獨(dú)有偶，在這一年的8月，人們?cè)谘芯磕Х奖澈蟮臄?shù)學(xué)問(wèn)題上也取得了重要進(jìn)展。

風(fēng)靡世界的玩具

1974年春天，匈牙利布達(dá)佩斯應(yīng)用藝術(shù)學(xué)院的建筑學(xué)教授魯比克萌生了一個(gè)有趣的念頭，他想設(shè)計(jì)一個(gè)教學(xué)工具來(lái)幫助學(xué)生直觀地理解空間幾何的各種轉(zhuǎn)動(dòng)。經(jīng)過(guò)思考，他決定制作一個(gè)由一些小方塊組成的，各個(gè)面能隨意轉(zhuǎn)動(dòng)的3×3×3的立方體。這樣的立方體可以很方便地演示各種空間轉(zhuǎn)動(dòng)。

這個(gè)想法雖好，實(shí)踐起來(lái)卻面臨一個(gè)棘手的問(wèn)題，即如何才能讓這樣一個(gè)立方體的各個(gè)面能隨意轉(zhuǎn)動(dòng)？魯比克想了很多點(diǎn)子，比如用磁鐵或橡皮筋連接各個(gè)小方塊，但都不成功。那年夏天的一個(gè)午后，他在多瑙河畔乘涼，他的眼光不經(jīng)意地落在了河畔的鵝卵石上。忽然，他心中閃過(guò)一個(gè)新的設(shè)想：用類似于鵝卵石那樣的圓形表面來(lái)處理立方體的內(nèi)部結(jié)構(gòu)。這一新設(shè)想成功了，魯比克很快完成了自己的設(shè)計(jì)，并向匈牙利專利局申請(qǐng)了專利。這一設(shè)計(jì)就是我們都很熟悉的魔方，也叫魯比克方塊。

6年后，魯比克的魔方經(jīng)過(guò)一位匈牙利商人兼業(yè)余數(shù)學(xué)家的牽頭，打進(jìn)了西歐及美國(guó)市場(chǎng)，并以驚人的速度成為風(fēng)靡全球的新潮玩具。在此后的25年間，魔方的銷量超過(guò)了3億個(gè)。在魔方玩家中，既有牙牙學(xué)語(yǔ)的孩子，也有跨國(guó)公司的老總。魔方雖未如魯比克設(shè)想的那樣成為一種空間幾何的教學(xué)工具，卻變成了有史以來(lái)最暢銷的玩具。

魔方之暢銷，最大的魔力就在于其數(shù)目驚人的顏色組合。一個(gè)魔方出廠時(shí)每個(gè)面各有一種顏色，總共有六種顏色，但這些顏色被打亂后，所能形成的組合數(shù)卻多達(dá)4325億億。我們可以很有把握地說(shuō)，假如不掌握訣竅地隨意亂轉(zhuǎn)，一個(gè)人哪怕從宇宙大爆炸之初就開(kāi)始玩魔方，也幾乎沒(méi)有任何希望將一個(gè)色彩被打亂的魔方復(fù)原。

魔方與上帝之?dāng)?shù)

自1981年起，魔方愛(ài)好者們開(kāi)始舉辦世界性的魔方大賽，從而開(kāi)始締造自己的世界紀(jì)錄。這一紀(jì)錄被不斷地刷新著。當(dāng)然，單次復(fù)原的紀(jì)錄存在一定的偶然性，為了減少這種偶然性，自2003年起，魔方大賽的冠軍改由多次復(fù)原的平均成績(jī)來(lái)決定，目前這一平均成績(jī)的世界紀(jì)錄為11.28秒。這些紀(jì)錄的出現(xiàn)，表明魔方雖有天文數(shù)字般的顏色組合，但只要掌握竅門(mén)，將任何一種組合復(fù)原所需的轉(zhuǎn)動(dòng)次數(shù)卻并不多。

那么，最少需要多少次轉(zhuǎn)動(dòng)，才能確保無(wú)論什么樣的顏色組合都能被復(fù)原呢？這個(gè)問(wèn)題引起了很多人，尤其是數(shù)學(xué)家的興趣。這個(gè)復(fù)原任意組合所需的最少轉(zhuǎn)動(dòng)次數(shù)被數(shù)學(xué)家們戲稱為“上帝之?dāng)?shù)”。

要研究上帝之?dāng)?shù)，首先當(dāng)然要研究魔方的復(fù)原方法。早在20世紀(jì)90年代中期，人們就有了較實(shí)用的算法，可以用平均15分鐘左右的時(shí)間找出復(fù)原一種給定顏色組合的最少轉(zhuǎn)動(dòng)次數(shù)。

從理論上講，如果有人能對(duì)每一種顏色組合都找出這樣的最少轉(zhuǎn)動(dòng)次數(shù)，那么這些轉(zhuǎn)動(dòng)次數(shù)中最大的一個(gè)無(wú)疑就是上帝之?dāng)?shù)。但可惜的是，4325億億這個(gè)巨大的數(shù)字成為人們窺視上帝之?dāng)?shù)的攔路虎。如果采用上面提到的算法，哪怕用一億臺(tái)機(jī)器同時(shí)計(jì)算，也要超過(guò)一千萬(wàn)年的時(shí)間才能完成。

看來(lái)蠻干是行不通的，數(shù)學(xué)家們于是便求助于他們的老本行：數(shù)學(xué)。從數(shù)學(xué)的角度看，魔方的顏色組合雖然千變?nèi)f化，其實(shí)都是由一系列基本的操作即轉(zhuǎn)動(dòng)產(chǎn)生的，而且那些操作還具有幾個(gè)非常簡(jiǎn)單的特點(diǎn)，比如任何一個(gè)操作都有一個(gè)相反的操作（比如與順時(shí)針轉(zhuǎn)動(dòng)相反的操作就是逆時(shí)針轉(zhuǎn)動(dòng)）。對(duì)于這樣的操作，數(shù)學(xué)家們的軍火庫(kù)中有一種非常有效的工具來(lái)對(duì)付它，這工具叫做群論，它早在魔方問(wèn)世之前一百四十多年就已出現(xiàn)了。

對(duì)魔方研究來(lái)說(shuō)，群論有一個(gè)非常重要的優(yōu)點(diǎn)，就是它可以充分利用魔方的對(duì)稱性。我們前面提到4325億億這個(gè)巨大數(shù)字時(shí)，其實(shí)有一個(gè)疏漏，那就是并未考慮到魔方作為一個(gè)立方體所具有的對(duì)稱性。由此導(dǎo)致的結(jié)果，是那4325億億種顏色組合中有很多其實(shí)是完全相同的，只是從不同的角度去看（比如讓不同的面朝上）而已。因此，4325億億這個(gè)令人望而生畏的數(shù)字實(shí)際上是“注水豬肉”。那么，這“豬肉”中的“水分”占多大比例呢？說(shuō)出來(lái)嚇大家一跳：占了將近99%！換句話說(shuō)，僅憑對(duì)稱性一項(xiàng)，數(shù)學(xué)家們就可以把魔方的顏色組合減少兩個(gè)數(shù)量級(jí)。

但減少兩個(gè)數(shù)量級(jí)對(duì)于尋找上帝之?dāng)?shù)來(lái)說(shuō)還遠(yuǎn)遠(yuǎn)不夠，因?yàn)槟遣贿^(guò)是將前面提到的1000萬(wàn)年的時(shí)間減少為了10萬(wàn)年。對(duì)于解決一個(gè)數(shù)學(xué)問(wèn)題來(lái)說(shuō)，十萬(wàn)年顯然還是太長(zhǎng)了。因此為了尋找上帝之?dāng)?shù)，人們還需要尋找更巧妙的思路。幸運(yùn)的是，群論這一工具的威力遠(yuǎn)不只是用來(lái)分析像立方體的對(duì)稱性那樣顯而易見(jiàn)的東西，在它的幫助下，新的思路很快就出現(xiàn)了。

尋找上帝之?dāng)?shù)

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

但即便如此，要用科先巴的方法對(duì)上帝之?dāng)?shù)進(jìn)行估算仍不是一件容易的事。尤其是，要想進(jìn)行快速的計(jì)算，最好是將復(fù)原那200億種顏色組合的最少轉(zhuǎn)動(dòng)次數(shù)存儲(chǔ)在計(jì)算機(jī)的內(nèi)存中，這大約需要300兆的內(nèi)存。300兆在今天看來(lái)是一個(gè)不太大的數(shù)目，但在科先巴提出新思路的那年，普通計(jì)算機(jī)的內(nèi)存連它的十分之一都遠(yuǎn)遠(yuǎn)不到。因此直到3年后，才有人利用科先巴的方法給出了第一個(gè)估算結(jié)果。此人名叫里德，是美國(guó)佛羅里達(dá)大學(xué)的數(shù)學(xué)家。1995年，里德通過(guò)計(jì)算發(fā)現(xiàn)，最多經(jīng)過(guò)12次轉(zhuǎn)動(dòng)，就可以將魔方的任意一種顏色組合變?yōu)榭葡劝湍?00億種組合之一;而最多經(jīng)過(guò)18次轉(zhuǎn)動(dòng)，就可以將那200億種組合中的任意一種復(fù)原。這表明，最多經(jīng)過(guò)12+18=30次轉(zhuǎn)動(dòng)，就可以將魔方的任意一種顏色組合復(fù)原。

在得到上述結(jié)果后，里德很快對(duì)自己的計(jì)算作了改進(jìn)，將結(jié)果從30減少為29，這表明上帝之?dāng)?shù)不會(huì)超過(guò)29。此后隨著計(jì)算機(jī)技術(shù)的發(fā)展，數(shù)學(xué)家們對(duì)里德的結(jié)果又作了進(jìn)一步的改進(jìn)，但進(jìn)展并不迅速。直到11年后的2006年，奧地利開(kāi)普勒大學(xué)符號(hào)計(jì)算研究所的博士生拉杜才將結(jié)果推進(jìn)到了27。第二年，即2007年，美國(guó)東北大學(xué)的計(jì)算機(jī)科學(xué)家孔克拉和庫(kù)伯曼又將結(jié)果推進(jìn)到了26，他們的工作采用了并行計(jì)算系統(tǒng)，所用內(nèi)存高達(dá)700萬(wàn)兆，所耗計(jì)算時(shí)間則長(zhǎng)達(dá)8000小時(shí)（相當(dāng)于將近一年的24小時(shí)不停歇計(jì)算）。這些計(jì)算結(jié)果表明，上帝之?dāng)?shù)不會(huì)超過(guò)26。2008年，研究上帝之?dāng)?shù)長(zhǎng)達(dá)15年之久的計(jì)算機(jī)高手羅基奇運(yùn)用了相當(dāng)于將科先巴的特殊水域擴(kuò)大幾千倍的巧妙方法，在短短幾個(gè)月的時(shí)間內(nèi)對(duì)上帝之?dāng)?shù)連續(xù)發(fā)動(dòng)了4次猛烈攻擊，將它的估計(jì)值從25一直壓縮到了22。截至今日，這是全世界范圍內(nèi)的最佳結(jié)果。

因此，現(xiàn)在我們已經(jīng)知道，上帝之?dāng)?shù)一定不超過(guò)22。但是，羅基奇的特殊水域雖然很大，終究仍有很多顏色組合的最佳復(fù)原方法是無(wú)須經(jīng)過(guò)那片特殊水域的，因此，上帝之?dāng)?shù)很可能比22更小。那么，它究竟是多少呢？人們雖然還無(wú)法確知，但種種跡象表明，它極有可能是20。這是因?yàn)椋藗冊(cè)谶^(guò)去這么多年的所有努力中，都從未遇到任何必須用20次以下轉(zhuǎn)動(dòng)才能復(fù)原的顏色組合，這表明“上帝之?dāng)?shù)”很可能不大于20。

另一方面，人們已經(jīng)發(fā)現(xiàn)了幾萬(wàn)種顏色組合，它們必須要用20次轉(zhuǎn)動(dòng)才能復(fù)原，這表明上帝之?dāng)?shù)不可能小于20。將這兩方面綜合起來(lái)，數(shù)學(xué)家們普遍相信，上帝之?dāng)?shù)的真正數(shù)值就是20。當(dāng)然，“上帝”也許是微妙的，我們誰(shuí)也無(wú)法保證它是否會(huì)在某個(gè)角落為我們留下驚訝，我們唯一有理由相信的也許是：這個(gè)游戲與數(shù)學(xué)交織而成的神秘的上帝之?dāng)?shù)距離它水落石出的那一天已不太遙遠(yuǎn)了。