数学,让魔方拧得更快.doc

数学,让魔方拧得更快一年前, 谷歌告诉我们任意拧乱的魔方可以在 20 步内复原, 这个 20 , 也叫做上帝之数。当然,那只是对于 3 阶的魔方来说的。最近,一帮 MIT 的数学家说,他们找到了一种通用算法,可以找到任意阶魔方的上帝之数。那么,他们是怎么做到的呢? 魔方大概是现在最有影响力的智力游戏了, 它是一个 3×3×3 的正方体, 初始状态下每个面的 9 个方格都涂上同样颜色,6 个面一共 6 种颜色。作为一个智力游戏, 它的目标就是将任意拧乱的魔方尽快还原为每面所有小方格同色的初始状态。为了赢得比赛, 大家都致力于找到更快的魔方复原方法。大概一年前, Google 的一帮人验证了任意拧乱的魔方可以在 20 步内复原。但是, 一般人要在 20 步内复原任意魔方的话,就要记住一个硕大无比的表格(大约 8EB ,一 EB 大约是一百万 TB ), 这东西只有拥有全知全能的上帝及其类似物( 比如说团长、春哥或者高斯) 才能做到,所以 20 这个数又被称为魔方的“上帝之数”。魔方当然不只有一种。最简单的变化方法就是将魔方的“边长”(或者叫阶数)变大。原版的魔方是 3 阶的,也就是 3×3×3 的立方体。我们可以扩展到 4 阶( 4×4×4 ), 5阶,一直到 7阶, 甚至有人目击过 11 阶的魔方。魔方的阶数越大, 解起来也越复杂, 需要的步数也越多,它们的上帝之数也越大而且越难计算。现在, 一帮在 MIT 的由 Erik Demaine 领衔的数学家, 竟然说他们找到了任意阶数魔方的上帝之数, 而且还给出了一个复原的算法, 需要的步数与上帝之数相差不远! 我们现在就来看个究竟。怎么转都转不出那 24 个陷阱初看起来, 魔方每个面可以拧得千变万化, 让人无从捉摸。然而对于魔方面上涂色的小方块来说,它们可去的地方并不多(假设我们能做的操作就是将魔方的某排拧动 90 度)。由 24 个位置组成的一个位置群无论魔方被如何拧动, 图中所示的小色块一共只能到达最多 24 个位置。我们把这些位置称作一个位置群。一个 n 阶的魔方, 不算边角上的色块, 只有大约(n-2) 2 /4 个位置群。这些位置群都是相互独立的。要复原魔方,就相当于要将所有位置群复原。 Demaine 从玩魔方的人们那里了解到,有标准的手法可以单单将一个位置群内的小色块复原, 而不影响别的位置群的色块。这就是为什么我们说这些位置群是独立的。而因为每个位置群内色块的数目都是固定的(不多于 24 个),所以要复原一个位置群里的所有色块,只需要固定步数的操作。这些知识,魔方社区早就一清二楚。但是, 如果单靠这种方法来解 n 阶魔方的话, 因为至少有(n-2) 2 /4 个位置群, 所以用这种方法复原魔方需要的步数大约与 n2 成正比。有没有可能用更少的步数复原魔方呢?复原所有魔方的步数有没有下限呢? 上帝之数不能太小为了方便,我们记 n 阶魔方的上帝之数为 D(n) 。他们首先证明了,对于足够大的 n, D(n) 不能太小, 至少是 c×n2 /ln(n) , 其中 c 是一个常数。这个计算并不太难, 我们就一起来试试看。对于足够大的 n, 我们大约有 n2 /4 个位置群, 它们各自有 24 个不同位置的小色块。在这 2 4 个色块中,6 种颜色分别各有 4个, 这是初始状态决定的。用一点简单的组