打字猴:1.70761158e+09
1707611580 因为星星在那里:科学殿堂的砖与瓦 二、魔方与“上帝之数”
1707611581
1707611582 魔方的玩家多了,相互间的比赛自然是少不了的。自1981年起,魔方爱好者们开始举办世界性的魔方大赛,从而开始缔造自己的世界纪录。这一纪录被不断地刷新着,截至2013年,复原魔方的最快纪录已经达到了令人吃惊的5.55秒。当然,单次复原的纪录存在一定的偶然性,为了减少这种偶然性,自2003年起,魔方大赛的冠军改由多次复原的平均成绩来决定[4],截至2013年,这一平均成绩的世界纪录为6.54秒。这些纪录的出现,表明魔方虽有天文数字般的颜色组合,但只要掌握窍门,将任何一种给定的颜色组合复原所需的转动次数却很可能并不多。
1707611583
1707611584 那么,最少需要多少次转动,才能确保无论什么样的颜色组合都能被复原呢[5]?这个问题引起了很多人,尤其是数学家们的兴趣。这个复原任意组合所需的最少转动次数被数学家们戏称为“上帝之数”(God’s number),而魔方这个玩具世界的宠儿则由于这个“上帝之数”而一举侵入了学术界。
1707611585
1707611586 要研究“上帝之数”,首先当然要研究魔方的复原方法。在玩魔方的过程中,人们早就知道,将任何一种给定的颜色组合复原都是很容易的,这一点已由玩家们的无数杰出纪录所示范。不过魔方玩家们所用的复原方法是便于人脑掌握的方法,却不是转动次数最少的,因此无助于寻找“上帝之数”。寻找转动次数最少的方法是一个有一定难度的数学问题。当然,这个问题是难不倒数学家的。早在20世纪90年代中期,人们就有了较实用的算法,可以用平均15分钟左右的时间找出复原一种给定的颜色组合的最少转动次数。从理论上讲,如果有人能对每一种颜色组合都找出这样的最少转动次数,那么这些转动次数中最大的一个无疑就是“上帝之数”了。但可惜的是,“4 325亿亿”这个巨大数字成为了人们窥视“上帝之数”的拦路虎。如果采用上面提到的算法,用上面提到的速度寻找,哪怕用一亿台计算机同时进行,也要用超过1 000万年的时间才能完成。
1707611587
1707611588 看来蛮干是行不通的,数学家们于是便求助于他们的老本行:数学。从数学的角度看,魔方的颜色组合虽然千变万化,其实都是由一系列基本操作——即转动——产生的,而且那些操作还具有几个非常简单的特点,比如任何一个操作都有一个相反的操作(比如与顺时针转动相反的操作就是逆时针转动)。对于这样的操作,数学家们的“武器库”中有一种非常有效的工具来对付它,这工具叫做群论(group theory),它比魔方问世早了140多年就已出现了。据说德国数学大师希尔伯特(David Hilbert)曾经表示,学习群论的窍门就是选取一个好的例子。自魔方问世以来,数学家们已经写出了好几本通过魔方讲述群论的书。因此,魔方虽未成为空间几何的教学工具,却在一定程度上可以作为学习群论的“好的例子”。
1707611589
1707611590 对魔方研究来说,群论有一个非常重要的优点,就是可以充分利用魔方的对称性。我们前面提到“4 325亿亿”这个巨大数字时,其实有一个疏漏,那就是未曾考虑到魔方作为一个立方体所具有的对称性。由此导致的结果,是那4 325亿亿种颜色组合中有很多其实是完全相同的,只是从不同的角度去看——比如让不同的面朝上或者通过镜子去看——而已。因此,“4 325亿亿”这个令人望而生畏的数字实际上是“注水猪肉”。那么,这“猪肉”中的“水分”占多大比例呢?说出来吓大家一跳:占了将近99%!换句话说,仅凭对称性一项,数学家们就可以把魔方的颜色组合减少两个数量级[6]。
1707611591
1707611592 但减少两个数量级对于寻找“上帝之数”来说还是远远不够的,因为那不过是将前面提到的1000万年的时间减少为了10万年。对于解决一个数学问题来说,10万年显然还是太长了,而且我们也并不指望真有人能动用一亿台计算机来计算“上帝之数”。数学家们虽然富有智慧,在其他方面却不见得富有,他们真正能动用的也许只有自己书桌上那台计算机。因此为了寻找“上帝之数”,人们还需要更巧妙的思路。幸运的是,群论这一工具的威力远不只是用来分析像立方体的对称性那样显而易见的东西,在它的帮助下,更巧妙的思路很快就出现了。
1707611593
1707611594
1707611595
1707611596
1707611597 因为星星在那里:科学殿堂的砖与瓦 [:1707611250]
1707611598 因为星星在那里:科学殿堂的砖与瓦 三、寻找“上帝之数”
1707611599
1707611600 1992年,德国数学家科先巴(Herbert Kociemba)提出了一种寻找魔方复原方法的新思路[7]。他发现,在魔方的基本转动方式中,有一部分可以自成系列,通过这部分转动可以形成将近200亿种颜色组合[8]。利用这200亿种颜色组合,科先巴将魔方的复原问题分解成了两个步骤:第一步是将任意一种颜色组合转变为那200亿种颜色组合之一,第二步则是将那200亿种颜色组合复原。如果我们把魔方的复原比作是让一条汪洋大海中的小船驶往一个固定目的地,那么科先巴提出的那200亿种颜色组合就好比是一片特殊水域——一片比那个固定目的地大了200亿倍的特殊水域。他提出的两个步骤就好比是让小船首先驶往那片特殊水域,然后从那里驶往那个固定目的地。在汪洋大海中寻找一片巨大的特殊水域,显然要比直接寻找那个小小的目的地容易得多,这就是科先巴新思路的巧妙之处。
1707611601
1707611602 但即便如此,要用科先巴的新思路对“上帝之数”进行估算仍不是一件容易的事。尤其是,要想进行快速计算,最好是将复原那200亿种颜色组合的最少转动次数(这相当于是那片特殊水域的“地图”)存储在计算机的内存中,这大约需要300兆(300MB)的内存。300兆在今天看来是一个不太大的数目,但在科先巴提出新思路的年代,普通计算机的内存连它的十分之一都远远不到。因此直到3年之后,才有人利用科先巴的新思路给出了第一个估算结果。此人名叫里德(Michael Reid),是美国中佛罗里达大学(Unversity of Central Florida)的数学家。1995年,里德通过计算发现,最多经过12次转动,就可以将魔方的任意一种颜色组合转变为科先巴新思路中那200亿种颜色组合之一;而最多经过18次转动,就可以将那200亿种颜色组合中的任意一种复原。这表明,最多经过12+18=30次转动,就可以将魔方的任意一种颜色组合复原。
1707611603
1707611604 在得到上述结果后,里德很快对自己的估算作了改进,将结果从30减少为了29,这表明“上帝之数”不会超过29。此后随着计算机技术的发展,数学家们对里德的结果又作出了进一步改进,但进展并不迅速。直到11年后的2006年,奥地利开普勒大学(Johannes Kepler University)符号计算研究所(Research Institute for Symbolic Computation)的博士生拉杜(Silviu Radu)才将结果推进到了27。第二年(即2007年),美国东北大学(Northeastern University)的计算机科学家孔克拉(Dan Kunkle)和库伯曼(Gene Cooperman)又将结果推进到了26,他们的工作采用了并行计算系统,所用的最大存储空间高达700万兆(7×106MB),所耗的计算时间则长达8 000小时(相当于将近一年的24小时不停歇计算)。
1707611605
1707611606 这些计算表明,“上帝之数”不会超过26。但是,所有这些计算的最大优点——即利用科先巴新思路中那片特殊水域——同时也是它们最致命的弱点,因为它们给出的复原方法都必须经过那片特殊水域。可事实上,很多颜色组合的最佳复原方法根本就不经过那片特殊水域,比如紧邻目的地,却恰好不在特殊水域中的任何小船,显然都没必要像中国大陆和台湾之间的直航包机一样,故意从那片特殊水域绕一下才前往目的地。因此,用科先巴新思路得到的复原方法未必是最佳的,由此对“上帝之数”所做的估计也极有可能是高估。
1707611607
1707611608 可是,如果不引进科先巴新思路中的特殊水域,计算量又实在太大,怎么办呢?数学家们决定采取折中手段,即扩大那片特殊水域的“面积”。因为特殊水域越大,最佳复原路径恰好经过它的可能性也就越大(当然,计算量也会有相应的增加)。2008年,研究“上帝之数”长达15年之久的计算机高手罗基奇(Tomas Rokicki)运用了相当于将科先巴新思路中的特殊水域扩大几千倍的巧妙方法,在短短几个月的时间内对“上帝之数”连续发动了四次猛烈攻击,将它的估计值从25一直压缩到了22——这就是本文开头提到的人们在研究魔方背后的数学问题上取得的重要进展。罗基奇的计算得到了电影特效制作商索尼图形图像运作公司(Sony Pictures Imageworks)的支持,这家曾为《蜘蛛人》(Spider-Man)等著名影片制作特效的公司向罗基奇提供了相当于50年不停歇计算所需的计算机资源。
1707611609
1707611610 由此我们进一步知道,“上帝之数”一定不会超过22。但是,罗基奇虽然将科先巴新思路中的特殊水域扩展得很大,终究仍有一些颜色组合的最佳复原方法是无需经过那片特殊水域的,因此,“上帝之数”很可能比22更小。那么,它究竟是多少呢?种种迹象表明,它极有可能是20。这是因为,人们在过去这么多年的所有努力——其中包括罗基奇直接计算过的大约4 000万亿种颜色组合——中,都从未遇到过任何必须用20次以上转动才能复原的颜色组合,这表明“上帝之数”很可能不大于20;另一方面,人们已经发现了几万种颜色组合,它们必须要用20次转动才能复原,这表明“上帝之数”不可能小于20。将这两方面综合起来,数学家们普遍相信,“上帝之数”的真正数值就是20。
1707611611
1707611612 2010年8月,这个游戏与数学交织而成的神秘的“上帝之数”终于水落石出:研究“上帝之数”的“元老”科先巴、“新秀”罗基奇,以及另两位合作者——戴维森(Morley Davidson)和德斯里奇(John Dethridge)——宣布了对“上帝之数”是20的证明[9]。他们的证明得到了谷歌公司(Google)提供的相当于英特尔(Intel)四核心处理器35年不停歇计算所需的计算机资源。
1707611613
1707611614 因此,现在我们可以用数学特有的确定性来宣布“上帝之数”的数值了,那就是:20。
1707611615
1707611616 2008年11月2日写于纽约
1707611617
1707611618 2014年9月18日最新修订
1707611619
1707611620 [1]本文曾发表于《科学画报》2008年第12期(上海科学技术出版社出版)。
1707611621
1707611622 [2]“魔方”是鲁比克自己为这一设计所取的名字,“鲁比克方块”则是美国玩具公司Ideal Toys所取的名字。在西方国家,鲁比克方块这一名称更为流行,在中国,则是魔方这一名称更为流行。另外要提醒读者的是,魔方有很多种类,本文介绍的3×3×3魔方只是其中最常见的一种。
1707611623
1707611624 [3]具体的计算是这样的:在组成魔方的小立方体中,有8个是顶点,它们之间有8!种置换;这些顶点每个有3种颜色,从而在朝向上有37种组合(由于结构所限,魔方的顶点只有7个能有独立朝向)。类似的,魔方有12个小立方体是边,它们之间有12! /2种置换(之所以除以2,是因为魔方的顶点一旦确定,边的置换就只有一半是可能的);这些边每个有两种颜色,在朝向上有211种组合(由于结构所限,魔方的边只有11个能有独立朝向)。因此,魔方的颜色组合总数为8!×37×12!×211/2=43 252 003 274 489 856 000,即大约4 325亿亿。另外值得一提的是,倘若我们允许将魔方拆掉重组,则前面提到的结构限定将不复存在,它的颜色组合数将多达51 900亿亿种。不过颜色组合数的增加并不意味着复原的难度变大,魔方结构对颜色组合数的限制实际上正是使魔方的复原变得困难的主要原因。举个例子来说,26个英文字母在相邻字母的交换之下共有约400亿亿亿种组合,远远多于魔方颜色的组合数,但通过相邻字母的交换将随意排列的26个英文字母复原成从A到Z的初始排列却非常简单。
1707611625
1707611626 [4]确切地说是取5次尝试中居中的3次成绩的平均值。
1707611627
1707611628 [5]为了使这一问题有意义,当然首先要定义什么是转动。在对魔方的数学研究中,转动是指将魔方的任意一个(包含9个小方块的)面沿顺时针或逆时针方向转动90°或180°,对每个面来说,这样的转动共有3种。(请读者想一想,为什么不是4种?)由于魔方有6个面,因此它的基本转动方式共有18种。
1707611629
[ 上一页 ]  [ :1.70761158e+09 ]  [ 下一页 ]