魔方与上帝之数

2008年7月，来自世界各地的很多最优秀的魔方玩家聚集在捷克共和国中部的帕尔杜比采，参加魔方界的重要赛事：捷克公开赛。在这次比赛上，荷兰玩家阿克斯迪杰克创下了一个惊人的纪录:只用7.08秒就复原了一个颜色被彻底打乱的魔方。无独有偶，在这一年的8月，人们在研究魔方背后的数学问题上也取得了重要进展。
　　
　　风靡世界的玩具
　　
　　1974年春天，匈牙利布达佩斯应用艺术学院的建筑学教授鲁比克萌生了一个有趣的念头，他想设计一个教学工具来帮助学生直观地理解空间几何的各种转动。经过思考，他决定制作一个由一些小方块组成的，各个面能随意转动的3×3×3的立方体。这样的立方体可以很方便地演示各种空间转动。
　　这个想法虽好，实践起来却面临一个棘手的问题，即如何才能让这样一个立方体的各个面能随意转动？鲁比克想了很多点子，比如用磁铁或橡皮筋连接各个小方块，但都不成功。那年夏天的一个午后，他在多瑙河畔乘凉，他的眼光不经意地落在了河畔的鹅卵石上。忽然，他心中闪过一个新的设想：用类似于鹅卵石那样的圆形表面来处理立方体的内部结构。这一新设想成功了,鲁比克很快完成了自己的设计,并向匈牙利专利局申请了专利。这一设计就是我们都很熟悉的魔方，也叫鲁比克方块。
　　6年后，鲁比克的魔方经过一位匈牙利商人兼业余数学家的牵头，打进了西欧及美国市场，并以惊人的速度成为风靡全球的新潮玩具。在此后的25年间，魔方的销量超过了3亿个。在魔方玩家中，既有牙牙学语的孩子，也有跨国公司的老总。魔方虽未如鲁比克设想的那样成为一种空间几何的教学工具，却变成了有史以来最畅销的玩具。
　　魔方之畅销，最大的魔力就在于其数目惊人的颜色组合。一个魔方出厂时每个面各有一种颜色，总共有六种颜色，但这些颜色被打乱后，所能形成的组合数却多达4325亿亿。我们可以很有把握地说，假如不掌握诀窍地随意乱转，一个人哪怕从宇宙大爆炸之初就开始玩魔方，也几乎没有任何希望将一个色彩被打乱的魔方复原。
　　
　　魔方与上帝之数
　　
　　自1981年起，魔方爱好者们开始举办世界性的魔方大赛，从而开始缔造自己的世界纪录。这一纪录被不断地刷新着。当然，单次复原的纪录存在一定的偶然性，为了减少这种偶然性，自2003年起，魔方大赛的冠军改由多次复原的平均成绩来决定，目前这一平均成绩的世界纪录为11.28秒。这些纪录的出现，表明魔方虽有天文数字般的颜色组合，但只要掌握窍门，将任何一种组合复原所需的转动次数却并不多。
　　那么，最少需要多少次转动，才能确保无论什么样的颜色组合都能被复原呢？这个问题引起了很多人，尤其是数学家的兴趣。这个复原任意组合所需的最少转动次数被数学家们戏称为“上帝之数”。
　　要研究上帝之数，首先当然要研究魔方的复原方法。早在20世纪90年代中期，人们就有了较实用的算法，可以用平均15分钟左右的时间找出复原一种给定颜色组合的最少转动次数。
　　从理论上讲，如果有人能对每一种颜色组合都找出这样的最少转动次数，那么这些转动次数中最大的一个无疑就是上帝之数。但可惜的是，4325亿亿这个巨大的数字成为人们窥视上帝之数的拦路虎。如果采用上面提到的算法，哪怕用一亿台机器同时计算，也要超过一千万年的时间才能完成。
　　看来蛮干是行不通的，数学家们于是便求助于他们的老本行：数学。从数学的角度看，魔方的颜色组合虽然千变万化，其实都是由一系列基本的操作即转动产生的，而且那些操作还具有几个非常简单的特点，比如任何一个操作都有一个相反的操作(比如与顺时针转动相反的操作就是逆时针转动)。对于这样的操作，数学家们的军火库中有一种非常有效的工具来对付它，这工具叫做群论，它早在魔方问世之前一百四十多年就已出现了。
　　对魔方研究来说，群论有一个非常重要的优点，就是它可以充分利用魔方的对称性。我们前面提到4325亿亿这个巨大数字时，其实有一个疏漏，那就是并未考虑到魔方作为一个立方体所具有的对称性。由此导致的结果，是那4325亿亿种颜色组合中有很多其实是完全相同的，只是从不同的角度去看(比如让不同的面朝上)而已。因此，4325亿亿这个令人望而生畏的数字实际上是“注水猪肉”。那么，这“猪肉”中的“水分”占多大比例呢？说出来吓大家一跳：占了将近99%！换句话说，仅凭对称性一项，数学家们就可以把魔方的颜色组合减少两个数量级。
　　但减少两个数量级对于寻找上帝之数来说还远远不够，因为那不过是将前面提到的1000万年的时间减少为了10万年。对于解决一个数学问题来说，十万年显然还是太长了。因此为了寻找上帝之数，人们还需要寻找更巧妙的思路。幸运的是，群论这一工具的威力远不只是用来分析像立方体的对称性那样显而易见的东西，在它的帮助下，新的思路很快就出现了。
　　
　　寻找上帝之数
　　
　　1992年，德国数学家科先巴提出了一种寻找魔方复原方法的新思路。他发现，在魔方的基本转动方式中，有一部分可以自成系列，通过这部分转动可以形成将近200亿种颜色组合。利用这200亿种组合，科先巴将魔方的复原问题分解成了两个步骤：第一步是将任意一种颜色组合转变为那200亿种组合之一，第二步则是将那200亿种组合复原。如果我们把魔方复原比作是让一条汪洋大海中的小船驶往一个固定的目的地，那么科先巴提出的那200亿种颜色组合就好比是一片特殊的水域—一片比那个固定地点大了200亿倍的特殊水域。他提出的两个步骤就好比是让小船首先驶往那片特殊水域，然后从那里驶往那个固定的目的地。在汪洋大海中寻找一片巨大的特殊水域，显然要比直接寻找那个小小的目的地容易得多，这就是科先巴的新思路的优越之处。
　　但即便如此，要用科先巴的方法对上帝之数进行估算仍不是一件容易的事。尤其是，要想进行快速的计算，最好是将复原那200亿种颜色组合的最少转动次数存储在计算机的内存中，这大约需要300兆的内存。300兆在今天看来是一个不太大的数目，但在科先巴提出新思路的那年，普通计算机的内存连它的十分之一都远远不到。因此直到3年后，才有人利用科先巴的方法给出了第一个估算结果。此人名叫里德,是美国佛罗里达大学的数学家。1995年,里德通过计算发现,最多经过12次转动，就可以将魔方的任意一种颜色组合变为科先巴那200亿种组合之一;而最多经过18次转动,就可以将那200亿种组合中的任意一种复原。这表明,最多经过12+18=30次转动，就可以将魔方的任意一种颜色组合复原。
　　在得到上述结果后，里德很快对自己的计算作了改进，将结果从30减少为29,这表明上帝之数不会超过29。此后随着计算机技术的发展,数学家们对里德的结果又作了进一步的改进,但进展并不迅速。直到11年后的2006年,奥地利开普勒大学符号计算研究所的博士生拉杜才将结果推进到了27。第二年，即2007年，美国东北大学的计算机科学家孔克拉和库伯曼又将结果推进到了26，他们的工作采用了并行计算系统，所用内存高达700万兆，所耗计算时间则长达8000小时(相当于将近一年的24小时不停歇计算)。这些计算结果表明，上帝之数不会超过26。2008年，研究上帝之数长达15年之久的计算机高手罗基奇运用了相当于将科先巴的特殊水域扩大几千倍的巧妙方法，在短短几个月的时间内对上帝之数连续发动了4次猛烈攻击，将它的估计值从25一直压缩到了22。截至今日，这是全世界范围内的最佳结果。
　　因此，现在我们已经知道，上帝之数一定不超过22。但是，罗基奇的特殊水域虽然很大，终究仍有很多颜色组合的最佳复原方法是无须经过那片特殊水域的，因此，上帝之数很可能比22更小。那么，它究竟是多少呢？人们虽然还无法确知，但种种迹象表明，它极有可能是20。这是因为，人们在过去这么多年的所有努力中，都从未遇到任何必须用20次以下转动才能复原的颜色组合，这表明“上帝之数”很可能不大于20。
　　另一方面,人们已经发现了几万种颜色组合,它们必须要用20次转动才能复原，这表明上帝之数不可能小于20。将这两方面综合起来，数学家们普遍相信,上帝之数的真正数值就是20。当然,“上帝”也许是微妙的，我们谁也无法保证它是否会在某个角落为我们留下惊讶，我们唯一有理由相信的也许是：这个游戏与数学交织而成的神秘的上帝之数距离它水落石出的那一天已不太遥远了。
　　（张川永摘自《科学画报》
　　2008年第12期,杜凤宝图）
（作者：卢昌海）