版权归原作者所有,如有侵权,请联系我们

最少要多少次转动才能让魔方复原?

北京科协

魔方是一种深受人们喜爱的益智玩具。自 20 世纪 80 年代初开始,这一玩具风靡了全球。

魔方拥有竞速、盲拧、单拧等多种玩法,风靡程度经久未衰,每年都会举办大小赛事,是最受欢迎的智力游戏之一。

通常意义下的魔方,是指狭义的三阶魔方。三阶魔方形状通常是正方体,由有弹性的硬塑料制成。常规竞速玩法是将魔方打乱,然后在最短的时间内复原。广义的魔方,指各类可以通过转动打乱和复原的几何体。

魔方与华容道、法国的单身贵族(独立钻石棋)同被称谓智力游戏界的三大不可思议。

图源:pexls

魔方是匈牙利布达佩斯应用艺术学院的建筑学教授艾尔诺·鲁比克(Ernö Rubik)发明的,也被称为鲁比克方块(Rubik’s cube)。

图源:pexls

鲁比克最初想发明的并不是益智玩具,而是一个能演示空间转动,帮助学生直观理解空间几何的教学工具。经过一段时间的考虑,他决定制作一个由小方块组成、各个面能随意转动的 3×3×3 结构的立方体。

图源:pexls

自 1981 年起,魔方爱好者们开始举办世界性的魔方大赛。在这种大赛中,不断有玩家刷新最短复原时间的世界纪录。

不过,玩家们复原魔方所用的转动次数并不是理论上最少的次数(即并不是“上帝之数”),因为他们采用的是便于人脑掌握的方法,追求的则是最短的复原时间。

多几次转动虽然要多花一点时间,但比起寻找理论上最少的转动次数来仍要快速得多——事实上,后者往往根本就不是人脑所能胜任的。

那么,最少要多少次转动才能让魔方复原呢?或者更确切地说,最少要多少次转动才能确保任意颜色组合的魔方都被复原呢?这个问题不仅让魔方爱好者们感到好奇,还引起了一些数学家的兴趣,因为它是一个颇有难度的数学问题。数学家们甚至给这个最少的转动次数取了一个很气派的别名,叫作“上帝之数”。

自 20 世纪 90 年代起,数学家们就开始寻找这个神秘的“上帝之数”。寻找“上帝之数”的一个最直接的思路是大家都能想到的,那就是对所有颜色组合逐一计算出最少的转动次数,它们中最大的那个显然就是能确保任意颜色组合都被复原的最少转动次数,即“上帝之数”。可惜的是,那样的计算是世界上最强大的计算机也无法胜任的,因为魔方的颜色组合实在太多了。怎么办呢?数学家们只好诉诸他们的老本行——数学。1992 年,一位名叫赫伯特·科先巴(Herbert Kociemba)的德国数学家提出了一种新思路。他发现, 在魔方的基本转动方式中, 有一部分可以自成系列,通过这部分转动可以形成将近 200 亿种颜色组合。利用这 200 亿种组合,科先巴将魔方的复原问题分解成了两个步骤:第一步是将任意一种颜色组合转变为那 200 亿种组合之一,第二步则是将那 200亿种组合复原。

如果我们把魔方复原比作是让一条汪洋大海中的小船驶往一个固定的目的地,那么科先巴提出的那两百亿种颜色组合就好比是一片特殊的水域——一片比那个固定地点大了 200 亿倍的特殊水域。他提出的两个步骤就好比是让小船首先驶往那片特殊水域,然后从那里驶往那个固定的目的地。在汪洋大海中寻找一片巨大的特殊水域,显然要比直接寻找那个小小的目的地容易得多, 这就是科先巴的新思路的优越之处。但即便如此, 要用科先巴的方法对 “上帝之数” 进行估算仍不是一件容易的事。尤其是,要想进行快速的计算,最好是将复原那 200 亿种颜色组合的最少转动次数 (这相当于是那片 “特殊水域” 的地图) 存储在计算机的内存中, 这大约需要 300 兆的内存。300 兆在今天看来是一个不太大的数目,但在科先巴提出新思路的那年,普通机器的内存连它的十分之一都远远不到。因此直到三年后,才有人利用科先巴的方法给出了第一个估算结果。此人名叫里德(M. Reid),是美国数学家。

1995 年,里德通过计算发现,最多经过 12 次转动,就可以将魔方的任意一种颜色组合变为科先巴那 200 亿种组合之一;而最多经过 18 次转动,就可以将那 200 亿种组合中的任意一种复原。这表明,最多经过 12+18=30 次转动, 就可以将魔方的任意一种颜色组合复原。运用这一思路,2007 年,“上帝之数”被证明了不可能大于 26。也就是说,只需 26 次转动就能确保任意颜色组合的魔方都被复原。但这个数字却还不是“上帝之数”,因为科先巴的新思路有一个明显的局限,那就是必须先经过他所选出的特殊颜色组合中的一个。事实上,某些转动次数最少的复原方法是不经过那些特殊颜色组合的。因此,科先巴的新思路虽然降低了计算量,找到的复原方法却不一定是转动次数最少的。

图源:pexls

为了突破这个局限,数学家们采取了一个折中手段,那就是适当地增加特殊颜色组合的数目,因为这个数目越大,转动次数最少的复原方法经过那些特殊颜色组合的可能性也就越大。当然,这么做无疑会增大计算量。不过,计算机技术的快速发展很快就抵消了计算量的增大。

2008 年,计算机高手汤姆·罗基奇(TomRokicki)用这种折中手段把对“上帝之数”的估计值压缩到了 22。也就是说,只需要 22 次转动就能确保任意颜色组合的魔方都被复原。那么,22 这个数字是否就是“上帝之数”呢?答案是否定的。这一点的一个明显征兆,就是人们从未发现任何一种颜色组合需要超过 20 次转动才能复原。这使人们猜测“上帝之数”应该是 20(它不可能小于 20,因为有很多颜色组合已被证明需要 20 次转动才能复原)。

2010 年 7 月,这一猜测终于被科先巴本人及几位合作者所证明。因此,现在我们可以用数学特有的确定性来回答“最少要多少次转动才能让魔方复原?”了,答案就是:20 次。

本文转载自/原点阅读

责编/小西途说

评论
坚持学习,提升素质
太傅级
魔方是一种深受人们喜爱的益智玩具。小小的魔方隐藏着大大的智慧。
2022-08-05
离线不掉线
太师级
为了突破这个局限,数学家们采取了一个折中手段,那就是适当地增加特殊颜色组合的数目,因为这个数目越大,转动次数最少的复原方法经过那些特殊颜色组合的可能性也就越大。当然,这么做无疑会增大计算量。不过,计算机技术的快速发展很快就抵消了计算量的增大。
2022-08-05
科普天天平安快乐
秀才级
复杂中带着技术与技巧,不仅仅是益智玩具。
2022-08-05