如何把魔方拧得更快

正文

请到「今天看啥」查看全文

Demaine从玩魔方的人们那里了解到，有标准的手法可以单单将一个位置群内的小色块复原，而不影响别的位置群的色块。这就是为什么我们说这些位置群是独立的。而因为每个位置群内色块的数目都是固定的（不多于24个），所以要复原一个位置群里的所有色块，只需要固定步数的操作。这些知识，魔方社区早就一清二楚。

但是，如果单靠这种方法来解n阶魔方的话，因为至少有(n-2)²/4个位置群，所以用这种方法复原魔方需要的步数大约与n²成正比。有没有可能用更少的步数复原魔方呢？复原所有魔方的步数有没有下限呢？

上帝之数不能太小

为了方便，我们记n阶魔方的上帝之数为D(n)。他们首先证明了，对于足够大的n，D(n)不能太小，至少是c×n²/ln(n)，其中c是一个常数。这个计算并不太难，我们就一起来试试看。

对于足够大的n，我们大约有n²/4个位置群，它们各自有24个不同位置的小色块。在这24个色块中，6种颜色分别各有4个，这是初始状态决定的。用一点简单的组合知识就可以知道，我们一共有(24!)/(4!)⁶种方法打乱一个位置群中的色块。因为位置群之间是独立的，所以魔方至少有 (24!)/(4!)⁶ ^(n-2)²/4 种不同的打乱方式（还没算边角排列的各种可能性）。

由上帝之数的定义，我们可以在D(n)步内将任意魔方复原。如果我们将这些复原的步骤倒过来操作，这其实就意味着我们可以用至多D(n)步将魔方打乱到所有可能的打乱方式。每一步我们有(6n+1)种操作，每次操作就是将某一排拧上90度，另外复原后举起魔方炫耀然后被打倒在地踩上一万只脚也算一次操作，可以爬起来然后多次重复这项操作。所以魔方至多有 (6n+1) ^D(n) 种打乱方式，因为某些系列操作会导致同样的打乱结果。

我们就有了以下的不等式：

从这个不等式我们可以得到：

当n趋向于无穷大的时候，上面那个看起来很复杂的量就跟 c×n²/ln(n) 差不多了，其中c大约是35.7164。

请到「今天看啥」查看全文