解谜的艺术(1) 撬锁

deducemath · 发表于 2010-5-29 08:26

本帖最后由 deducemath 于 2012-2-24 17:34 编辑

声明：本文涉及高等数学，存在没有明确定义的概念，某些描述比较笼统。原因有二：其一，阐述清楚繁琐而费时；其二，此文属自娱型。想弄明白的读者请查阅相关文献。

      我之所以这么喜欢开锁，可能主要是因为我喜欢解各种各样的谜题。每个锁就好像一道谜题。……猫咪，你有时也像谜一样，但我最后还是会解开你的。”
                                                                                 ——Richard P. Feynman[1]
      我迷恋上了钥匙，并开始制造它们。先是把自己家的各种锁一一打开，偷看大人的秘密，后来就发展到未经邀请的去开别人家锁着的门。每当锁舌铛的一声跳开，我便陷入无限的欣喜之中。
                                                                                 ——马小军（《阳光灿烂的日子》主角）

   人们天生对隐秘的事物感兴趣。一些人喜欢撬锁因为开锁之后可以做所谓有趣的事儿。例如，在电影《阳光灿烂的日子》里，正太马小军爱偷看大人秘密；诺兰的处女作《追随》中克布“喜欢”由房间里的私人物品揣测屋主的特点，拿走或搞乱一些东西以“干扰某人的正常生活轨迹，让他们重新审视原本已熟视无睹的一切。” 我本人则比较享受撬锁的过程。上海美术电影制片厂的动画片我小时候看过不少，系列动画《邋遢大王奇遇记》有个片段记忆犹新，可以说，这是关于解锁谜题的最初记忆。

《邋遢大王》第9集秘密地图之“箱锁”

本文之锁非现实之锁，究其原因，或许自己不具备费曼撬锁的天赋，而撇了一眼还算饱满的钱包后我忽然意识到，这可能不是真实原因。对锁匠来说，撬锁不仅是个细致的技术活，还比较费体力。一般而言，我欣赏纯文纯理的东西。我始终期盼一本以撬锁为核心谜题的推理小说横空出世，它具备爱伦坡的趣味性及种种锁具的手绘插图。虽然国内小说《锁侠》、《天锁》以撬锁为主题，可惜语言乏味，内容玄幻离奇，没有丝毫推理解谜的乐趣可言，而日本推理作家法月伦太郎的《失窃的信》则过于简短不成系统。——还好，AVG不乏撬锁谜题。

讲AVG谜题设计的文章[2]把撬锁谜题归于GUI /Board Puzzles。而在Mechanical Puzzles中它们则属于Sequential Movement Puzzles。这些小谜题一般比较容易，凭直觉就可以破解，有时需要纸笔作点记录画些草图，也费不了多少时间。从审美学的角度看，上等好锁的材质、形式和意蕴都要趋于完美。而如果一把锁的数学结构优雅而精致，那么它在意蕴上就已经满足成为上等锁具的条件。注意，我论述的是撬锁的艺术，不要只迷恋GUI的华丽，或者满足于开锁后幼稚的成就感。以博学著称的宝姐姐曾教导我们，“小事上用学问一提，那小事越发作高一层了。不拿学问提着，便都流入世俗去了[3]”。所以我得用点学问提一下，这点学问具体指的是初等群论和图论。群论是数学中描述对称的语言，19世纪初法国数学家Galois(1811-1832)用它完全解决了5次以上代数方程的根式求解问题，20岁时他为一个女人死于决斗。图论起源于Euler(1707-1783)关于哥尼斯堡七桥问题(推广问题俗称一笔画)的一篇论文。下面我通过分析几个经典锁具来展示撬锁之艺术。先摆上第一把锁：

破箱人_拼图铁箱

tabris在“AVG谜题探索(01)”[4]中分析过此锁，但文中定理一有错，其实那8个方块的所有排列均可获得。下面给出Jaap的定理，很多旋转类谜题可以由此定理得到其排列的群结构。
图上的旋转谜题定理[5]：设图G顶点数为n，每个顶点上放置一个转块，且每一个转块经过某些旋转操作之后都可以到达G的任意一个顶点。若G上存在两个旋转圈使得两圈的公共部分恰为一条路，则除两个特例之外，有3种情形：
1、若G是圈，群为Zn。
2、若G上无偶旋转圈，群为An。
3、否则群为Sn。
其中Zn为n阶循环群，An为n阶交错群，Sn为n阶对称群。两特例如下图所示，它们对应的旋转圈分别为{(1,2,3,4),(2,6,5,4,3)}，{(6,1,4,5),(1,2,3,4)}，群都与S5同构。

据Jaap定理，拼图铁箱的群为S25，所有排列均可得到。存在一些旋转谜题不满足定理条件，举一个简单的例子：Hungarian Rings。如下图：

所以此定理有待推广。规模较小的旋转谜题用计算代数软件GAP[6]求解只需短短几行代码，使用起来非常方便。可以在[7]下载适用于XP和Vista系统的GAP软件。如果谜题旋转圈较多，输出答案可能很长，操作不方便。最好先凭直觉排好一部分，剩下的子迷题再用软件求解(一般当群为Sn时容易使用此法)。例如，若拼图铁箱与本文截图一致，限制在右下方8个小方格中的子迷题可以用如下三行代码：
G:=Group((1,2,4,3),(3,4,6,5),(5,6,8,7));
W:=EpimorphismFromFreeGroup(G:names:=["a","b","c"]);
P:=PreImagesRepresentative(W,(3,4,8,7));
输出结果： c*b*c*b*c*b*a*b^-1*a*c^-1*b^-1*a*b。
现在摆出第二把锁：

静物_九宫锁

   “当我想以一个词来表达音乐时，我找到了维也纳；而当我想以一个词来表达神秘时，我只想到了布拉格(尼采，1844-1900)。”此时此刻，你处于这座神秘之城的地下世界，被潮湿和黑暗裹挟，在迷宫般的下水道中摸索前行。最终一扇铁门挡住去路，门上呈现的就是这么个装置，颓败，锈迹斑斑，结构精巧。放上好不容易收集到的六个小巧的银戒指，装置开启。金属细细的摩擦声与阴郁诡异的背景音乐交织在一起……

   把钥匙调整到最顶层最少步数可能为21，你可以编程验证，但这不是我关心的问题。我的问题是，如果让九个滑块位居中央，所有的排列方式都能得到吗？否。九个滑块的变换群为A9，只能得到一半排列。证明思路如下：

   先证群中不含奇置换：将处于中央位置的9个滑块的置换群看作是它们与12个空滑块的置换群的子群，群中任一置换为一系列基本置换（每个拉杆的拉动操作对应一个基本置换）的乘积，乘积中每个基本置换与其逆元出现次数相同（保证九宫格复位），故为偶置换。为证群是A9，使用某些基本置换的乘积得到一些旋转圈对应的置换。例如用四个基本置换相乘得到右下角三个滑块的顺（逆）时针旋转（其余滑块位置保持不变）。构造的旋转圈的并含有九宫格对应图的九个顶点，由Jaap定理即可得证。

   最初我以为九宫锁为本游戏原创，后来在网上下到Hordern的《Sliding Piece Puzzles》的电子版，插图11中有类似谜题。如下图：左下角谜题为九宫锁的4*4形式。

第三把锁——静物_吊车锁

《Sliding Piece Puzzles》插图3中画着蓝精灵的滑块玩具与吊车锁结构一样。蓝精灵是80后最钟爱的卡通人物之一，一提蓝精灵，那纯净轻快的主题歌似乎又萦绕耳边：“在那山的那边海的那边有一群蓝精灵他们活泼又聪明他们调皮又灵敏……”。可惜这两个家伙的名字我记不起来了。再看插图3，右上角是停车库版的吊车锁，可能某个有眼光的制造商看了《亨利·杜德尼的数学趣题》之停车库趣题后将其做成了玩具。

吊车锁与15-Puzzle等经典的滑块类谜题可以推广到一般形式。Richard M. Wilson[8] 74年证明了无割点图上仅空一格的滑块谜题的置换群定理，但吊车锁是树上空4格的谜题，定理不适用。84年有三个人给出下面的推广定理，应用于吊车锁，群为S6。
图上的滑动谜题定理[9]：设图G顶点数为n。在其中k个顶点上放置滑块，每个顶点放一个，k<n，且每一个滑块都可以到达G的任意一个顶点。则除一个特例外，有3种情形：
1、若G是圈，群为Zk。
2、若G是二部图，且k=n-1，群为Ak。
3、否则，群为Sk。
特例[12]如下图所示，群与S5同构。

如果图上存在滑块不能到达所有顶点，则谜题能分解成一些子迷题，举例如下图所示，原谜题置换群为子迷题置换群的直积。

第四把锁——静物_祖父箱子的密码锁

从符号学的角度看，祖父的箱子放在阁楼里有象征意义：“阁楼(储藏室)代表尘封的回忆或被人忽略的真相，等待有心人去发掘。[10]”此谜题很多人分析过，甚至有用枚举法编程求解的，然而此谜题的推广形式显然有多项式算法。谜题结构很简单，解一个Z4环上的线性方程组既可。下面是具体解法。

箱子上有五个的转筒，每个转筒按相同顺序刻有四种图案：黑桃、红桃、梅花、方片。初始状态为（方，红，方，黑，梅），若用鼠标点击某个滚筒，它自身朝左或右绕轴转90度的同时会带动另外某两个筒旋转。规律如下表：

其中m行n列的文字表示用鼠标点击第m个筒时第n个筒的反应（向*转一下），空则表示不变。

注：环上矩阵的初等行变换与数域上矩阵的初等行变换有所不同，当用环中某元素乘某一行时，元素必须是可逆元。
下面给出计算代数软件Magma的求解代码。软件有在线版[11]，感兴趣者可以把代码贴进去一试。
K:=RingOfIntegers(4);
A:=Matrix(K,5,5,[[1,3,1,0,0],[1,1,0,0,3] ,[0,3,1,3,0], [3,0,0,1,1] ,[0,0,3,1,1]]);
b:=Vector(K, [0,2,2,1,3]);
V:=Solution(A,b);
V;
参考文献：
[1]《费曼手札》 P60 三联书店 “猫咪”为费曼对妻子阿琳的昵称。
[2] Application of Puzzle Theory http://junk.dk/puzzle/#gui
[3]《红楼梦》 P765人民文学出版社
[4] AVG迷题探索（01） https://www.chinaavg.com/read.php?tid=8281
[5] Rotational Puzzles on Graphs  http://www.jaapsch.net/puzzles/graphpuzz.htm
[6] http://www.gap-system.org
[7] http://www.math.colostate.edu/~hulpke/CGT/education.html
[8] Richard M. Wilson.  Graph puzzles, homotopy, and the alternating group 74
[9] Daniel Kornhauser, GaryMiller, and Paul Spirakis. Coordinating pebble motion
on graphs, the diameter of permutation groups, and applications
[10]《符号与象征》P235 三联书店
[11] http://magma.maths.usyd.edu.au/calc/
[12] Alex Fink and Richard Guy  Rick’s Tricky Six Puzzle: S5 Sits Specially in S6