百科问答小站 logo
百科问答小站 font logo



如何从数学角度证明魔方复原存在必可解策略? 第1页

  

user avatar   liu-yang-zhou-23 网友的相关建议: 
      

目录

  • 符号
  • 变换群
  • 分析
  • 2 阶魔方公式列举
  • R语言程序
  • 效果展示

为了简便,以 2 阶魔方为例。

符号

我们将正方体的六个面展开如下:

其中俯视图、正视图、右侧视图分别为 我们称之为主面,它们的对面分别是 ,称之为次面。每个面都分成四个小方块:

例如,当 时,则此面为

变换群

当我们将 面逆时针旋转 ,我们只需要观察上层魔方的变化:

同理,关于侧视图、正视图也有类似的旋转。如果在复平面中,这种旋转的变换表示十分简洁:

所以不妨以 分别表示 的逆时针旋转(同时也可以看做是这三个面的外法向量)。另外,我们不需要考虑次面的旋转:若我们对 面进行旋转 ,再对 进行旋转 ( 的外法向量),则魔方恢复原状,从代数上也是很符合的:

表示恒等变换。所以旋转 的逆向操作即逆元,有两种等价的操作:或者将 顺时针旋转,或者将 进行逆时针旋转,我们都将此记成 。关于侧视图、正视图的旋转同理。

于是,我们考虑一个变换群:

这个群的乘法是变换的复合, 为生成元,词群()的关系() 比较复杂,比较显然的有: 将一个面朝同一方向旋转 4 次就会恢复原状。这个群我们称之为 阶魔方群。

至于逆元,由前文易得知。这个群显然是有限的,从置换群的角度看,魔方的状态是有限的,于是它是某置换群的子群

分析

回到题主的问题,魔方复原总是可解吗?已知当前魔方的状态,我们只要构造出它的逆元即可。求一个元素的逆元在群论中是非常容易的事情,例如 的逆元就是 。至于用某些公式(即特殊的关系),总可以使得魔方的状态进入一个轨道,这个轨道经过初始状态,于是只要按照公式机械重复操作,则其结果始终在此轨道上,并且最终到达目的地。理论上,我们可以把这个有限群以图论的方式表示:每个状态记为一个节点,如果存在一个变换,可以从此状态得到彼状态,那么这两个节点必有一条边相连接。于是,我们可以求任意节点到初始状态所代表节点的(最短)路径,这是图论中最基本的问题。


2 阶魔方公式列举

我再补充一下魔方群的关系:我们观察部分词()的阶,这些词我们按照代数式的次数进行分类。

声明:

  1. 下面的映射的复合结果都是 ,往后不在特别声明;
  2. 群论一般的记法 表示先执行映射 ,再执行映射 ;
  3. 如果在个别式子满足乘法交换性,则我只列出其中一个。
  4. 构成右手系,由魔方的对称性可知,关于这三者的轮换式只需列出其中之一即可。

  • 次(注意到 )


于是我们任意给定一个 幂次乘积的有限序列,通过上面公式的可以化简为更简洁的序列。


R语言程序

       ####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 } #矩阵元素逆时针旋转 r <- function(A) {     t = A[1,1]     A[1,1] = A[1,2]     A[1,2] = A[2,2]     A[2,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 = matrix(rep(1,4),2) B = matrix(rep(2,4),2) C = matrix(rep(3,4),2) a = matrix(rep(4,4),2) b = matrix(rep(5,4),2) c = matrix(rep(6,4),2)  #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 --> B),输入输出皆为列表   ABup <- function(Aup)     {     Bup = list()     Bup[[1]] = Aup[[1]]     Bup[[2]] = o(Aup[[2]])     Bup[[3]] = Aup[[3]]     Bup[[4]] = o(Aup[[4]])     Bup[[5]] = v(Aup[[5]])     Bup[[6]] = r(Aup[[6]])     Bup[[7]] = Xup(Bup[[3]],Bup[[4]],Bup[[2]],                    Bup[[1]],Bup[[5]],Bup[[6]])     Bup }  #(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 --> C ACup <- function(Aup)     {     Cup = list()     Cup[[1]] = Aup[[1]]     Cup[[2]] = Aup[[2]]     Cup[[3]] = r(Aup[[3]])     Cup[[4]] = v(Aup[[4]])     Cup[[5]] = Aup[[5]]     Cup[[6]] = Aup[[6]]     Cup[[7]] = Xup(Cup[[5]],Cup[[6]],Cup[[3]],                    Cup[[4]],Cup[[2]],Cup[[1]])     Cup }  #(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 }    #画出魔方展开图 color = c("white","red","orange","yellow","green","blue","purple") par(mai=rep(0,4),oma=rep(0,4)) plot(0,0, type = "n", xlim = c(0,7), ylim = c(0,9)) draw <- function(Cube)    #输入矩阵 {     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]    #坐标旋转由复数推导     unfold[2:5,4:7] = A[2:5,4:7]     A = unfold[3:4,5:6]     a = unfold[3:4,1:2]     B = unfold[1:2,5:6]     b = unfold[5:6,5:6]     C = unfold[3:4,3:4]     c = unfold[3:4,7:8]     List = list(A,a,B,b,C,c,unfold)     List    }  #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]    #坐标旋转由复数推导     unfold[2:5,4:7] = A[2:5,4:7]     A = unfold[3:4,5:6]     a = unfold[3:4,1:2]     B = unfold[1:2,5:6]     b = unfold[5:6,5:6]     C = unfold[3:4,3:4]     c = unfold[3:4,7:8]     List = list(A,a,B,b,C,c,unfold)     List    }  #对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]    #坐标旋转由复数推导     unfold[2:5,4:7] = A[2:5,4:7]     B = unfold[3:4,5:6]     b = unfold[3:4,1:2]     a = unfold[1:2,5:6]     A = unfold[5:6,5:6]     C = unfold[3:4,3:4]     c = unfold[3:4,7:8]     List = list(A,a,B,b,C,c,unfold)     List    }  #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]    #坐标旋转由复数推导     unfold[2:5,4:7] = A[2:5,4:7]     B = unfold[3:4,5:6]     b = unfold[3:4,1:2]     a = unfold[1:2,5:6]     A = unfold[5:6,5:6]     C = unfold[3:4,3:4]     c = unfold[3:4,7:8]     List = list(A,a,B,b,C,c,unfold)     List    }  #对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]    #坐标旋转由复数推导     unfold[2:5,4:7] = A[2:5,4:7]     C = unfold[3:4,5:6]     c = unfold[3:4,1:2]     B = unfold[1:2,5:6]     b = unfold[5:6,5:6]     A = unfold[3:4,7:8]     a = unfold[3:4,3:4]     List = list(A,a,B,b,C,c,unfold)     List    } #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]    #坐标旋转由复数推导     unfold[2:5,4:7] = A[2:5,4:7]     C = unfold[3:4,5:6]     c = unfold[3:4,1:2]     B = unfold[1:2,5:6]     b = unfold[5:6,5:6]     a = unfold[3:4,3:4]     A = unfold[3:4,7:8]     List = list(A,a,B,b,C,c,unfold)     List    }   #魔方的变换 Transform <- function(Cha)  #输入由U/V/F/E/R/K构成的字符串 {     Cha = unlist(strsplit(Cha,split=""))    #将字符串的字母逐个拆开     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))     

代码说明:

  • 代码中两个变换的乘法 表示先执行 再执行 ,这与映射复合的乘法规则相反。其实修改代码也不是难事,但是我太懒了。
  • 表示对二阶魔方做变换 ,利用这个代码,可以验证上面的公式。
  • 倒数第三行(括号不算)的代码 ,我为了做演示视频,有意设置了延迟效果。如果网友想要快速得到结果,可以删掉这行代码。
  • 最近知乎没办法插入图片,所以没有办法展示效果,大家自行在电脑上演示吧。




  

相关话题

  七个小朋友,只能切四刀,怎么把三个苹果均分? 
  数学专业出身的口算能力会比其他人强很多吗? 
  S={a+b√3i | a∈Q, b∈Q} 是数域吗? 
  如何用初等方法证明k阶齐次线性常系数递推数列的通项公式? 
  一天做完一百道积分题是一种什么感觉? 
  学文科会影响数学思维吗? 
  数学能取代人类语言吗? 
  这个不等式题目怎么做? 
  数学各领域的巨著或者非常深入的教材是什么? 
  两个星期自学完高中数学实际吗? 

前一个讨论
晾一件刚洗的衣服,有可能计算出每滴水落地的时间间隔吗?
下一个讨论
除了 3,4,5 以外是否还有别的三角形,它的三条边是连续自然数,它的面积也是自然数?





© 2024-11-08 - tinynew.org. All Rights Reserved.
© 2024-11-08 - tinynew.org. 保留所有权利