三阶魔方状态的对称性分类计数(一):三阶魔方的总状态数

这一系列文章中我们将探讨如何将三阶魔方的状态按照空间对称性分类并计算每一类状态的数量。

此篇要介绍的是三阶魔方总状态数的计算。这个问题在魔方相关的数学问题中可以算是比较基础的一个,也在很多现有资料中都能找到讲解,不过为了完整性,在这里还是从头说一遍。

首先明确一些本系列文章中用到的概念和约定:

每一个可以独立运动且对魔方的外观有影响的部分称为组块。每个组块的每个外表面称为面片。有一个、两个及三个面片的组块分别称为中心块棱块角块。每个组块以其所包含面片的按顺时针顺序的颜色序列命名。如,某个角块从外侧看按顺时针次序三个面片为白色、蓝色和红色,则称其为“白蓝红”角块。依序列的起始点不同,同一个组块可以有多个名称,如蓝红白角块与白蓝红角块为同一个组块。但在表示组块的状态的时候不同的名称有区别,后述。我们使用三阶魔方标准颜色方案,即有一个白蓝红角块,白色的对面为黄色,蓝色的对面为绿色,红色的对面为橙色。为简便,可以英文首字母将颜色记为白=W,黄=Y,蓝=B,绿=G,红=R,橙=O。

我们的讨论仅限于魔方贴纸本身无图案的情况,因为否则的话还需要考虑贴纸图案的对称性,过于复杂。在此约定下,中心块的不同方向视为等价。

图 1:坐标系、面的名称和标准状态

将魔方置于空间直角坐标系中,中心位于原点,所有棱与坐标轴平行。魔方的面以其外侧法向量的方向命名。约定x轴正、负方向为前、后,y轴正、负方向为右、左,z轴正、负方向为上、下。为简便,可以英文首字母将面记为前=F,后=B,右=R,左=L,上=U,下=D(图 1)。组块的状态为其面片所在的面的序列。如,白蓝红(WBR)角块,其白色面片位于前面、蓝色面片位于左面、红色面片位于上面,称其所在状态为“前左上(FLU)”(图 2a)。我们将“a 组块位于 b 状态”记作“a @ b”。状态名的面序列应与组块名的面片序列对应,故如果将此组块称为“蓝红白(BRW)”,则此状态应称为“左上前(LUF)”,即“WBR @ FLU”与“BRW @ LUF”含义相同,但与“WBR @ LUF”(图 2b)不同。组块的位置为其面片所在的面的集合,即不计顺序(方向)。我们将“a 组块位于 b 位置”记作“a ~ b”。同一个位置也可以有多个名称。如“WBR ~ FLU”与“WBR ~ LUF”含义相同。

图 2a:WBR @ FLU
图 2b:WBR @ LUF

某一组块集合的状态(位置)为其包含的组块到组块状态(位置)集合的映射。魔方的状态为其所有组块构成的集合的状态。每个面的所有面片颜色相同的状态称为复原状态。由于仅有整体方向不同的状态一般视为等价,且所有中心块的相对位置完全确定,一般可将中心块固定在某个状态而仅考虑其他组块的状态。若某状态中白、黄、红、橙、蓝、绿中心块分别位于上、下、前、后、右、左面,称此状态处于标准方向。标准方向下的复原状态称为标准状态,此时每个组块的状态(位置)也称为其标准状态(位置)。从复原状态通过任意旋转魔方的面可以到达的状态称为合法状态,否则为非法状态

魔方的操作以被旋转的面的名称表示,无附加标记的为顺时针旋转 90°,逆时针旋转 90° 上标加撇号,旋转 180° 后加“2”。如,右面顺时针旋转 90° 记作 R,逆时针旋转 90° 记作 R’,旋转 180° 记作 R2。

我们的目标是计算标准方向下的合法状态的数量。若无说明,以下的讨论仅考虑标准方向。

标准方向下的总状态数很容易计算:角块和棱块可以各自任意互换位置,且可以在同一位置上任意旋转。因此,所有角块的位置总数为 8!,同一位置的状态总数为 38,所有棱块的位置总数为 12!,同一位置的状态总数为 212,魔方的总状态数为 8! × 38 × 12! × 212

为了计算合法状态的数量,先考虑某个状态合法的必要条件。状态合法性的必要条件有三个:

1. 位置置换的奇偶性。考虑所有组块的位置相对于其标准位置的置换。魔方单个面的 90° 旋转会对角块的位置和棱块的位置分别做 4-轮换,相当于共计 6 个组块对换,为偶置换。因此,魔方的任何操作不改变组块置换的奇偶性。标准状态下的组块置换为恒等置换,是偶置换,因此任何合法状态下,组块位置的置换一定为偶置换。

2. 角块方向。一个角块位于其标准位置时,其方向的定义是显然的,即以其与魔方中心的连线为旋转轴的相对于其标准状态的旋转角。而当一个角块位于其他位置时,需要对其方向做适当的定义。一般来说,可以按以下方法定义角块的旋转数:先对每个角块指定一个面片为基准面片。基准面片可以任意指定,但适当地选取基准面片可以简化分析。我们选取每个角块上的白色或黄色面片为基准面片(图 3)。在某个状态下,某个角块的旋转数由它的基准面片所在的面和标准状态下此位置上的角块的基准面片所在的面的关系决定。若当前基准面片与标准位置下的基准面片重合,则旋转数为 0;若当前基准面片相对于标准位置下的基准面片顺时针旋转了 120°,则旋转数为 1;若当前基准面片相对于标准位置下的基准面片逆时针旋转了 120°,则旋转数为 -1(图 4)。

图 3:有标记的面片为角块的基准面片
图 4:角块旋转数举例。WGO @ URF,旋转数为 0;YGR @ FLU,旋转数为 1;YBO @ RUB,旋转数为 -1。

容易看出旋转上面或下面不会改变某个角块的白/黄面片与上/下面的位置关系,因此也不会改变旋转数。而其他四个面的旋转操作效果对称,只考虑其中一个。又由于同一个面的顺时针和逆时针旋转互为逆操作,只需要考虑其中一个。考虑 R 操作。可以验证:位于 URF 或 DRB 位置的角块,R 操作后其旋转数增加 1 (模 3),而位于 UBR 或 DFR 位置的角块,R 操作后其旋转数减少 1 (模 3)(图 5),旋转数的总增量模 3 余 0。因此,魔方的任何操作不改变角块旋转数总和模 3 的余数。标准状态下每个角块的旋转数均为 0,总和模 3 余 0,因此任何合法状态下,角块旋转数总和模 3 余 0。

图5:R 操作对角块旋转数的影响

3. 棱块方向。与角块旋转数类似,定义棱块翻转数:对每个棱块,按图 6 指定基准面片。对于每个棱块,若当前基准面片与标准位置下的基准面片重合,则翻转数为 0,否则为 1。

图6:有标记的面片为棱块的基准面片

容易看出,任何一个 90° 旋转都会改变全部 4 个被移动的棱块的翻转数。因此,魔方的任何操作不改变棱块翻转数总和的奇偶性。标准状态下每个棱块的翻转数均为 0,总和为偶数,因此任何合法状态下,棱块翻转数总和为偶数。

满足以上三个条件的状态一定是合法状态,这可以构造性证明:只需任选一种复原方法,证明满足以上三个条件的状态都可以复原即可。特别地,可以取 CFOP 法,先验证从任何状态开始一定可以复原前两层,然后验证 OLL 公式集包含了最后一层满足旋转数和翻转数条件的所有方向组合、PLL 公式集包含了最后一层满足置换奇偶性条件的所有位置组合,此处略。

通过对换两个固定位置的组块(如对换 UR 位置和 UF 位置的棱块并保持其翻转数),可以将组块置换为偶置换的状态与组块置换为奇置换的状态一一对应,因此两类状态数量相等。类似地,通过旋转某个固定位置的角块和翻转某个固定位置的棱块,可以证明角块总旋转数模 3 余 0、1 和 -1 的状态数量相等,棱块总翻转数为奇数和偶数的状态数量相等。又,上述三个操作各自只影响三个条件对应的不变量中的一个,因此三个条件互相独立。等概率随机任取一个状态,其满足每个条件的概率分别为 1/2,1/3 和 1/2 且三者独立,因此其为合法状态的概率为 1/2 × 1/3 × 1/2 = 1/12。由此可得三阶魔方合法状态总数为

2 thoughts on “三阶魔方状态的对称性分类计数(一):三阶魔方的总状态数”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: