儿童节刚刚过去,本期文章我们谈谈童年回(噩)忆(梦)中的魔方。
也许这是一个略显愚蠢的问题:为什么一个完好的魔方总是可以恢复原样?这其实是一个既简单又深刻的问题。
答:魔方的每个状态都是由初始状态通过一系列有限的操作所得到的,这些操作包括(顺时针旋转上层四分之一周)、(顺时针旋转前层四分之一周)、(顺时针旋转右层四分之一周)……那我们只需要“原路返回”,不就可以回到起点了吗?
例如我们对魔方进行操作:,那么我们只需要再进行如下操作即可:
其中表示的反向操作,即「逆时针」旋转前层四分之一周,其余符号同理。不过按照魔方术语,往往用其小写字母表示,即。
最基本的魔方是27块(实际上是20块+骨架)
在群论中,称为的「逆」,因为他们的复合的结果是「单位元」,即魔方会回到初始状况:
群的复合运算满足「结合律」,容易给出上面等式成立的证明:
一个代数系统如果满足三条性质,则称为群:
存在单位元;
存在逆元;
满足结合律。
可见魔方确实是一个实实在在的「有限群(Finite group)」!
为什么说它有限呢?因为它是「置换群(Permutation group)」 的「子群(Subgroup)」,置换群是有限群,而它的子群是由其元素的子集构成的更小的群,所以其子群也一定是有限群。
魔方由六个中心块、十二个棱块、八个角块组成,所对应的棱块有两个面的不同颜色,角块有3个面的不同颜色,其中棱块只能和棱块换位,角块只能和角块换位,中心块不能移动。国际魔方标准色为:上黄-下白,前蓝-后。
所谓置换群,用魔方来讲就是:魔方的所有状态构成一个有限集合。状态与状态之间的转移,就是群的元素。一个的魔方有6个面,每个面又分为9个小的块面,于是一共有54个小的块面。这些小的块面的颜色共同构成魔方的当前状态,如果这54个块面可以随意互换位置,那么构成的群我们记为。然而魔方由于其特殊的内部构造,使得这种随意性是不可能发生的,真实的情况则是的一个子群,我们称为「魔方群(Rubik' Cube group)」。
这个群的实际状态数已被数学家给出,它是一个巨大的数字:
大约是现在地球人口数目的平方。
答:20步!
这个结果被称之为上帝之数。与平面图的四色定理(给不含有飞地的地图着色,使得邻国颜色不同,只需要四种颜色就够了)的证明类似,同样是通过计算机暴力证明。
总共有26个块 6格中心块不能动 8个角块 12个棱块
这么多,那么少!
这意味着什么呢?说明魔方的各个状态高度关联,所有的状态统统被压缩在直径为20的高维球体内。
我们如何理解魔方的还原公式呢?
我们可以将魔方群以图论的方式表示:每个状态记为一个节点,如果存在一个变换,可以从此状态得到彼状态,那么这两个节点必有一条边相连接,于是我们得到一个关于魔方状态的网络。在这个网络中,寻找最优路线对于新手而言是不切实际的,而还原公式帮助我们进入特定的轨道中,这个轨道就像是时钟表盘,而轨道上各个状态正如表盘上的刻度,而魔方的初始状态就是这个表盘上的12点,只要我们按照顺(逆)时针走,就一定会经过我们的目标。
魔方群中这种类似于表盘结构的子群,我们称之为「循环群(Cyclic group)」,并且是有限循环群。
而魔方还原公式本身的结构也非常耐人寻味,例如
R语言程序
下面是我写的2阶魔方的平面展开图,给定操作自动演算出结果。
魔方核心是一个轴,并由26个小正方体组成.包括中心方块6个,固定不动,只一面有颜色.边角方块8个(3面有色)(角块)可转动.边缘方块12个(2面有色)(棱块)亦可转动.玩具在出售时,小立方体的排列使大立方体的每一面都。
代码说明:
这里我没有遵守通常的记号习惯。
代码中两个变换的乘法表示先执行再执行,这虽然与映射复合的乘法规则相反,但是符合我们从左往右的阅读习惯。
最后一行代码表示对二阶魔方做变换,利用这个代码,可以验证上面的公式。
倒数第三行(括号不算)的代码,我为了做演示视频,有意设置了延迟效果。如果网友想要快速得到结果,可以删掉这行代码。
矩阵中心对称o <- function(A){ t = A[1,1] A[1,1] = A[2,2] A[2,2] = t t = A[1,2] A[1,2] = A[2,1] A[2,1] = t A}矩阵元素顺时针旋转v <- function(A){ t = A[1,1] A[1,1] = A[2,1] A[2,1] = A[2,2] A[2,2] = A[1,2] A[1,2] = t A}A为俯视图,B为正视图,C为右侧视图,X=A,B,C;结果为矩阵形式,方便绘图。Xup <- function(A,a,B,b,C,c){ Aup = matrix(rep(0,48),6) Aup[3:4,5:6] = A Aup[3:4,1:2] = a Aup[1:2,5:6] = B Aup[5:6,5:6] = b Aup[3:4,3:4] = C Aup[3:4,7:8] = c Aup}cube = list(A,a,B,b,C,c)cube[[7]] = Xup(A,a,B,b,C,c)(B --> A)BAup <- function(Bup) { Aup = list() Aup[[1]] = Bup[[1]] Aup[[2]] = o(Bup[[2]]) Aup[[3]] = Bup[[3]] Aup[[4]] = o(Bup[[4]]) Aup[[5]] = r(Bup[[5]]) Aup[[6]] = v(Bup[[6]]) Aup[[7]] = Xup(Aup[[1]],Aup[[2]],Aup[[3]],Aup[[4]],Aup[[5]],Aup[[6]]) Aup}(C --> A)CAup <- function(Cup) { Aup = list() Aup[[1]] = Cup[[1]] Aup[[2]] = Cup[[2]] Aup[[3]] = v(Cup[[3]]) Aup[[4]] = r(Cup[[4]]) Aup[[5]] = Cup[[5]] Aup[[6]] = Cup[[6]] Aup[[7]] = Xup(Aup[[1]],Aup[[2]],Aup[[3]],Aup[[4]],Aup[[5]],Aup[[6]]) Aup}输入矩阵{for(i in 1:6)for(j in 1:8)points(i,j,pch = 15,cex = 4,col = color[Cube[i,j]+1])}draw(Xup(A,a,B,b,C,c)) 对A(红色面)逆时针旋转90度;此时List应该是A面为俯视面的形式U <- function(List){ unfold = Xup(List[[1]],List[[2]],List[[3]],List[[4]],List[[5]],List[[6]]) A = matrix(rep(0,48),6)for(i in 2:5)for(j in 4:7) A[9-j,2+i] = unfold[i,j] U的逆变换,此时List应该是A面为俯视面的形式V <- function(List){ unfold = Xup(List[[1]],List[[2]],List[[3]],List[[4]],List[[5]],List[[6]]) A = matrix(rep(0,48),6)for(i in 2:5)for(j in 4:7) A[j-2,9-i] = unfold[i,j] 对B(橙色面)逆时针旋转90度;此时List应该是B面为俯视面的形式F <- function(List){ unfold = Xup(List[[3]],List[[4]],List[[2]],List[[1]],List[[5]],List[[6]]) A = matrix(rep(0,48),6)for(i in 2:5)for(j in 4:7)A[9-j,2+i] = unfold[i,j] F的逆变换,此时List应该是B面为俯视面的形式E <- function(List){ unfold = Xup(List[[3]],List[[4]],List[[2]],List[[1]],List[[5]],List[[6]]) A = matrix(rep(0,48),6)for(i in 2:5)for(j in 4:7)A[j-2,9-i] = unfold[i,j] 对C(黄色面)逆时针旋转90度;此时List应该是C面为俯视面的形式R <- function(List){ unfold = Xup(List[[5]],List[[6]],List[[3]],List[[4]],List[[2]],List[[1]]) A = matrix(rep(0,48),6)for(i in 2:5)for(j in 4:7)A[9-j,2+i] = unfold[i,j] R的逆变换,此时List应该是C面为俯视面的形式K <- function(List){ unfold = Xup(List[[5]],List[[6]],List[[3]],List[[4]],List[[2]],List[[1]]) A = matrix(rep(0,48),6)for(i in 2:5)for(j in 4:7)A[j-2,9-i] = unfold[i,j] 魔方的变换Transform <- function(Cha) 将字符串的字母逐个拆开for(i in Cha) {if(i=="U"){cube = U(cube)}if(i=="V"){cube = V(cube)}if(i=="F"){cube = F(ABup(cube)); cube = BAup(cube)}if(i=="E"){cube = E(ABup(cube)); cube = BAup(cube)}if(i=="R"){cube = R(ACup(cube)); cube = CAup(cube)}if(i=="K"){cube = K(ACup(cube)); cube = CAup(cube)} draw(cube[[7]]) Sys.sleep(0.2) } cube[[7]]}Transform(rep("RVE",30))
- END -
数学英才
中学生英才计划
数学学科官方公众号
推送数学微慕课和学习资料