趣味数学：数学教你玩转各类魔方( 二 ) _小知识

可能是经济危机中人们的各种节俭方式(拼车之类的)启发了Demaine，他想，虽然位置群之间是相互独立的，但是也许可以将不同位置群的复原操作兼并起来，一次拧动同时解决多个位置群的问题。如果说原来的复原方法是每个位置群各自为政，各自拥有一条复原线路的话，Demaine他们的方法就相当于建起了一条公交线路，一次将多个位置群送到彼岸。
利用这个方法，他们给出了一个算法，可以在c'×n2/ln(n)步内还原任意的n阶魔方。在这里c'是另一个常数，它比c大得多。
本来笔者想在这里描述一下证明过程，但无奈这个证明过于暴力，打上R-18也不为过，所以笔者也不好说太细，想详细观赏的重口味同学请上 arXiv 看现场。这里笔者只能写意地描绘一下。
证明过程中最重要的引理之一是，对于某些特定的k×m个位置群，要复原它们中被打乱方式相同的位置群，按照传统的方法平均需要的步数正比于k×m，但我们可以建一条公交线路，只用正比于(m+k)的步数就可以将这些位置群一下子全部解决，代价是一些别的位置群“躺着也中枪”，不知不觉就被改变了。
然后，在一些必要的预处理(比如说先解决边角问题)后，Demaine他们将魔方的所有位置群大约平均地分成n/4份，通过巧妙地应用上面的引理，使每次中枪的都是固定的几个位置群。当所有其它的位置群都被复原后，剩下满身弹孔(认识QB的同学请自行脑补)的“中枪专用位置群”数目也不多，可以用传统的方法一个一个解决。整个过程所需要的步数，恰好差不多正比于 n2/ln(n)，与最优的可能性只差一个乘法常数。这种过于暴力的方法，也是使常数c'变得很大的原因之一。
可能你会说笔者太坑爹，那些常规方法需要的步数，增长趋势也只是 n2，也就是说最多是另一个常数乘以 n2 。我们现在这么费劲也就是削下来了一个 ln(n) 的因子，这个看起来没什么用啊。
但不要小看 ln(n) 。常数毕竟是常数，它是不会变的，但是 ln(n) 可以无限增长。当 n 不断增长，总有一天 ln(n) 会比任何常数都要大，n2 会比 n2/ln(n) 大得多。
那么，Demaine他们的工作意义是什么呢?他们其实证明了任意 n 阶魔方的上帝之数 D(n) 的增长趋势与 n2/ln(n) 是一样的。更具体地说，尽管我们现在仍然不知道D(n)的具体表达式(可能永远也不会知道)，但它必定在 c×n2/ln(n) 和 c'×n2/ln(n) 之间。用数学的语言来说，我们第一次确定了任意n阶魔方上帝之数的阶，第一次将它困在了一个区间里。这是万里长征第一步，之后我们可以进行更精细的分析，缩短两个常数的距离，更好地确定上帝之数的位置。这也是Demaine他们下一步打算做的事情。
这个结果在魔方界也引起了不少人的兴趣。据某些魔方高手所言，Demaine他们的“差一个常数最优”的算法过程，对他们探索解高阶魔方的快速方法相当有启发，只是观摩已经满足不了他们了。