CurvatureFlow的个人博客分享 http://blog.sciencenet.cn/u/CurvatureFlow

博文

魔方和群论

已有 9883 次阅读 2019-2-10 23:33 |系统分类:观点评述

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


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




群论的基本概念

一个群(Group)由集合G和乘法算子*构成,满足:

1.封闭性(closure)640?wx_fmt=gif

2.结合律(associative)640?wx_fmt=gif

3.单位元(identity element)640?wx_fmt=gif

4.逆元(invrese element)640?wx_fmt=gif


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


一个群(G,*)作用(action)在一个非空几何A是一个映射 640?wx_fmt=gif,给定一个元素640?wx_fmt=gif, 得到A的另外一个元素,记为640?wx_fmt=gif,满足下列两个条件:

1.640?wx_fmt=gif

2.640?wx_fmt=gif

如果G作用在集合A上,那么640?wx_fmt=gif轨道(orbit)是集合640?wx_fmt=gif。如果群作用只有一条轨道,我们说群作用是传递的(transitive)。


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


640?wx_fmt=gif640?wx_fmt=gif是两个群,它们的直积640?wx_fmt=gif成群,乘法定义如下:640?wx_fmt=gif 640?wx_fmt=gif


640?wx_fmt=gif640?wx_fmt=gif是两个子群,640?wx_fmt=gif半积,如果

1. 640?wx_fmt=gif

2.640?wx_fmt=gif,这里640?wx_fmt=gif是A的单位元;

3.640?wx_fmt=gif640?wx_fmt=gif是A的正规子群。




对称群

n个字母排列(permutation)在复合(composition)下构成n阶对称群,记成640?wx_fmt=gif。例如640?wx_fmt=gif

640?wx_fmt=gif

一个k-轮换640?wx_fmt=gif是对称群中的一个元素, 640?wx_fmt=gif,满足640?wx_fmt=gif640?wx_fmt=gif支集(support)为640?wx_fmt=gif。如果j不属于支集,640?wx_fmt=gif,那么640?wx_fmt=gif。两个轮换640?wx_fmt=gif640?wx_fmt=gif被称为是分离的(disjoint),如果它们的交集为空。每个2-轮换被称为是一个对换


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

640?wx_fmt=gif,

可以分解为轮换之积 640?wx_fmt=gif。每个k-轮换可以被分解成对换之积,640?wx_fmt=gif。由此所有的对换生成整个对称群640?wx_fmt=gif


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



魔方状态表示

640?wx_fmt=png

图1. 魔方(Rubik's Cube)的初始状态


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


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


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


640?wx_fmt=png

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


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


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


640?wx_fmt=png

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


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


假设640?wx_fmt=gif是魔方群中的一个操作,将魔方的一个角块映到了魔方坐标系中的

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


640?wx_fmt=png

图4. 定向标记。


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

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


640?wx_fmt=gif




合法状态的必要条件

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


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

640?wx_fmt=gif

这里640?wx_fmt=gif代表两个排列的乘积(复合),640?wx_fmt=gif代表排列640?wx_fmt=gif作用在向量640?wx_fmt=gif上,即640?wx_fmt=gif将向量640?wx_fmt=gif的分量重新排列。


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


640?wx_fmt=png

我们看到640?wx_fmt=gif的各个分量之和与640?wx_fmt=gif的各个分量之和在模3下同余;640?wx_fmt=gif的各个分量之和与640?wx_fmt=gif的各个分量之和在模2下同余。


由此,我们得到一个状态640?wx_fmt=gif是合法态的必要条件是:

  1.  640?wx_fmt=gif ,角块和棱块排列的奇偶性相同;

  2. 640?wx_fmt=gif,角块的总扭转为0;

  3. 640?wx_fmt=gif,棱块的总翻转为0.


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



交换子和共轭 Commutator & Conjugate

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


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


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



角块位置3-轮换

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


640?wx_fmt=png

图5. 操作640?wx_fmt=gif


640?wx_fmt=gif640?wx_fmt=gif,得到640?wx_fmt=gif。同时,640?wx_fmt=gif。由此640?wx_fmt=gif640?wx_fmt=gif共同影响640?wx_fmt=gif640?wx_fmt=gif640?wx_fmt=gif映到640?wx_fmt=gif640?wx_fmt=gif640?wx_fmt=gif映到640?wx_fmt=gif。如图6所示,交换子给出3-轮换,640?wx_fmt=gif

640?wx_fmt=png

图6. 交换子640?wx_fmt=gif


640?wx_fmt=gif640?wx_fmt=gif变换角块640?wx_fmt=gif,与640?wx_fmt=gif的共轭得到3-轮换,640?wx_fmt=gif,如图7所示。


640?wx_fmt=png

图7. 640?wx_fmt=gif角块位置3-轮换



棱块位置3-轮换

我们将和Front面、Back面中间的一层顺时针旋转90度,这一操作记为640?wx_fmt=gif

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


640?wx_fmt=png

图8. 640?wx_fmt=gif


640?wx_fmt=gif640?wx_fmt=gif关于640?wx_fmt=gif的共轭等于640?wx_fmt=gif,如图9所示。

640?wx_fmt=png

图9. 640?wx_fmt=gif棱块3-轮换



角块定向旋转

640?wx_fmt=png

图10. 符号定向标记。


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


每个操作被表示成循环之积,例如640?wx_fmt=gif。例如2-循环640?wx_fmt=gif,意味着dfr的底面(前面、右面)映成dbl的底面(背面、左面)。


640?wx_fmt=png

图11. 640?wx_fmt=gif


如图11所示,640?wx_fmt=gif将ufl,dlf,ubr,fl,br映成lfd,rdf,bdr,df,dr。640?wx_fmt=gif关于640?wx_fmt=gif的共轭640?wx_fmt=gif,如图12所示,

640?wx_fmt=png

图12. 640?wx_fmt=gif


考察操作640?wx_fmt=gif,那么640?wx_fmt=gif640?wx_fmt=gif共同影响了角块ufl和ubr,它们的交换子具有非常简洁的形式

640?wx_fmt=gif,

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


640?wx_fmt=png

图13. 角块定向旋转操作。640?wx_fmt=gif


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

640?wx_fmt=gif640?wx_fmt=gif将urf映射成bru,因此共轭算子作用后得到 640?wx_fmt=gif


640?wx_fmt=png

图14. 角块定向旋转操作


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

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



棱块定向翻转

640?wx_fmt=png

640?wx_fmt=png

图15. 640?wx_fmt=gif


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


640?wx_fmt=gif,

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


640?wx_fmt=gif


640?wx_fmt=png

图16. 640?wx_fmt=gif


同理,如图17所示,640?wx_fmt=gif

640?wx_fmt=png

图17. 640?wx_fmt=gif


640?wx_fmt=png

图18. 棱块定向翻转640?wx_fmt=gif


两种操作复合之后,我们得到非常简洁的棱块定向翻转公式:640?wx_fmt=gif


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



合法状态的充分条件

给定一个魔方状态640?wx_fmt=gif,满足:

  1.  640?wx_fmt=gif ,角块和棱块排列的奇偶性相同;

  2. 640?wx_fmt=gif,角块的总扭转为0;

  3. 640?wx_fmt=gif,棱块的总翻转为0.

我们来构造魔方群中的一个操作640?wx_fmt=gif,将初始状态变换成640?wx_fmt=gif


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


1. 角块位置归位 如果640?wx_fmt=gif640?wx_fmt=gif同时为奇排列,我们增加一步基本操作R。由此不妨假设640?wx_fmt=gif640?wx_fmt=gif同时为偶排列。

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


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


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


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


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


定理(魔方基本定理)魔方状态640?wx_fmt=gif可解的充分必要条件是:

  1. 1. 640?wx_fmt=gif ,角块和棱块排列的奇偶性相同;

  2. 2.640?wx_fmt=gif,角块的总扭转为0;

  3. 3.640?wx_fmt=gif,棱块的总翻转为0.



魔方群的结构

通过以上分析,我们看到魔方群可以分解成位置变换群,和定向变换群的半积(semi-product)。位置变换群可以分解成角块位置变换群,棱块位置变换群和的640?wx_fmt=gif直积,这是因为角块位置的排列和棱块位置的排列奇偶性相同;定向变换群可以分解成角块定向变换群和棱块定向变换群的直积。


定理(魔方群结构)魔方群可以分解为:


640?wx_fmt=gif


角块位置3-循环生成了640?wx_fmt=gif,棱块3-循环生成了640?wx_fmt=gif,角块定向旋转生成了640?wx_fmt=gif,棱块定向翻转生成了640?wx_fmt=gif


1981年7月,Thistlethwaite 给出了魔方群的另外一种分解方法,将魔方群分解成系列嵌套子群,640?wx_fmt=gif

640?wx_fmt=gif

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


上帝之数

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

640?wx_fmt=gif

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

640?wx_fmt=gif

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


640?wx_fmt=png

图19. SuperFlip。



总结

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

原文发布在【老顾谈几何】公众号 2018年7月3日



http://blog.sciencenet.cn/blog-2472277-1161562.html

上一篇:简介医学影像配准的基本算法
下一篇:魔方和群论(2)

20 郭维 张学文 胡大伟 刘士勇 郭战胜 王卫 惠小强 吴日恒 吕洪波 张珑 康建 张翠娟 李哲林 韦玉程 刘钢 刘全慧 贺玖成 刘浔江 zjzhaokeqin liyou1983

该博文允许注册用户评论 请点击登录 评论 (5 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2019-10-17 21:38

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部