知乎[1]上看到有人问:如下的滚珠游戏,左右各14颗珠子,中间4颗,如果每个珠子都有编号,对任意的初始状态,是否都能把珠子移动到指定位置?
此题看上去很烦,但使用群论处理后出奇得简单,结论是可以做到。
限于篇幅,我假设读者有一些群论的基础知识,尤其是置换群。
首先把游戏换成下图,每个数字表示珠子可以处于的位置:
(我无法调整图片布局,姑且接受这种上下布局状态)
如果定义一次“置换”就是任意的把若干位置上的珠子换到另一些位置上,那么所有这些操作构成了一个对称群,以下记作 ,该群的阶是32!。
但游戏中的操作受限,目测有4个“原子”置换:
上环顺时针转动1格。
上环逆时针转动1格。
下环顺时针转动1格。
下环逆时针转动1格。
但以上的顺指针置换连续执行17次后,效果就等同于一次逆时针置换,所以本质上是2个“原子”置换,这里我选取1和4号置换。
所以问题就变成,利用以上2个原子置换,能否组合出所有的置换?如果可以,则游戏可以达到任何指定的状态,否则不行。
1号置换用循环记号写出就是:
其含义是:15号位换到16号位;16号位换到17号位;17号位换到18号位,...32号位换到15号位。
4号置换用循环记号写出就是:
其含义是:1号位换到2号位;2号位换到3号位;3号位换到4号位,...18号位换到1号位。
现在问题就变为,在对称群 中,使用以上上两个置换为生成元,所生成的子群会是什么样的群?阶数为多少?
借助SAGEMath,可以方便地计算:
sage: S32=SymmetricGroup(32)
sage: UP=S32("(15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32)")
sage: DOWN=S32("(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18)")
sage: HR=S32.subgroup([UP,DOWN])
sage: HR.order()==factorial(32)
True
sage: HR.order()==S32.order()
True
sage: HR==S32
True
以上代码表明,所生成的子群的阶等于 的阶,它本身就是 ,问题解决!
留下一个思考题:
如果两个环之间“共享”的位置不是4个,而是3个或5个或更多,结果会怎样?
一个更有意思的问题是:
对这个游戏,有没有类似于魔方中的速记“公式”,使得我们可以快速完成游戏?
这问题并不简单,利用群论,也确实能帮我们找出一些快捷公式。
谁说抽象代数只是抽象,它也很实用!
知乎: https://www.zhihu.com/question/665554308