打乱一个魔方有多难？（魔方难题）

“科研圈”报道·ID keyanquan·

宅在家里太无聊？来玩玩魔方吧。和还原魔方相比，打乱魔方看起来不需要任何技巧，但数学家发现事实并非如此……

图片来源：Pixabay

来源 the Conversation

撰文 Tim Garoni, Peaker Guo, Zongzheng Zhou

翻译张元一

编辑戚译引

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

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

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

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

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

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

置乱魔方意味着什么？

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

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

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

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

马尔可夫链蒙特卡罗方法

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

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

口袋魔方

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

这个魔方中没有边缘和中心部分，只剩下角。口袋魔方只有 3674160 个可能的状态，它的上帝数字只有 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。