丘成桐中學數學獎中的魔方問題

2018年丘成桐中學科學數學金獎論文是“群論和五魔方”，作者用群論知識解出了五魔方的群結構，給出了求解五魔方的算法。

五魔方（megaminx）是一個正十二面體，每個面是一個正五邊形，原始狀態下每個面各有一個顏色，一共有12個不同的顏色（還有一種五魔方有6個不同的顏色）。五魔方玩法和三階魔方一樣，通過旋轉各面恢復原始狀態，只是難度更大。

圖片來自獲獎者論文[1]

五魔方的群結構與三階魔方有所不同，不過研究方法相同，如果掌握了三階魔方群的研究方法，不難導出五魔方的群結構，因此適合中學生研究。

三階魔方（以下簡稱魔方）是一款世界流行的玩具，由26個可見的小立方塊組成一個立方體，原始狀態下立方體六個面各有一個顏色，通常是紅、橙、藍、綠、黃和白（見下圖）。旋轉魔方的任意一個面或中間層，會改變魔方的顏色分布，經過一系列隨機旋轉后原始狀態被打亂，玩家需要旋轉魔方恢復原始狀態。

圖片來自紐約現代藝術博物館https://www.moma.org/collection/works/2908?artist_id=5069&locale=zh&page=1&sov_referrer=artis

匈牙利建筑學教授厄爾諾·魯比克（Erno? Rubik）在1974年發明了魔方，起初只是為了尋找一種由很多可動部件組成且任意活動都不會散架的結構，后來他發現魔方可以當玩具玩，于是在1975年申請了專利。1980年初在Ideal Toy公司的推廣下成為風靡全球的玩具，并且有了新名字叫魯比克立方體（Rubik's Cube）。

1981年Douglas Hofstadter在《科學美國人》雜志上撰文詳細介紹了魔方，促進了魔方的流行，他本人用了7個月累計花費50個小時復原了魔方。從1980年到1983年全球賣出了約2億個魔方，是魔方歷史上最瘋狂的時刻。?

為什么魔方令大眾著迷？一個原因是魔方能夠產生數量巨大的不同狀態，大約有4.3×1019個。這么多狀態如果一秒鐘數100萬個也要140萬年才能數完，因此每個人拿到的魔方狀態可能都不一樣，看似簡單然變化無窮，容易上手卻琢磨不透。

圖片來自文獻[4]

魔方也吸引了數學家的注意，John Conway 很早就有了一個魔方，David Singmaster 在1978年8月的國際數學家大會上見到了魔方，迫不及待地用一本書換來一個，然后花了兩周時間找到了復原魔方的通用方法。Singmaster在復原中設計了一套標記，并且運用了數學中的群論，他總結成書，在1980和1981年多次出版[2]。根據Singmaster的算法，只需要幾分鐘就可以復原魔方。

Singmaster的書在1981年賣出了5到6萬本，不過跟另一本書比起來就是小巫見大巫了。James?G.?Nourse是斯坦福大學化學系員工，在1980年圣誕節前買了一個魔方，本打算作為圣誕節禮物送人，沒想到自己竟然在節日期間復原了魔方，于是寫了本書講解他的復原方法[3]。Nourse更沒想到的是這本書在1981年賣出了668萬本，成為當年最暢銷的書籍。

Christoph?Bandelow 隨后也出版了一本書，介紹了魔方群的數學結構[4]。Bandelow 還討論了魔方的變體，除了立方體形狀外還有正四面體，正八面體，正十二面體（五魔方）和正二十面體，這五個正多面體統稱柏拉圖立體(Platonic solids)，是全部的正多面體。

正多面體魔方有很多變化，比如二階魔方、四階魔方（Rubik’sRevenge）、五階魔方（Professor’s?Cube）,金字塔魔方（Meffert's Pyraminx）等等。?

二階魔方? Meffert's Pyraminx圖片來自文獻[4]?

 

1982年魔方無論是復原方法，還是數學理論，都有了很大進展，除了一個重要問題還沒有解決，即Singmaster提出的上帝之數，也就是復原任意狀態的魔方所需最小步數的上界。Morwen B. Thistlethwaite給出了一個不超過52步的算法，將這個上界限制在52步以下。

大眾的狂熱沒有堅持多久，到1982年底開始漸漸退去。對數學家來說，魔方把抽象的群論可視化，是非常好的教學和科研工具[5]。普林斯頓數學系教授曼紐爾·巴爾加瓦(Manjul Bhargava)在讀研究生的時候，經常坐在宿舍里擺弄著一個特殊的二階魔方，魔方的8個角塊有八個字母a,b,c,d,e,f,g,h，代表8個整數，他覺得這個2×2×2結構的魔方中隱藏著高斯復合問題(gauss composition)的秘密，努力地尋找答案。

無論是玩魔方，還是研究魔方，都離不開對魔方的標記。Singmaster根據魔方每個面所處的位置用字母L(左面)、R(右面)、F(前面)、B(后面)、U(上面)、D(底面)表示，然后根據人們的操作習慣定義任意面順時針旋轉90度為基本操作，用各面字母的黑體L,R,F,B,U,D表示，逆時針旋轉90度則表示為L',R',F',B',U',D'。

有了標記后，描述魔方的旋轉就非常方便。比如L表示L面順時針旋轉90度，(L')2表示L面逆時針旋轉180度，DFD'F'表示從左至右依次執行D、F、D'、F'操作。

魔方每個面有9個小正方形，六個面一共有54個小正方形，原始狀態下54個小正方形處在各自的位置上，對應一個排列，不妨記作1，2，3，……，54。一個操作是一個置換，變換魔方上小正方形的位置，得到一個新的排列。理論上這樣的排列有54！（54！=1×2×3···×53×54）個，對應54！個狀態。

實際上操作魔方得到的狀態遠沒有這么多。54個小正方形分布在6個中心塊，8個角塊和12個棱塊上，如下圖陰影部分所示，每個中心塊分到一個小正方形，每個角塊有3個、棱塊有2個。

旋轉魔方的任意面，角塊和棱塊的位置發生改變，而中心塊位置不變。如果旋轉中心塊所在的中間層，等價于逆向旋轉相鄰的兩個面，因此理論上只需要考慮面的旋轉就行了。

6個位置不變的中心塊的顏色代表魔方各個面的顏色，從而魔方的狀態只由角塊和棱塊決定。由于角塊變到角塊，棱塊變到棱塊，因此8個角塊所有可能的位置有8！個，12個棱塊所有可能的位置有12個。

每個角塊的三個小正方形在角塊轉動中可能產生順時針或逆時針旋轉，導致3個不同的定向，同樣每個棱塊會產生2個不同的定向(兩個小正方形的對換)，因此所有可能的狀態有8！×12！×38×212個，其中能夠由原始狀態通過操作魔方得到的狀態只有十二分之一，也就是8！×12！×37×210個，約 4.3×1019個。這些狀態稱為原始狀態的軌道，也就是全部的有效狀態。
五魔方有20個角塊，30個棱塊，有效狀態有20！×30！×319×227，約1068個，遠遠多于魔方。

群是一個常用的漢字，表示聚集在一起的人或物，數學上群被抽象成一個非空集合，集合中的元素可以是數，也可以是矩陣、置換等，并且還有一個單位元、每個元素有逆元，任意兩個元素之間服從一種運算，滿足結合律且運算結果仍然在集合中。全部整數的集合對于加法運算就是一個群，0是單位元。

魔方中的很多操作都可以構成群。比如由操作R得到的集合{R,R2,R3,I} 就是一個群，其中單位元是I，滿足R4=I。可以證明，魔方所有操作的集合構成一個群，稱為魔方群。魔方群中的運算是復合運算，假設M1，M2是魔方群中的兩個操作，它們的復合M1M2表示對魔方先進行M1操作，再進行M2操作，有時復合運算用符號表示為M1·M2。類似的，五魔方有五魔方群。

在2014年魔方誕生40周年之際，一篇發表的學術文章宣告了上帝之數的解決[6]，這個數是20，也就是從魔方的任意一個有效狀態恢復到原始狀態最多不超過20步（這里的一步使用half turn metric度量，指面旋轉90度或180度都算一步）。在這一年召開的國際數學家大會上，曼紐爾·巴爾加瓦獲得了菲爾茲獎，委員會在介紹他的工作時寫到，“巴爾加瓦相信有更好的方法解高斯復合問題。然后有一天，他在玩魔方時，找到了答案。

參考文獻
[1]http://www.yau-awards.science/wp-content/uploads/2018/11/Gerald-Jiarong-Xupaper_1402.pdf
[2]David Singmaster，?Notes on Rubik's Magic Cube, 1981.
[3]James?G.?Nourse，The Simple Solutions to Cubic Puzzles，1981.
[4]Christoph?Bandelow, Inside Rubik's Cube and Beyond, 1982.
[5]J. Chen,?Group theory and the rubik's cube, Lecture Notes.
[6]Tomas Rokicki,et al.,The Diameter of the Rubik’s Cube Group is Twenty. SIAM J. DISCRETE MATH. Mathematics Vol. 27, No. 2, pp. 1082–1105.