魔方与“上帝之数”

卢昌海

1974年春天，匈牙利布达佩斯应用艺术学院的建筑学教授鲁比克萌生了一个有趣的念头，那就是设计一个教学工具来帮助学生直观地理解空间几何中的各种转动。经过思考，他决定制作一个由一些小方块组成的，各个面能随意转动的3×3×3的立方体。鲁比克为这一制作向匈牙利专利局申请了专利。这就是我们熟悉的魔方，也叫鲁比克方块。

6年后，鲁比克的魔方经过一位匈牙利商人兼业余数学家的牵头，打进了西欧及美国市场，并以惊人的速度成为风靡全球的新潮玩具。

魔方之畅销，最大的魔力就在于其数目惊人的颜色组合。一个魔方出厂时每个面各有一种颜色，总共有6种颜色，但这些颜色被打乱后，所能形成的组合数却多达4325亿亿个。如果我们将这些组合中的每一种都做成一个魔方，这些魔方排在一起，可以从地球一直排到250光年外的遥远星空——也就是说，如果我们在这样一排魔方的一端点上一盏灯，那么灯光要在250年后才能照到另一端！如果哪位勤勉的玩家想要尝试所有的组合，哪怕他不吃、不喝、不睡，每秒钟转出十种不同的组合，也要花1500亿年的时间才能如愿。与这样的组合数相比，广告商们常用的“成千上万”、“数以亿计”、“数以十亿计”等虚张声势、忽悠顾客的形容词反倒变成了难得的谦虚。

魔方的玩家多了，比赛自然是少不了的。自1981年起，魔方爱好者们开始举办世界性的魔方大赛，从而开始缔造自己的世界纪录。截至2013年，复原魔方的最快纪录已经达到了令人吃惊的5.55秒。当然，单次复原的纪录存在一定的偶然性。为了减少这种偶然性，自2003年起，魔方大赛的冠军改由多次复原的平均成绩来决定，截至2013年，这一平均成绩的世界纪录为6.54秒。这些纪录的出现，表明魔方虽有天文数字般的颜色组合，但只要掌握窍门，将任何一种给定的颜色组合复原所需的转动次数却很可能并不多。

那么，最少需要多少次转动，才能确保无论什么样的颜色组合都能被复原呢？这个问题引起了很多人尤其是数学家们的兴趣。这个复原任意组合所需的最少转动次数被数学家们戏称为“上帝之数”，而魔方这个玩具世界的宠儿则由于 “上帝之数”而一举侵入了学术界。

要研究“上帝之数”，当然首先要研究魔方的复原方法。在玩魔方的过程中，将任何一种给定的颜色组合复原都是很容易的，不过魔方玩家们所用的复原方法是便于人脑掌握的方法，却不是转动次数最少的，因此无助于寻找“上帝之数”。寻找转动次数最少的方法是一个有一定难度的数学问题。早在20世纪90年代中期，人们就有了较实用的算法，可以用平均15分钟左右的时间找出复原一种给定的颜色组合的最少转动次数。从理论上讲，如果有人能对每一种颜色组合都找出这样的最少转动次数，那么这些转动次数中最大的一个无疑就是“上帝之数”了。但可惜的是，“4325亿亿”这个巨大数字成了人们窥视“上帝之数”的拦路虎。如果采用上面提到的算法，哪怕用一亿台计算机同时进行，也要用超过1000万年的时间才能完成。

看来蛮干是行不通的。数学家们于是求助于他们的老本行——数学。魔方的颜色组合虽然千变万化，其实都是由一系列基本操作——转动——产生的。对于那些操作，数学家们的“武器库”中有一种非常有效的工具来对付它，这工具叫作群论，在它的帮助下，巧妙的思路出现了。

1992年，德国数学家科先巴提出了一种寻找魔方复原方法的新思路。他发现，在魔方的基本转动方式中，有一部分可以自成系列，通过这部分转动可以形成将近200亿种颜色组合。利用这200亿种颜色组合，科先巴将魔方的复原问题分解成两个步骤：第一步是将任意一种颜色组合转变为那200亿种颜色组合之一，第二步则是将那200亿种颜色组合复原。如果我们把魔方的复原比作是让一条汪洋大海中的小船驶往一个固定目的地，那么科先巴提出的那200亿种颜色组合就好比是一片特殊水域——一片比那个固定目的地大了200亿倍的特殊水域。他提出的两个步骤就好比是让小船首先驶往那片特殊水域，然后再从那里驶往那个固定目的地。在汪洋大海中寻找一片巨大的特殊水域，显然要比直接寻找那个小小的目的地容易得多，这就是科先巴新思路的巧妙之处。

3年之后，有人利用科先巴的新思路给出了第一个估算结果。此人名叫里德，是美国佛罗里达大学的数学家。1995年，里德通过计算发现，最多经过12次转动，就可以将魔方的任意一种颜色组合转变为科先巴新思路中那200亿种颜色组合之一;而最多经过18次转动，就可以将那200亿种颜色组合中的任意一种复原。这表明，最多经过12+18=30次转动，就可以将魔方的任意一种颜色组合复原。

在得到上述结果后，里德很快对自己的估算作了改进，将结果从30减少为29，这表明“上帝之数”不会超过29。此后随着计算机技术的发展，数学家们对里德的结果又作出了进一步改进。2006年，奥地利开普勒大学符号计算研究所的博士生拉杜将结果推进到了27。2007年，美国东北大学的计算机科学家孔克拉和库伯曼又将结果推进到了26。

这些计算表明，“上帝之数”不会超过26。但是，所有这些计算的最大优点——利用科先巴新思路中那片特殊水域——同时也成了它最致命的弱点，因为它们给出的复原方法都必须经过那片特殊水域。可事实上，很多颜色组合的最佳复原方法根本就不经过那片特殊水域。因此，用科先巴新思路得到的复原方法未必是最佳的，由此对“上帝之数”所做的估计也极有可能是高估。

可是，如果不引进科先巴新思路中的特殊水域，计算量又实在太大，怎么办呢？数学家们决定采取折中手段，即扩大那片特殊水域的面积。因为特殊水域越大，最佳复原路径恰好经过它的可能性也就越大（当然，计算量也会有相应的增加）。2008年，研究“上帝之数”长达15年之久的计算机高手罗基奇运用了相当于将科先巴新思路中的特殊水域扩大几千倍的巧妙方法，在短短几个月的时间内对“上帝之数”连续发动了四次猛烈攻击，将它的估值从25一直压缩到了22。

由此我们进一步知道，“上帝之数”一定不会超过22。但是，罗基奇虽然将科先巴新思路中的特殊水域扩展得很大，终究仍有一些颜色组合的最佳复原方法是无需经过那片特殊水域的，因此，“上帝之数”很可能比22更小。那么，它究竟是多少呢？种种迹象表明，它极有可能是20。这是因为，人们在过去这么多年的所有努力，其中包括罗基奇直接计算过的大约4000万亿种颜色组合中，都从未遇到过任何必须用20次以上转动才能复原的颜色组合，这表明“上帝之数”很可能不大于20;同时，人们已经发现了几万种颜色组合，它们必须要用20次转动才能复原，这表明“上帝之数”不可能小于20。将这两方面综合起来，数学家们普遍相信，“上帝之数”的真正数值就是20。

2010年8月，这个游戏与数学交织而成的神秘的“上帝之数”终于水落石出：研究“上帝之数”的元老科先巴、新秀罗基奇，以及另两位合作者——戴维森和德斯里奇——宣布了对“上帝之数”是20的证明。

因此，现在我们可以用数学特有的确定性来宣布“上帝之数”的数值了，那就是：20。 □endprint