打乱一个魔方有多难？

　　40年来，魔方一直是世界上最受欢迎的谜题之一。正如无数的书中所解释的那样，人们已设计出好几种不同的方法来解决这个问题。有经验的“快速魔方玩家”可以在几秒钟内解决这个问题，将魔方还原。

　　除了其惊人的灵活性，与魔方相关的还有许多迷人的数学问题。魔方的一次转动被定义为将六个面中的一个旋转90、180或270度。要想通过多次转动还原魔方，一共有惊人的43 252 003 274 489 856 000个可能状态。

　　尽管魔方如此复杂，但2010年有人证明，无论初始状态如何，魔方总是可以通过20次之内的转动被还原。这个数字被称为“上帝的数字”，因为人类已知的所有还原运算方法得出的转动步数通常都比这个最优值多得多。

　　但你有没有想过与这相反的问题：要打乱一个还原的魔方需要多少转动步数？乍一看，这是一个比计算上帝的数字容易得多的问题。毕竟，与还原魔方不同，置乱魔方不需要任何技巧。

　　在洗牌问题中，类似的问题已经被回答了。一个著名的例子是1990年数学家戴夫·拜尔（Dave Bayer）和珀西·迪亚科尼斯（Perci Diaconis）对“快速洗牌”（riffle shuffle）的研究。如果一副牌的顺序是随机的，那么我们定义它为“混合的”（mixed），每一种可能的顺序都有相同的出现概率。拜耳和迪亚科尼斯表明，七次快速洗牌是必要的，这样可以大致得到一套混合的扑克牌。

　　去年，数学家发表了一篇关于15拼图的类似研究报告，该拼图是一个4x4正方形，填充着15个图块和一个空白空间。

　　一个人试图置乱魔方的典型做法是重复的随机转动。数学家将由此产生的状态随机序列称为马尔可夫链的一个特例。它的关键特性是：给定当前状态，则下一个状态出现的概率只取决于这个当前状态，而不取决于之前任何一个状态。

　　将马尔可夫链理论应用于置乱魔方，结果表明，随着随机转动次数增加，处于任一特定可能状态的概率越来越接近1/4 325 200 327 448 985 600。数学家称之为“均匀概率分布”，因为每个可能状态以相同的概率出现。

　　在任意数量的随机转动之后，魔方的状态将是随机的，但其概率分布不一定是均匀分布；某些状态将比其他状态更容易发生。

　　用d(t)表示t次随机转动后的概率分布与均匀概率分布之间的差异。随着随机移动次数t的增加，d(t)值将减小。被搅乱的魔方有较小的d(t)。

　　马尔可夫链理论中，d(t)的这种下降过程被称为“混合”（mixing）。除了洗牌和拼图之外，马尔可夫链混合理论也具有非常实际的应用。蒙特卡罗方法也是现代科学和工程中最重要的计算工具之一。这种方法得名于一家著名的赌场，基本上依赖于几率。本质上，它用多个随机猜测来近似解决数学难题。

　　在实践中，马尔可夫链经常被用来产生随机状态。要了解马尔可夫链蒙特卡罗方法的准确度，关键是计算d(t)随t增加而减少的速度。

　　研究标准三阶魔方的置乱问题是目前一个尚未解决的迷人挑战。然而，如果我们把注意力转向一个更小的二阶版本，即口袋魔方（pocket cube），它就变得非常容易。

　　这个魔方中没有边缘和中心部分，只剩下角。口袋魔方只有3 674 160个可能的状态，它的上帝数字只有11。

　　在下图中，我们为口袋魔方绘制d(t)。经过11次转动，d(t)仍然很大，为0.695。在马尔可夫链理论中，使d(t)值低于0.25（通常被称为“混合时间”）的第一个转动次数（t值）为19.25次转动后d(t)为0.092；50次转动后d(t)为0.0012；100次转动后d(t)为0.00000017。

　　在t次转动之后，二阶魔方状态概率分布与随机分布之间的差异。（图片来源：Eric Zhou）

　　那么，你应该用多少步来完全置乱一个口袋魔方呢？答案取决于你希望d(t)有多小。然而，上帝数字次转动确实是不够的。作为最低限度，一个人不应该转动少于19次。（更多细节，包括计算d(t)的代码，可以在GitHub获得。）