魔方和群论

        暑假课程预告

        报告人：顾险峰  美国纽约州立大学石溪分校计算机系，哈佛大学数学科                          学和应用中心客座教授

        时间：  2018年7月8日、15日、22日、29日 每周日  14:30-16:00

        地点：  清华大学近春园西楼三层报告厅

        题目：  计算共形几何

        直播：  online.conformalgeometry.org  

---

魔方是广大人民群众喜闻乐见的智力玩具，无数人沉浸其中，废寝忘食，痴迷不已。但是绝大多数魔方爱好者通过识别模式，运用记忆的口诀来解魔方，对于口诀如何得来，如何创造新的诀窍并没有深入思考。这里，我们希望能够用魔方来揭示其背后更加普适的规律，从而可以将其思想深化和推广，应用于更加复杂的场景。我们主要用群论来进行探讨。

群论本质上是描述大自然中的对称性，探究各种变换中存在的内在结构。群论是现代数学不可或缺的工具，更是现代物理的理论基础。但是群论相对抽象，难以琢磨，比较难以入门。魔方这一游戏足够精巧，能够反映出群论大部分的思想，同时也足够复杂，使得群论能够得以运用。因此，通过深入思考魔方就可以便捷地领悟到群论的要义。

群论的基本概念

一个群（Group）由集合G和乘法算子*构成，满足：

1. 封闭性（closure）

2. 结合律（associative）

3. 单位元（identity element）

4. 逆元（invrese element）

令S是群G的子集，如果G中的任意一个元素都可以表示成S中元素及其逆元的有限乘积，则我们说S生成（generate）了G。由S生成的子群记成。一个群G被称为是循环群（cyclic），如果存在一个元素，满足。

一个群（G，*）作用（action）在一个非空几何A是一个映射 ，给定一个元素, 得到A的另外一个元素，记为，满足下列两个条件：

如果G作用在集合A上，那么的轨道（orbit）是集合。如果群作用只有一条轨道，我们说群作用是传递的（transitive）。

群中两个元素被称为彼此共轭(conjugate)，如果存在一个元素，满足。群（G，*）的子集H被称为是子群（subgroup），如果（H，*）构成群。子群N被称为是G的正规子群（normal subgroup），，如果N在共轭作用下不变，。

令和是两个群，它们的直积成群，乘法定义如下： 。

令和是两个子群，是半积，如果

1.  ；

2. ，这里是A的单位元；

3. ，是A的正规子群。

对称群

n个字母排列（permutation）在复合（composition）下构成n阶对称群，记成。例如，

。

一个k-轮换是对称群中的一个元素， ，满足，的支集（support）为。如果j不属于支集，，那么。两个轮换和被称为是分离的（disjoint），如果它们的交集为空。每个2-轮换被称为是一个对换。

任何一个排列可以分解成分离的轮换之积。例如，

,

可以分解为轮换之积 。每个k-轮换可以被分解成对换之积，。由此所有的对换生成整个对称群。

任意一个置换可以被分解成对换之积，如果有奇数个对换，那么，被称为是奇置换；如果有偶数个对换，那么，被称为偶置换。所有的偶置换构成一个正规子群，记为，被称为是交错群。任意一对对换可以由一系列3-轮换生成，因此，所有的3-轮换生成了交错群。

魔方状态表示

图1. 魔方（Rubik's Cube）的初始状态。

如图1所示，魔方整体是一个立方体，被分成共27个小立方体，每个小立方体小块被称为“块”（cubie）。中心的立方体小块外面看不到，可以忽略不计。魔方表面被分成54个小正方形，带有不同的颜色，每个小正方形被称为一个“面”（facet）。魔方整体的6个侧面记为顶面Up，底面Down，左面Left，右面Right，前面Front和后面Back。在初始状态，6个侧面内所有的面带有相同的颜色，对应的颜色为白色，黄色，绿色，蓝色，红色和橙色。魔方的26个立方体小块中，有8个角块，12个棱块和6个中心块。每个角块有3个面，每个棱块有两个面，每个中心块有1个面。在操作中，我们一直固定6个中心块的位置。

魔方的每个侧面可以整体转动，顺时针转动90度的操作被称为是基本操作，依次记为，逆时针转动90度的操作为基本逆操作，记做。一系列基本操作和基本逆操作的复合构成一个操作（operation），所有操作构成的群被称为是魔方群 （Rubik's Cube Group），记成。魔方群的结构是我们研究的主要问题之一。

我们将魔方拆开，再重新组装回去，所有的角块和棱块的位置被打乱。同时每一角块的三个面的顺序也被旋转，每个棱块的两个面也被颠倒，如此得到了魔方的一个状态（state）。所有的状态构成魔方的状态空间，记为。魔方操作群作用在魔方状态空间上：如果一个操作，将魔方的一个状态变换成另一个状态，则我们记为 ，并且我们称两个状态 在群作用下彼此等价。状态空间被的群作用分解为不同的等价类，每一个等价类被称为是一条轨道（orbit）。初始状态所处的轨道被称为是合法轨道，合法轨道中的每个状态被称为是合法状态。如何判定一个状态是否合法，也是我们需要回答的问题。

图2. 角块上的位置标记。

为了精确描述魔方的状态，我们将魔方的54个面进行位置标记。在魔方群的作用下，6个中心块上的面位置不动，因此我们只需标记余下48个面。魔方群的每个操作可以被等价地表示成1到48的一个排列，即对称群中的一个元素。这种表示虽然信息完全，但是非常不直观。

另外一种更为直观的方法是将角块和棱块进行位置标记。如图2所示，对于每个角块我们任意选择一个面写上位置序号，共有8个角块从1到8排列。

图3. 棱块上的位置标记。

如图3所示，对于每个棱块，我们任意选择一个面写上位置序号，共有12个棱块从1到12排列。我们将初始状态定义的标记方式记为魔方坐标系，在操作中，魔方的角块和棱块在变动，但是魔方坐标系保持不动。

假设是魔方群中的一个操作，将魔方的一个角块映到了魔方坐标系中的

某一个角块的位置，这样操作产生角块的一个排列，得到中的一个元素；同时将魔方中的每一个棱块变换到魔方坐标系中的某一个棱块的位置，如此得到棱块的一个排列，表示成中的一个元素。这两个排列描述了角块和棱块的位置变化，但是没有反映每个角块或棱块“定向”（orientation）的变化：每个棱块的两个带颜色的面是否互换，每个角块三个带颜色的面是否发生了旋转。

图4. 定向标记。

如图4所示，我们为每个面添加另外一种标记，称之为定向标记。考察每个角块，带有位置标记的面上定向标记为0，另外两个面上标记为1和2，使得角块定向标记为{01,2}的三个面顺时针排序。同样，考察每个棱块，带有位置标记的面上定向标记为0，另外的面上标记为1。我们用向量，来表示角块的定向。考察在魔方坐标系中的第i个角块，记为。假设在目前状态中，被魔方的第j个角块所占据。的某个面占据的第0个面，

等于的这个面上的定向标记。（换言之，如果和带有位置标记的面彼此重合，那么为0；如果需要顺时针旋转120度才会使得带位置标记的面重合，那么为1；如果需要顺时针旋转240度才会使得带位置标记的面重合，那么为2。）同样，我们用向量，来表述棱块的定向。考察在魔方坐标系中的第i个棱块，记为。假设在目前状态中，被魔方的第j个棱块所占据。的第0个面被的某个面占据，等于的这个面上的定向标记。（等价的，如果和带有位置标记的面彼此重合，那么为0；否则，如果和带有位置标记的面彼此不重合，那么为1。）由此，我们用4元组来表述魔方的一个状态：

合法状态的必要条件

假设是魔方群中的一个操作，，，。每个基本操作都是一个角块4-循环和一个棱块4-循环的乘积。例如顺时针旋转右侧面，。每个4-循环可以分解成3个对换（2-循环），因此，和的奇偶性相同，即。

我们考察角块定向的变化。假设作用在初始状态，得到最终状态为；另外一个操作，作用在初始状态所得到的状态为。那么，操作作用在初始状态所得到的最终状态满足等式

，

这里代表两个排列的乘积（复合），代表排列作用在向量上，即将向量的分量重新排列。

比如，我们令h为基本操作，即魔方群的生成元，得到如下运算规则：

我们看到的各个分量之和与的各个分量之和在模3下同余；的各个分量之和与的各个分量之和在模2下同余。

由此，我们得到一个状态是合法态的必要条件是：

1.   ，角块和棱块排列的奇偶性相同；

2. ，角块的总扭转为0；

3. ，棱块的总翻转为0.

如果一个状态满足合法性的三个必要条件，那么是否存在一个魔方群中的操作，将初始状态变换成？为此我们构造一些基本操作序列。

交换子和共轭 Commutator & Conjugate

魔方群非常庞大，我们需要寻找符合人类直觉的关键几个操作：3个角块位置（position）的轮换（cycle），3个棱块位置的轮换，两个角块定向（orientation）的旋转（twist），两个棱块定向的翻转（flip）。这几个关键复杂操作由简单操作依照两条法则合成：交换子（commutator）和共轭（conjugate）。交换子可以生成3-轮换，共轭可以实现坐标变换。

交换子 魔方群一个非阿贝尔群，给定两个操作，其交换子衡量了可交换性，。如果交换子等于单位元，则两个操作可以交换。假设操作影响了很多角块和棱块，也影响了很多角块和棱块，如果一个角块只被作用，不被所影响，（或者只被作用，不被所影响），那么角块经过交换子操作后，位置和定向会被复原。同样的结论对于棱块也成立。如此来看，虽然操作和各自影响了很多角块和棱块，如果它们没有共同影响的角块或者棱块，那么为单位元，所有的角块和棱块复原。如果操作和共同只影响了一个角块，将角块转到了，将角块变换到，那么交换子是一个3-轮换。

共轭 关于的共轭定义为，其作用相当于群中的坐标变换，我们先用将魔方变换到新的坐标系下，然后在新坐标系下进行操作，然后用返回到初始坐标系。例如是3-轮换，将映射到，那么给出3-轮换。

角块位置3-轮换

我们下面用交换子和共轭来构造关键操作。首先，我们构造角块3-轮换。

图5. 操作。

由，，得到。同时，。由此和共同影响，将映到，将映到。如图6所示，交换子给出3-轮换，。

图6. 交换子。

，变换角块，与的共轭得到3-轮换，，如图7所示。

图7. ，角块位置3-轮换。

棱块位置3-轮换

我们将和Front面、Back面中间的一层顺时针旋转90度，这一操作记为。

，,，和共同影响棱块和，交换子为，如图8所示。经过化简，我们将分解成基本操作的序列，得到等下操作序列。

图8. 。

，关于的共轭等于，如图9所示。

图9. ，棱块3-轮换。

角块定向旋转

图10. 符号定向标记。

为了考虑角块和棱块定向的变换，我们需要使用更为复杂的标记法，如图10所示。在初始位置，魔方的顶（底、左、右、前、后）侧面（side）的每个面（facet）都标记成U（D、L、R、F、B）。每个角块可以由其所有面（facet）的标记有序组来表示。例如，第一个角块可以被表示成。

每个操作被表示成循环之积，例如。例如2-循环，意味着dfr的底面（前面、右面）映成dbl的底面（背面、左面）。

图11. 。

如图11所示，将ufl，dlf，ubr，fl，br映成lfd，rdf，bdr，df，dr。关于的共轭，如图12所示，

图12. 

考察操作，那么和共同影响了角块ufl和ubr，它们的交换子具有非常简洁的形式

,

即ufl逆时针旋转120度，ubr顺时针旋转120度，如图13所示。

图13. 角块定向旋转操作。。

我们可以用共轭的方法实现任意一对角块定向的旋转。例如，

，将urf映射成bru，因此共轭算子作用后得到 。

图14. 角块定向旋转操作。

经过共轭操作，我们可以实现任意两个角块定向的旋转，一个顺时针，另外一个逆时针旋转120度。

棱块定向翻转

图15. 。

图15详细解释了，上面帧显示了诱导了中心块的轮换， 顶层带定向角块的4-循环，顶层两个棱块加上定向构成4-循环；下面帧显示了带定向棱块的8-循环，由此我们得到

,

如图16所示，4次幂消去4-循环，我们得到

图16. 。

同理，如图17所示，。

图17. 。

图18. 棱块定向翻转，。

两种操作复合之后，我们得到非常简洁的棱块定向翻转公式：。

经过共轭操作，我们可以实现任意两个棱块定向的同时翻转。

合法状态的充分条件

给定一个魔方状态，满足：

1.   ，角块和棱块排列的奇偶性相同；

2. ，角块的总扭转为0；

3. ，棱块的总翻转为0.

我们来构造魔方群中的一个操作，将初始状态变换成。

我们分4步来构造，这种构造方法实际上给出了解魔方的一种算法。

1. 角块位置归位 如果和同时为奇排列，我们增加一步基本操作R。由此不妨假设和同时为偶排列。

将分解成一系列彼此不交的循环（cycles），将循环分解成一系列对换（swaps）；将所有对换配对，每对对换可以用3-循环生成。因为我们已经构造了所有的角块位置3-循环（图7），因此我们可以用一系列角块位置3-循环将归位成初始状态，并且保持所有棱块的位置和定向不变。

2. 棱块位置归位 我们将分解成3-循环的乘积，因为我们已经构造了所有的角块位置3-循环（图9），因此我们可以用一系列棱块位置3-循环将归位成初始状态，并且保持所有角块的位置和定向不变。

3. 角块定向归位 我们将中非0的项配对，每对中包含一个+1项和一个+2项，然后用角块定向旋转操作及其共轭（图14）将每一对角块的定向同时归位。这种操作不会改变角块和棱块的位置，也不会改变棱块的定向。

4.棱块定向归位 我们将中非0的项配对，每对中包含两个+1项，然后用棱块定向翻转操作及其共轭（图18）将每一对棱块的定向同时归位。这种操作不会改变角块和棱块的位置，也不会改变角块的定向。

经过上面4不操作之后，我们将魔方变换到初始状态。由此，我们证明了魔方的基本定理。

定理（魔方基本定理）魔方状态可解的充分必要条件是：

1.   ，角块和棱块排列的奇偶性相同；

2. ，角块的总扭转为0；

3. ，棱块的总翻转为0.

魔方群的结构

通过以上分析，我们看到魔方群可以分解成位置变换群，和定向变换群的半积（semi-product）。位置变换群可以分解成角块位置变换群，棱块位置变换群和的直积，这是因为角块位置的排列和棱块位置的排列奇偶性相同；定向变换群可以分解成角块定向变换群和棱块定向变换群的直积。

定理（魔方群结构）魔方群可以分解为：

角块位置3-循环生成了，棱块3-循环生成了，角块定向旋转生成了，棱块定向翻转生成了。

1981年7月，Thistlethwaite 给出了魔方群的另外一种分解方法，将魔方群分解成系列嵌套子群，，

Thistlethwaite的思想就是逐步降解魔方所处的群到更小的子群，最后到单位子群，也即还原状态。Thistlethwaite的思想已经被消化成人类可用的算法，52步之内可以解出所有状态。

上帝之数

我们看到，如果将魔方拆解，重新组装，总共会有  多种状态，其中只有12分之1是合法状态。那么我们最少需要多少步操作可以解任意状态的魔方？这个最少步数被称为是“上帝之数”（God Number）。首先第一步我们可以选择{U,D,L,R,F,B}及其逆操作，共12种可能。第二步，我们有11种可能性；以后每步至多有11种可能性，因此n步之后，操作序列所能达到的状态至多只有。如果我们希望n步操作覆盖所有状态，我们得到不等式

因此得到。上面Thistlethwaite的方法证明了上帝之数不大于52步。经过谷歌的35计算机年的暴力计算，最终于2010年7月证明三阶魔方的上帝之数正是20HTM（Half Turn Metric）。有一种很著名的最远状态，被称作SuperFlip，其打乱公式为：

SuperFlip需要至少20步才能被解决。

图19. SuperFlip。

总结

这里我们应用群论的基本知识来证明魔方的可解性，其基本思想是将魔方群分解成较为简单的子群的乘积，然后构造每个子群的生成元。生成元的构造过程中主要使用了交换子和共轭的方法，化繁为简。这种方法具有很强的普适性，可以直接推广到其他复杂情形。

---

请长按下方二维码，选择 “识别图中二维码”，即可关注。

【老顾谈几何】邀请国内国际著名纯粹数学家，应用数学家，理论物理学家和计算机科学家，讲授现代拓扑和几何的理论，算法和应用。

回复“目录”，可以浏览往期精华；回复“智商”，可以阅读“如何从大脑形状判断一个人的智商”；回复“象牙塔”，可以阅读“纯粹数学走出象牙塔”；回复“概览”，可以阅读“计算共形几何概览”。