數學，讓魔方擰得更快

魔方大概是現在最有影響力的智力遊戲了。它是一個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的由Erik Demaine領銜的數學家，竟然說他們找到了任意階數魔方的上帝之數，而且還給出了一個復原的演算法，需要的步數與上帝之數相差不遠！我們現在就來看個究竟。

怎麼轉都轉不出那24個陷阱

初看起來，魔方每個面可以擰得千變萬化，讓人無從捉摸。然而對於魔方面上塗色的小方塊來說，它們可去的地方並不多（假設我們能做的操作就是將魔方的某排擰動90度）。

無論魔方被如何擰動，圖中所示的小色塊一共只能到達最多24個位置。我們把這些位置稱作一個位置群。一個n階的魔方，不算邊角上的色塊，只有大約(n-2)2/4個位置群。這些位置群都是相互獨立的。要復原魔方，就相當於要將所有位置群復原。

Demaine從玩魔方的人們那裡了解到，有標準的手法可以單單將一個位置群內的小色塊復原，而不影響別的位置群的色塊。這就是為什麼我們說這些位置群是獨立的。而因為每個位置群內色塊的數目都是固定的（不多於24個），所以要復原一個位置群里的所有色塊，只需要固定步數的操作。這些知識，魔方社區早就一清二楚。

但是，如果單靠這種方法來解n階魔方的話，至少有(n-2)2/4個位置群。所以用這種方法復原魔方需要的步數大約與n2成正比，有沒有可能用更少的步數復原魔方呢？復原所有魔方的步數有沒有下限呢？

上帝之數不能太小

為了方便，我們記n階魔方的上帝之數為D(n)。他們首先證明了，對於足夠大的n，D(n)不能太小，至少是c×n2/ln(n)，其中c是一個常數。這個計算並不太難，我們就一起來試試看。

對於足夠大的n，我們大約有n2/4個位置群，它們各自有24個不同位置的小色塊。在這24個色塊中，6種顏色分別各有4個，這是初始狀態決定的。用一點簡單的組合知識就可以知道，我們一共有(24!)/(4!)?種方法打亂一個位置群中的色塊。因為位置群之間是獨立的，所以魔方至少有 (24!)/(4!)? (n-2)2/4 種不同的打亂方式（還沒算邊角排列的各種可能性）。

由上帝之數的定義，我們可以在D(n)步內將任意魔方復原。如果我們將這些復原的步驟倒過來操作，這其實就意味著我們可以用至多D(n)步將魔方打亂到所有可能的打亂方式。每一步我們有(6n+1)種操作，每次操作就是將某一排擰上90度，另外復原後舉起魔方炫耀然後被打倒在地踩上一萬隻腳也算一次操作，可以爬起來然後多次重複這項操作。所以魔方至多有 (6n+1) D(n) 種打亂方式，因為某些系列操作會導致同樣的打亂結果。

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

從這個不等式我們可以得到：

當n趨向於無窮大的時候，上面那個看起來很複雜的量就跟 c×n2/ln(n) 差不多了，其中c大約是35.7164。

可能我們做不到在 c×n2/ln(n) 步內還原任意的n階魔方，但是能不能提出一種方法，即使還原的步數稍多一點，但是起碼增長速度跟 n2/ln(n) 一樣呢？

互搭便車的暴力復原方法

可能是經濟危機中人們的各種節儉方式（拼車之類的）啟發了Demaine，他想，雖然位置群之間是相互獨立的，但是也許可以將不同位置群的復原操作兼并起來，一次擰動同時解決多個位置群的問題。如果說原來的復原方法是每個位置群各自為政，各自擁有一條復原線路的話，Demaine他們的方法就相當於建起了一條公交線路，一次將多個位置群送到彼岸。

利用這個方法，他們給出了一個演算法，可以在c ×n2/ln(n)步內還原任意的n階魔方。在這裡c 是另一個常數，它比c大得多。

本來筆者想在這裡描述一下證明過程，但無奈這個證明過於暴力，打上R-18也不為過，所以筆者也不好說太細，這裡筆者只能寫意地描繪一下。

證明過程中最重要的引理之一是，對於某些特定的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他們的「差一個常數最優」的演算法過程，對他們探索解高階魔方的快速方法相當有啟發，只是觀摩已經滿足不了他們了。

文章來自果殼網

每天好玩的數學

微信號：DailyMathFun

以數學學習為主題，以傳播數學文化為己任，以激發學習者學習數學的興趣為目標，分享有用的數學知識、有趣的數學故事、傳奇的數學人物等，為你展現一個有趣、好玩、豐富多彩的數學世界。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！