北大老教授讲数学：北大数学博士生硬核科普
北大老教授讲数学：北大数学博士生硬核科普33阶魔方示意图魔方发展到如今，演化出了各种各样的变形。四阶、五阶魔方早已不稀奇，目前的最高阶魔方已经达到惊人的33阶。数学家John Conway肖像 魔方最为大众熟悉的是“竞速”方面。目前的三阶魔方单次还原世界纪录是由中国选手杜宇生保持的3.47秒。北京大学校友董百强和柯言也曾分别在最少步还原（给定一个打乱，选手需要在1个小时的限时内通过多次还原来找到最短的解法并记录下来）与三阶盲拧（先对魔方进行记忆，然后蒙眼进行复原）两个项目上打破过世界纪录。世界魔方协会庆祝杜宇生3.47s世界纪录
最近受疫情影响延迟开学，宅家多日。虽说对于我们基础数学专业的学生，一本书、一支笔、一叠纸，沉浸其中，不知不觉就能从白天思考到黑夜；但许久未见到熟悉的老师和同学们，难免也有些孤单和烦闷。于是，在学习研究之余，我也拾起了曾经狂热的爱好——魔方，聊以消遣。今天，我想和大家分享一下关于魔方及其与数学关系的一点思考。
01 魔方简介魔方，这个风靡全球的小小玩具，是匈牙利建筑学教授Ernő Rubik在1974年发明的。自1980年大规模生产以来，魔方早已走进了千家万户。魔方曾多次出现在公众视野中，从电影《当幸福来敲门》威尔•史密斯饰演的男主角通过复原魔方而得到工作实习机会，到近年来《最强大脑》《挑战不可能》等综艺节目中的表演，都体现了魔方作为常人眼中“高智商玩具”的一面。
电影《当幸福来敲门》剧照
近期刚刚因新冠肺炎不幸逝世的著名数学家John Conway也与魔方有千丝万缕的联系。他是匈牙利以外最早关注魔方的人之一，把魔方带到了1978年在芬兰赫尔辛基举办的第十八届国际数学家大会上。他也一直关心包括魔方在内的各种数学游戏和智力玩具，曾在专注于此的马丁•加德纳的专栏写过多篇文章，还出席过许多相关的活动。
数学家John Conway肖像
魔方最为大众熟悉的是“竞速”方面。目前的三阶魔方单次还原世界纪录是由中国选手杜宇生保持的3.47秒。北京大学校友董百强和柯言也曾分别在最少步还原（给定一个打乱，选手需要在1个小时的限时内通过多次还原来找到最短的解法并记录下来）与三阶盲拧（先对魔方进行记忆，然后蒙眼进行复原）两个项目上打破过世界纪录。
世界魔方协会庆祝杜宇生3.47s世界纪录
02 魔方与几何魔方发展到如今，演化出了各种各样的变形。四阶、五阶魔方早已不稀奇，目前的最高阶魔方已经达到惊人的33阶。
33阶魔方示意图
其它外形的魔方也层出不穷，从相对常见的其它四种正多面体（正四面体、正八面体、正十二面体、正二十面体），到不那么常见的半正多面体、卡塔兰立体，甚至更加奇特的几何体，都在魔方中能找到。要玩好魔方，无疑需要对这些几何体都有充分的了解，这大概就是“魔方能提高空间想象力”的来源吧。
不同外形的魔方
从魔方中，我们能够直观地看到各种几何体的联系。限于篇幅，仅举一例如下。正十二面体三阶五魔方可以改造成立方体外形的Hexaminx，此时六个面的图案仍然十分规整——这就体现了正十二面体与立方体的选取正十二面体的八个顶点连接，就可以得到一个立方体。从三阶五魔方改造出Hexaminx的过程，正是切掉六个“屋顶”形状的部分。这个关系在数学中也有用处，可以被用于证明正十二面体的保向对称群与交错群A5同构。
三阶五魔方与Hexaminx
Michael Artin《代数》一书中的相关证明
现代的一些魔方则会用到更加奇妙的几何。譬如，有一类平面转盘魔方“天竺葵”系列，与彭罗斯密铺（Penrose Tiling）密切相关。值得一提的是，彭罗斯密铺因著名数学家、物理学家Roger Penrose的研究而得名，他本人亦是有据可查的将魔方带到1978年国际数学家大会上的人之一。
天竺葵魔方与彭罗斯密铺
而在计算机上，甚至可以模拟出一些现实中不存在的魔方，进行更多的头脑风暴。例如高维空间中的魔方，目前有4~7维魔方的模拟器，我们在屏幕上看到的是它们的三维“展开图”，再在二维的屏幕上的投影，可以通过操作在不同维度上旋转来观察投影。
四维三阶魔方示意图
如图，转动一步的四维三阶魔方：我们看到的是四维超立方体的三维展开图，由八个三维立方体组成，每个三维立方体与原先三维三阶魔方的一个面类似，由27块“三维贴纸”构成。现在的视角下只能看到8个三维立方体中的7个。
七维三阶魔方示意图
在计算机上，还可以模拟一些非欧式空间中的魔方，譬如三维双曲空间中的三阶魔方：
三维双曲空间中的三阶魔方示意图
03 三阶魔方转动群见识到了诸多复杂的魔方之后，让我们暂时回到最常见的三阶魔方的世界，探讨其与现代数学更加深刻的联系。
中心块、棱块、角块示意图
如图，在三阶魔方上，我们称有一个、两个、三个颜色的块分别为中心块、棱块、角块。
在上高等代数习题课讲到行列式的定义时，为了更直观地说明置换的奇偶性，我曾拿魔方举过例子：单独旋转三阶魔方的一层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度。
04 进一步探讨最后，我们再来对一般的魔方做一个初步的探讨。
绝大多数魔方的群结构都是比较简单的，单独看某一种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 ，作者徐林霄
