上帝的数字

Ⅲ　上帝的数字

其实魔方不只好玩，它在数学上用到了极多代数中的李群、群论，还有一些离散数学及概率知识。其实有机会上这些课的时候，都可以想想它在魔方上的应用，纯理论的课会因此变得生动些。魔方发展至今已有不少研究了，其中最大的课题就是“任意的三阶魔方，可以保证最少几步完成？”1982年佛雷(Alexander H. Frey)与辛马斯特(David Singmaster)合著的《魔方手册》(Handbook of Cubik)里，称这个答案为“上帝的数字”(God's number)，并证明这个数字介于17～52之间；也就是说，任意乱的情况，都可以在52步内完成，而且有一些情况保证至少要17步才能完成，书中并猜测上帝的数字为20。这里就要谈到怎么样才算“一步”，常见的有两种算法：一种是只要把一个面转90°就算一步，称做“quarter turn metric”(QTM)；另一种是转动一个面算一步，不管转几度，称做“face turn metric”(FTM)。QTM中若把一个面转180°，就算2步，而在FTM中只算了1步，因此FTM的数字会比QTM的少，而一般没特别指明的话，都是用FTM来计数。

1995年，美国玩家瑞德(Michael Raid)证明了某些情况至少需要20步才能完成，他将这些情况称做“Superflip”，同时，他也证明了可以在29步内完成所有的方块(QTM为42步)，一口气把上帝的数字范围缩小到20～29。2006年，雷杜(Silviu Radu)用群论证明了上界可以再缩小到27步(QTM为34步)，他将所有的情况分成几类，并借助离散数学系统(GAP)证明出在27步内都能完成。1990年，美国东北大学的计算机科学家古柏曼(Gene Cooperman)等人，在一个谈数学编码的研讨会上，发表了“2×2×2的方块皆可在11步内(QTM为14步)完成”；2007年，古柏曼与他的学生库柯尔(Daniel Kunkle)将这个方法推广到3×3×3的方块上，设计了一个平行算法，用20台超级计算机花了8000个小时，证明出26步内可以完成。2008年，美国史丹佛大学的罗区奇(Tomas Rokicki)继证明25步即可完成后，5月又在“魔方领域”(Domain of the CubeForum)论坛中更进一步证明了23步即可完成，震惊了整个魔方界，不过这些结果到目前还没有正式的论文出来。另一方面，德国数学家柯西姆巴(Herbert Kociemba)设计了一个叫做Cube Explorer的程序，可以帮你“尽量”找出最佳解，有时只比真的最佳解多一两步而已，他也用随机数生成了约1012种之多的情况，用Cube Explorer解开之后做了粗略的统计，约28%的情况可以在17步内完成、69%的情况可以18步完成、3%的情况可以19步完成，并没有超出20步的情况，可见瑞德的Superflip情况其实很少见。2010年8月，由Tomas Rokicki 及一些数学家与Google 的软件工程师，共同确定了“上帝的数字”为20。魔方的研究现今由数学、信息领域方面的学者共同努力，证出了上帝的数字。计算机的速度越来越快，数学也持续不断地发展，魔方是持续不断的推陈出新，相信会有越来越多的“上帝的数字”被确定出来。