趣味数学：数学教你玩转各类魔方.doc

趣味数学：数学教你玩转各类魔方魔方大概是现在最有影响力的智力游戏了它是一个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的由ErikDemaine领衔的数学家竟然说他们找到了任意阶数魔方的上帝之数而且还给出了一个复原的算法需要的步数与上帝之数相差不远!我们现在就来看个究竟。怎么转都转不出那24个陷阱初看起来魔方每个面可以拧得千变万化让人无从捉摸。然而对于魔方面上涂色的小方块来说它们可去的地方并不多(假设我们能做的操作就是将魔方的某排拧动90度)。无论魔方被如何拧动图中所示的小色块一共只能到达最多24个位置。我们把这些位置称作一个位置群。一个n阶的魔方不算边角上的色块只有大约(n-2)²/4个位置群。这些位置群都是相互独立的。要复原魔方就相当于要将所有位置群复原。Demaine从玩魔方的人们那里了解到有标准的手法可以单单将一个位置群内的小色块复原而不影响别的位置群的色块。这就是为什么我们说这些位置群是独立的。而因为每个位置群内色块的数目都是固定的(不多于24个)所以要复原一个位置群里的所有色块只需要固定步数的操作。这些知识魔方社区早就一清二楚。但是如果单靠这种方法来解n阶魔方的话因为至少有(n-2)²/4个位置群所以用这种方法复原魔方需要的步数大约与n²成正比。有没有可能用更少的步数复原魔方呢?复原所有魔方的步数有没有下限呢?上帝之数不能太小为了方便我们记n阶魔方的上帝之数为D(n)。他们首先证明了对于足够大的nD(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。可能我们做不到在c×n²/ln(n)步内还原任意的n阶魔方但是能不能提出一种方法即使还原的步数稍多一点但是起码增长速度跟n²/ln(n)一样呢?互搭便车的暴力复原方法可能是经济危机中人们的各种节俭方式(拼车之类的)启发了Demaine他想虽然位置群之间是相互独立的但是也许可以将不同位置群的复原操作兼并起来一次拧动同时解决多个位置群的问题。如果说原来的复原方法是每个位置群各自为政各自拥有一条复原线路的话Demaine他们的方法就相当于建起了一条公交线路一次将多个位置群送到彼岸。利用这个方法他们给出了一个算法可以在c'×n²/ln(n)步内还原任意的n阶魔方。在这里c'是另一个常数它比c大得多。本来笔者想在这里描述一下证明过程但无奈这个证明过于暴力打上R-18也不为过所以笔者也不好说太细想详细观赏的重口味同学请上arXiv看现场。这里笔者只能写意地描绘一下。