华容道怎么玩(数字华容道的奥秘详解)

seoxin 05-04 17:24 44次浏览

我的抽象代数系列课程先从一个智力游戏说起,可能有的人玩过这个游戏,这是节数学科普课,默认读者没有学过群论,这个游戏中包含的置换的思想也就是群论的雏形,人们在研究了置换之后于是发明了群这个结构。这个游戏就是数字华容道,有一个正方形的外框,里面有十五个小正方形滑块,下图中#井号表示的是空。由于有了这个空,滑块就可以滑动,游戏的目标是让打乱的数字通过滑块移动最终按顺序排列起来。很多人小时候玩过滑块拼图游戏,原理跟这个是一样的,有人通过摸索会掌握这个游戏的窍门,现在我从数学上来探究这个数字华容道,当你掌握了数学原理,你甚至可以自己创造让某个滑块从A点移动到B点而其他保持不变的公式。

数字华容道的奥秘

可以看到,如果按图表所示,让3和1交换,15和2交换…,这样能够复原数字华容道,可是按照规则,滑块只能滑动,把这个规则抽象出来就是,只能#和相邻的数字交换,每一个步骤必定是有#参与。其实图表所示的就是一个置换。我们中学就学过函数,置换可以看作特殊的函数,定义域的元素和值域元素相同,而且都是有限的。

数字华容道的奥秘

3和1交换用置换的写法就是(1 3),只有两个元素位置改变称作对换。玩游戏的时候每一步相当于井号和相邻的数字交换,如(# a1),(# a2),完成两步相当于两个对换相乘,置换乘法的定义本质是函数的复合

例如第一步(# a1),第二步(# a2),两步之后的结果,就是(# a2)(# a1),假如将(# a1)看作f(x),(# a2)看作g(x),(# a2)(# a1)的意思就是g[f(x)],也就是函数的合成。考虑(# a2)(# a1)中元素的变化,#在第一步变成a1,在第二步没有变;a1在第一步中变成#,第二步中由#变成a2;a2在第一步中没变,在第二步中变成#。所以

(# a2)(# a1)=(# a1 a2),这是一个三阶循环置换。所以上面的置换不能写成(3 1)(15 2)(4 3)(12 4)(10 5)(11 6)(1 7)(2 8)(8 9)(5 10)(13 11)(9 12)(6 13)(7 14)(14 15),那上表的置换应该怎么表示呢?

置换的完全分解是指将置换分解为不相交的循环置换,并且含有每个1-循环置换。这个置换完全分解就是(1 7 14 15 2 9 12 4 3)(5 10)(6 13 11)(8)(#)

要赢得这个游戏,就是要找到(# a(n))(# a(n-1))…(# a2)(# a1)这样的序列,使得(# a(n))(# a(n-1))…(# a2)(# a1)=(1 7 14 15 2 9 12 4 3)(5 10)(6 13 11)(8)(#)

在置换理论里有个定理,是说若一个置换能够表示成偶数个对换的乘积,那么它只能被表示成偶数个对换的乘积;若一个置换能够表示成奇数个对换的乘积,那么它只能被表示成奇数个对换的乘积。这个定理的证明此文就不涉及了,因为需要很多定义和定理的铺垫。后面讲抽象代数课程时会循序渐进地把重要的定理依次证明。这个游戏的起始状态和复原的状态相比#位置没有发生变化,游戏的每一步#都在和相邻数字交换,可以肯定的是只有经过偶数步#才能位置不变,假如向上有N步,一定向下也会有N,才能保证#位置不变,向下向左向右同理。(1 7 14 15 2 9 12 4 3)(5 10)(6 13 11)(8)(#)这个置换,符号=(-1)^(16-5)=-1是一个奇置换,所以这个图示的这种初始状态,要复原是不可能,别再傻傻的移动滑块了,纵使尝试亿万次还是不可能成功。这就是数学的力量,它能让你真正地玩透这个游戏。

  • 暂无推荐