打亂一個魔方有多難？_風聞

文章來源丨科研圈

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。

在 t 次轉動之後，二階魔方狀態概率分佈與隨機分佈之間的差異

那麼，你應該用多少步來完全置亂一個口袋魔方呢？答案取決於你希望 d(t) 有多小。然而，上帝數字次轉動確實是不夠的。作為最低限度，一個人不應該轉動少於 19 次。（更多細節，包括計算 d(t) 的代碼，可以在 GitHub 獲得。）

當然，一旦你置亂了魔方，剩下要做的就是再次還原它了