1707611553
绘画:张京
1707611554
1707611555
1707611556
1707611557
1707611558
因为星星在那里:科学殿堂的砖与瓦 魔方与“上帝之数”[1]
1707611559
1707611560
2008年7月,来自世界各地的很多优秀的魔方玩家聚集在捷克共和国(Czech Republic)中部城市帕尔杜比采(Pardubice),参加魔方界的重要赛事:捷克公开赛。在这次比赛上,荷兰玩家阿克斯迪杰克(Erik Akkersdijk)创下了一个惊人的纪录:只用7.08秒就复原了一个颜色被打乱的魔方。无独有偶,在这一年的8月,人们在研究魔方背后的数学问题上也取得了重要进展。在本文中,我们就来介绍一下魔方以及它背后的数学问题。
1707611561
1707611562
1707611563
1707611564
1707611566
因为星星在那里:科学殿堂的砖与瓦 一、风靡世界的玩具
1707611567
1707611568
1974年春天,匈牙利布达佩斯应用艺术学院(Budapest College of Applied Arts)的建筑学教授鲁比克(Ernö Rubik)萌生了一个有趣的念头,那就是设计一个教学工具来帮助学生直观地理解空间几何中的各种转动。经过思考,他决定制作一个由一些小方块组成的,各个面能随意转动的3×3×3的立方体。这样的立方体可以很方便地演示各种空间转动。
1707611569
1707611570
这个想法虽好,实践起来却面临一个棘手的问题,即如何才能让这样一个立方体的各个面能随意转动?鲁比克想了很多点子,比如用磁铁或橡皮筋连接各个小方块,但都不成功。那年夏天的一个午后,他在多瑙河畔乘凉,眼光不经意地落在了河畔的鹅卵石上。忽然,他心中闪过一个新的设想:用类似于鹅卵石表面那样的圆形表面来处理立方体的内部结构。这一新设想成功了,鲁比克很快完成了自己的设计,并向匈牙利专利局申请了专利。这一设计就是我们都很熟悉的魔方(magic cube),也叫鲁比克方块(Rubik’s cube)[2]。
1707611571
1707611572
6年后,鲁比克的魔方经过一位匈牙利商人兼业余数学家的牵头,打进了西欧及美国市场,并以惊人的速度成为了风靡全球的新潮玩具。在此后的25年间,魔方的销量超过了3亿个。在魔方的玩家中,既有牙牙学语的孩子,也有跨国公司的老总。魔方虽未如鲁比克设想的那样成为一种空间几何的教学工具,却变成了有史以来最畅销的玩具。
1707611573
1707611574
魔方之畅销,最大的魔力就在于其数目惊人的颜色组合。一个魔方出厂时每个面各有一种颜色,总共有6种颜色,但这些颜色被打乱后,所能形成的组合数却多达4 325亿亿[3](1亿亿=1×1016)。如果我们将这些组合中的每一种都做成一个魔方,这些魔方排在一起,可以从地球一直排到250光年外的遥远星空——也就是说,如果我们在这样一排魔方的一端点上一盏灯,那灯光要在250年后才能照到另一端!如果哪位勤勉的玩家想要尝试所有的组合,哪怕他不吃、不喝、不睡,每秒钟转出10种不同的组合,也要花1 500亿年的时间才能如愿(作为比较,我们的宇宙目前还不到140亿岁)。与这样的组合数相比,广告商们常用的“成千上万”、“数以亿计”、“数以十亿计”等平日里虚张声势、忽悠顾客的形容词反倒变成了难得的谦虚。我们可以很有把握地说,假如不掌握诀窍地随意乱转,一个人哪怕从宇宙大爆炸之初就开始玩魔方,也几乎没有任何希望将一个色彩被打乱的魔方复原。
1707611575
1707611576
1707611577
1707611578
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
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次转动,就可以将魔方的任意一种颜色组合复原。
[
上一页 ]
[ :1.707611553e+09 ]
[
下一页 ]