对平面魔方群及其Cayley图直径的研究

浙江省新昌中学作者:贾子涵张启煊项羽铭指导老师:吴裕东对平面魔方群及其Cayley图直径的研究中国·浙江1对平面魔方群及其Cayley图直径的研究摘要借鉴魔方的游戏规则,本文设计了一款游戏“平面魔方”,并运用群论、计算机等工具对其性质进行了深入的挖掘.首先,本文对平面魔方的规则进行了详细介绍,其次,运用群论的知识,本文研究了平面魔方的各个性质,如平面魔方置换群的阶、Cayley图直径等,最后将模型推广到异形并得出了一般性的结论.关键字:平面魔方置换群Cayley图直径2AbstractAccordingtotherulesofmagiccube,theauthorshavedesignedatwo-dimensionmagiccubeinthispaper.Andtherulesofthecubeareexplainedintegrallty.Also,bymakinguseofgrouptheoryandthecomputer,theauthorsstudythepropertiesofthecube,suchastheorderofthepermutationgroupofthecube,thediameterofCayleyGraph,etc.Theauthorsalsoextendthemodeltoirregularsituationsandthecommonresultsofthecubeareobtainedinthispaper.Keywords:two-dimensionmagiccube;permutationgroup;thediameterofCayleyGraph3目录摘要Abstract1.基本介绍.......................................................................................................................................11.1引言.....................................................................................................................................11.2平面魔方规则介绍.............................................................................................................11.3问题的提出.........................................................................................................................22.模型建立.......................................................................................................................................32.1群论基本介绍.....................................................................................................................32.2平面魔方群.........................................................................................................................4三、的阶......................................................................................................................................5四、Cayley图直径..........................................................................................................................64.1Cayley图的相关定义.......................................................................................................64.2n阶平面魔方群Cayley图直径机解算法.........................................................................74.3n阶平面魔方群Cayley图直径下界估计.......................................................................10五、模型推广................................................................................................................................135.1基本介绍...........................................................................................................................135.2的阶..........................................................................................................................135.3的Cayley图直径....................................................................................................145.4的Cayley图直径下界估计...................................................................................14六、未解决的问题........................................................................................................................15七、参考文献................................................................................................................................15八、附录........................................................................................................................................158.1平面魔方群Cayley图直径计算源码..............................................................................158.2n阶平面魔方群Cayley图直径下界计算源码...............................................................1711.基本介绍1.1引言魔方是当今流行的一款益智玩具.自其于1974年被匈牙利建筑学家Rublik发明以来,受到了世界各地人民的喜爱.最初的魔方是三阶魔方（图1）,随后便衍生出了各种各样的魔方（图2）,但魔方的改变都主要是在阶数、结构的改变上.曾有魔方爱好者将魔方推广到四维并制作出了可视化的计算机游戏,但最终由于操作过于繁琐、模型不够直观且无法在现实中实现等原因,未能流行开来.我们由此想到,既然可以将魔方推广到四维空间之中,那么是否也可以将其“压缩”到二维平面之中呢?受此启发,我们以魔方的规则为模板,设计出了一款新游戏——“平面魔方”,这将成为本文后几章中研究的重点.（注:平面魔方并非三维魔方在平面上的投影,它是一个由魔方启发而来,和魔方具有相似规则的游戏.）图1图21.2平面魔方规则介绍在本节中,我们将对平面魔方游戏规则进行介绍.1.2.1平面魔方结构n阶平面魔方由n2个大小相等的正方形魔方块组成,每个魔方块上标有各不相同的数字0,1,2,…,n2-1,且各个魔方块均可安置在任意的位置,组成一个的正方形（如图3）.图3二阶平面魔方三阶平面魔方n阶平面魔方21.2.2操作规则定义1.1移动指将n阶平面魔方中任意一列/行中的所有数字上移/左移1格,超出方阵范围的魔方块平移至该列/行的末尾.操作指将n阶平面魔方中任意一列/行进行任意(不为n的倍数)次移动.如图4就是三阶平面魔方中的一种操作.图4我们可以发现,对平面魔方无论如何进行操作,所得到的结果仍然是一个的方阵,且仍由数字0,1,2,…n2-1不重复填充.1.2.3初始状态、还原与还原步数下面我们给出初始状态、还原与还原步数的定义:定义1.2一个平面魔方处于初始状态,当且仅当平面魔方每个魔方块上的数字从左到右,从上到下递增.定义1.3若一个未处于初始状态的平面魔方经过若干次操作以后变换为了一个处于初始状态的平面魔方,则称这个平面魔方被还原了,且操作次数称为还原步数.1.3问题的提出关于三阶魔方,人们提出并解决了许多有趣的数学问题,比如:问题1三阶魔方共有多少种可能的组合?解答1三阶魔方有43,252,003,274,489,856,000种不同的可能组合状态.问题2至少需要几次操作,就一定能够还原任意一个三阶魔方?解答2任意组合的魔方均可以在20步之内还原.问题2的解被称为魔方的上帝之数(God’snumber),即三阶魔方Cayley图的直径.这一问题困扰了数学家长达三十多年,直到2010年7月,美国加利福尼亚州科学家征用到了更加强大的资源——谷歌旧金山总部的超级主脑计算机.随着程序的精简和设备的提升,这量配置惊人的计算机破解了这一谜团.研究人员利用计算机,用枚举法验证了每一种情况,证明任意组合的魔方均可以在20步之内还原,“上帝之数”正式定为20.需要指出的是,群论将是解决魔方这一类变换问题的有力数学工具,其介绍及一些基本内容将在第二章(2.1)中给出.操作前操作后3同样的,关于平面魔方,我们提出以下问题:问题3三阶平面魔方共有多少种可能的组合?问题4n阶平面魔方共有多少种可能的组合?问题5至少需要几次操作,就一定能还原任意一个三阶平面魔方?问题6至少需要几次操作,就一定能还原任意一个n阶平面魔方?关于问题3、4、5我们将在后面文章给出解答.限于能力,我们无法解出问题6的准确解,但我们通过估计的方法给出了下界.2.模型建立2.1群论基本介绍定义2.1.1设是一个非空集合,在中定义了一种封闭的代数运算,记作,即对于中任意两个元素,都存在使得.如果对这种运算还满足下面几个条件:(1)对,有.(2)对(3)对那么就称为一个群.元素称为的单位元素,称为的逆元素.定义2.1.2如果群包含的元素个数有限,则