最近受疫情影響延遲開學，宅家多日。雖說對于我們基礎數學專業的學生，一本書、一支筆、一疊紙，沉浸其中，不知不覺就能從白天思考到黑夜；但許久未見到熟悉的老師和同學們，難免也有些孤單和煩悶。于是，在學習研究之餘，我也拾起了曾經狂熱的愛好——魔方，聊以消遣。今天，我想和大家分享一下關于魔方及其與數學關系的一點思考。

魔方，這個風靡全球的小小玩具，是匈牙利建築學教授Ernő Rubik在1974年發明的。自1980年大規模生産以來，魔方早已走進了千家萬戶。魔方曾多次出現在公衆視野中，從電影《當幸福來敲門》威爾•史密斯飾演的男主角通過複原魔方而得到工作實習機會，到近年來《最強大腦》《挑戰不可能》等綜藝節目中的表演，都體現了魔方作為常人眼中“高智商玩具”的一面。

電影《當幸福來敲門》劇照

近期剛剛因新冠肺炎不幸逝世的著名數學家John Conway也與魔方有千絲萬縷的聯系。他是匈牙利以外最早關注魔方的人之一，把魔方帶到了1978年在芬蘭赫爾辛基舉辦的第十八屆國際數學家大會上。他也一直關心包括魔方在内的各種數學遊戲和智力玩具，曾在專注于此的馬丁•加德納的專欄寫過多篇文章，還出席過許多相關的活動。

數學家John Conway肖像

魔方最為大衆熟悉的是“競速”方面。目前的三階魔方單次還原世界紀錄是由中國選手杜宇生保持的3.47秒。北京大學校友董百強和柯言也曾分别在最少步還原（給定一個打亂，選手需要在1個小時的限時内通過多次還原來找到最短的解法并記錄下來）與三階盲擰（先對魔方進行記憶，然後蒙眼進行複原）兩個項目上打破過世界紀錄。

世界魔方協會慶祝杜宇生3.47s世界紀錄

魔方發展到如今，演化出了各種各樣的變形。四階、五階魔方早已不稀奇，目前的最高階魔方已經達到驚人的33階。

33階魔方示意圖

其它外形的魔方也層出不窮，從相對常見的其它四種正多面體（正四面體、正八面體、正十二面體、正二十面體），到不那麼常見的半正多面體、卡塔蘭立體，甚至更加奇特的幾何體，都在魔方中能找到。要玩好魔方，無疑需要對這些幾何體都有充分的了解，這大概就是“魔方能提高空間想象力”的來源吧。

不同外形的魔方

從魔方中，我們能夠直觀地看到各種幾何體的聯系。限于篇幅，僅舉一例如下。正十二面體三階五魔方可以改造成立方體外形的Hexaminx，此時六個面的圖案仍然十分規整——這就體現了正十二面體與立方體的選取正十二面體的八個頂點連接，就可以得到一個立方體。從三階五魔方改造出Hexaminx的過程，正是切掉六個“屋頂”形狀的部分。這個關系在數學中也有用處，可以被用于證明正十二面體的保向對稱群與交錯群A5同構。

三階五魔方與Hexaminx

Michael Artin《代數》一書中的相關證明

現代的一些魔方則會用到更加奇妙的幾何。譬如，有一類平面轉盤魔方“天竺葵”系列，與彭羅斯密鋪（Penrose Tiling）密切相關。值得一提的是，彭羅斯密鋪因著名數學家、物理學家Roger Penrose的研究而得名，他本人亦是有據可查的将魔方帶到1978年國際數學家大會上的人之一。

天竺葵魔方與彭羅斯密鋪

而在計算機上，甚至可以模拟出一些現實中不存在的魔方，進行更多的頭腦風暴。例如高維空間中的魔方，目前有4~7維魔方的模拟器，我們在屏幕上看到的是它們的三維“展開圖”，再在二維的屏幕上的投影，可以通過操作在不同維度上旋轉來觀察投影。

四維三階魔方示意圖

如圖，轉動一步的四維三階魔方：我們看到的是四維超立方體的三維展開圖，由八個三維立方體組成，每個三維立方體與原先三維三階魔方的一個面類似，由27塊“三維貼紙”構成。現在的視角下隻能看到8個三維立方體中的7個。

七維三階魔方示意圖

在計算機上，還可以模拟一些非歐式空間中的魔方，譬如三維雙曲空間中的三階魔方：

三維雙曲空間中的三階魔方示意圖

見識到了諸多複雜的魔方之後，讓我們暫時回到最常見的三階魔方的世界，探讨其與現代數學更加深刻的聯系。

中心塊、棱塊、角塊示意圖

如圖，在三階魔方上，我們稱有一個、兩個、三個顔色的塊分别為中心塊、棱塊、角塊。

在上高等代數習題課講到行列式的定義時，為了更直觀地說明置換的奇偶性，我曾拿魔方舉過例子：單獨旋轉三階魔方的一層90度，角塊和棱塊分别形成一個四循環，都是奇置換；二者合在一起，在魔方上形成一個偶置換。然而，單獨的棱塊對換或角塊對換都是奇置換，于是，三階魔方是不能單獨僅交換兩個棱塊或角塊的，兩者同時出現則是可能的。但在四階魔方上，一個棱塊被“劈成了兩半”，兩兩對換棱塊後可以得到三階魔方上出現不了的狀态。這算是“奇偶置換”的一個非常具體的應用了。

可能和不可能發生的情況

而與魔方關系最密切的數學分支，當屬代數學中的群論。維基百科的“群論”頁面的第一張圖片，就是一個三階魔方。

維基百科“Group”詞條截圖

數學中的“群”，指的是帶有一個二元運算的集合。其中二元運算滿足結合律，集合在此運算下封閉；集合存在一個“單位元”，任意元素與之運算後保持不變；對每個元素，存在一個“逆元”，使得元素與其逆元運算後得到單位元。例如，全體整數在通常的加法下構成一個群，單位元是0；全體非零有理數在通常的乘法下構成一個群，單位元是1；n個元素的所有置換在置換的複合下構成一個群，稱作對稱群Sn；n個元素的所有偶置換在置換的複合下也構成一個群，稱作交錯群An。

不難驗證，三階魔方通過轉動能達到的所有狀态構成一個群，稱作“三階魔方轉動群”（以下簡稱為“魔方群”）。具體來說，可以把魔方六個面上除中心塊外的48個方格編上号，這樣每一個通過轉動得到的狀态都是1到48的一個置換（注意到中心塊隻在原地旋轉，不會移動，所以不必編号），從而魔方群事實上可以看成是對稱群S48的一個子群，六個面的轉動對應的置換是這個群的一組生成元。在這種觀點下，也可以用GAP、Magma等群論計算軟件對其性質做一些分析。

标号後的三階魔方（展開圖）

最基礎的問題是求魔方群的階數，即三階魔方所有通過轉動能達到的狀态數。除剛才提到的“不能單獨交換兩個棱塊或兩個角塊”的限制外，不難驗證，還應有“不能單獨原地翻轉一個棱塊”與“不能單獨原地旋轉一個角塊”的限制；另外，還需檢查滿足這三條限制的所有狀态都是可以達到的。那麼，魔方群的階數為：

關于魔方群，一項最為重要的工作是“上帝之數（God’s number）”的确定。所謂上帝之數，指的是想象中“上帝”還原三階魔方需要的最多步數，也就是所有狀态所需的最少步數的最大值。最常見的計步方式被稱為“半轉度量（Half Turn Metric, HTM）”，即，将外層的六個面轉90度或180度都計為1步，那麼兩個狀态轉化所需的最小步數就是半轉度量。等價地來說，以三階魔方的所有狀态為頂點，把通過1步外層某個面90度或180度轉動能轉化的狀态用一條邊連接起來，從而得到一個有限圖，稱為魔方群的Cayley圖。圖上兩個狀态之間最短路徑的長度就是半轉度量。因此，這個Cayley圖的直徑就是上帝之數。

2010年8月8日，Tomas Rokicki在Domain of the Cube論壇上正式宣布，“三階魔方的上帝之數是20”，給對這一問題長達近30年的探索畫上了一個圓滿的句号。相關論文于2013年在期刊SIAM Journal on Discrete Mathematics上正式發表。其計算過程雖然利用群論做了一些簡化，但最終還是在谷歌的大量計算資源的支持下，耗時約35 CPU年（現實中幾周的時間），才得到了最後的結果。

CPU年是衡量算法運算量的一個單位，指每秒浮點運算次數為10億（1 GFLOPS）的參照機運行一年（8760小時）所進行的運算量，與具體用什麼CPU計算無關。

相關論文截圖

另外一項比較重要的結果是在魔方群的Cayley圖上找到一條Hamilton回路，即通過所有圖的頂點但不經過重複邊的回路。這個問題被稱為“惡魔算法”——由于Cayley圖的頂點傳遞性質，一個“惡魔”隻需要遵照Hamilton回路所對應的轉動序列一步步地擰魔方，總能在其中一步得到還原狀态。鑒于三階魔方的狀态如此之多，暴力搜索顯然是不可行的。2011年底、2012年初，Bruce Norskog先後對二階魔方、三階魔方解決了這個問題。他的做法十分巧妙，首先對魔方群構造出一個合适的群鍊，對最小的子群找到Hamilton回路後，想辦法把陪集連接起來，從而得到了大一層的子群的Hamilton回路，以此類推，最終得到最後的結果。

關于三階魔方轉動群，還有許多未解決的問題。例如，給定最自然的一組生成元（即六個面的90度轉動），找到其群表現（group presentation），即确定一組極小的生成關系。雖然這個問題聽起來很基礎，但确實還懸而未決。目前，對于二階魔方，人們已經找到了一個群表現，但這對三階的問題似乎沒有太大的啟發。

二階魔方轉動群的一個群表現

如圖，R, U, F分别對應二階魔方兩兩相鄰的三個面順時針轉動90度。

最後，我們再來對一般的魔方做一個初步的探讨。

絕大多數魔方的群結構都是比較簡單的，單獨看某一種n個塊的位置時，往往形成的是對稱群Sn或交錯群An，前者可以通過一步涉及奇偶變化的轉動轉化入後者的情形。于是從理論上破解魔方，隻需要對每一種塊找到一個三循環，再利用共轭（魔方中的術語叫Set up和Reverse）就能生成任意的三循環。交錯群An可以由所有的三循環生成，于是這樣就能解決這一類魔方了。而“構造出一個三循環”的最常用方法是利用換位子（魔方中的術語叫轉換機），可以從下例中略窺一二：

三階魔方上利用換位子構造的一個八步角塊三循環：

動圖由本文作者在參考網友模拟器的基礎上自制

通過共轭，把上面的角塊三循環變為另外三個角塊的三循環：

動圖由本文作者在參考網友模拟器的基礎上自制

在具體的魔方上，三循環的構造可能會極其複雜，有些魔方甚至可能需要用幾十步轉動才能實現循環某三個塊，而不去影響其它的塊。

然而，在很少的一部分魔方上能出現十分有趣的群。最簡單的例子是隻有相鄰兩個面能夠轉動的二階魔方，僅考慮這六個角塊的位置，它們的所有狀态構成的群不是S6，而是同構于S5！從魔方還原的角度看，這樣的魔方并不存在單獨的角塊三循環，在三個角塊歸位後，剩下三個角塊也會自動歸位。它的證明是多種多樣的，有一種巧妙而深刻的方法是利用有限域上的射影幾何，結合S5與射影一般線性群PGL(2, 5)的同構得到結果。事實上，這展示了S5到S6的例外嵌入，可以進一步用來構造S6的非平凡外自同構。

如果說上一個例子還不夠奇妙，幾周前，剛剛有設計師利用巧妙的機械結構設計出一個魔方，其所有狀态構成的群是有限單群分類中的26個散在單群中的M24！

M24 Cube示意圖

此外，雖然大多數魔方都與群論密切相關，但許多最新的魔方都不能完全被納入群論的框架下，即它們的所有狀态并不構成一個群。這樣的魔方無論是狀态數計算、公式的構造還是細緻的分析都會更加複雜。之前介紹過的天竺葵魔方就是一個例子，下面的直升機魔方則是此類魔方中更加經典的代表。

直升機魔方示意圖

如圖，一個能轉動的位置轉動無理數角度（arccos(1/3)，約等于70.53度）之後能夠繼續旋轉其它位置，且此時有一部分之前能旋轉的位置被阻擋，從而所有狀态不能構成一個群。

我想和大家分享的與魔方相關的内容大緻就是這些。限于篇幅，未能詳述。希望這篇文章可以給讀者帶來一點啟發。

文章來源：北京國際數學研究中心BICMR ，作者徐林霄

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!