本帖最后由 deducemath 于 2012-2-24 17:34 编辑
/ X i1 z, @: v3 j
2 ^. _. K+ F3 B* n# I. @ Y- H3 p9 m声明:本文涉及高等数学,存在没有明确定义的概念,某些描述比较笼统。原因有二:其一,阐述清楚繁琐而费时;其二,此文属自娱型。想弄明白的读者请查阅相关文献。
' x' `- P1 j0 F: u2 Z6 J 0 D8 p5 c& _+ ?' V
我之所以这么喜欢开锁,可能主要是因为我喜欢解各种各样的谜题。每个锁就好像一道谜题。……猫咪,你有时也像谜一样,但我最后还是会解开你的。” . x. u& X, Y, U$ U$ A
——Richard P. Feynman[1]9 B* ~; [, y& E# m
我迷恋上了钥匙,并开始制造它们。先是把自己家的各种锁一一打开,偷看大人的秘密,后来就发展到未经邀请的去开别人家锁着的门。每当锁舌铛的一声跳开,我便陷入无限的欣喜之中。& m! j) V. p* |; Y" k$ f. F n
——马小军(《阳光灿烂的日子》主角). y K9 E* i- g# h9 P$ K. p
4 _8 A4 H; d+ I, v- Y- a
人们天生对隐秘的事物感兴趣。一些人喜欢撬锁因为开锁之后可以做所谓有趣的事儿。例如,在电影《阳光灿烂的日子》里,正太马小军爱偷看大人秘密;诺兰的处女作《追随》中克布“喜欢”由房间里的私人物品揣测屋主的特点,拿走或搞乱一些东西以“干扰某人的正常生活轨迹,让他们重新审视原本已熟视无睹的一切。” 我本人则比较享受撬锁的过程。上海美术电影制片厂的动画片我小时候看过不少,系列动画《邋遢大王奇遇记》有个片段记忆犹新,可以说,这是关于解锁谜题的最初记忆。 ( k$ ]1 H7 f" ^! L2 L
, a/ r8 o0 b2 C- j$ r' y《邋遢大王》第9集秘密地图之“箱锁” ( b7 n6 v4 M( n; \
本文之锁非现实之锁,究其原因,或许自己不具备费曼撬锁的天赋,而撇了一眼还算饱满的钱包后我忽然意识到,这可能不是真实原因。对锁匠来说,撬锁不仅是个细致的技术活,还比较费体力。一般而言,我欣赏纯文纯理的东西。我始终期盼一本以撬锁为核心谜题的推理小说横空出世,它具备爱伦坡的趣味性及种种锁具的手绘插图。虽然国内小说《锁侠》、《天锁》以撬锁为主题,可惜语言乏味,内容玄幻离奇,没有丝毫推理解谜的乐趣可言,而日本推理作家法月伦太郎的《失窃的信》则过于简短不成系统。——还好,AVG不乏撬锁谜题。
) Z0 K9 \ }0 {& N, w- S# y" H! |( @* q. F1 L
讲AVG谜题设计的文章[2]把撬锁谜题归于GUI /Board Puzzles。而在Mechanical Puzzles中它们则属于Sequential Movement Puzzles。 这些小谜题一般比较容易,凭直觉就可以破解,有时需要纸笔作点记录画些草图,也费不了多少时间。 从审美学的角度看,上等好锁的材质、形式和意蕴都要趋于完美。而如果一把锁的数学结构优雅而精致,那么它在意蕴上就已经满足成为上等锁具的条件。注意,我论述的是撬锁的艺术,不要只迷恋GUI的华丽,或者满足于开锁后幼稚的成就感。以博学著称的宝姐姐曾教导我们,“小事上用学问一提,那小事越发作高一层了。不拿学问提着,便都流入世俗去了[3]”。所以我得用点学问提一下,这点学问具体指的是初等群论和图论。群论是数学中描述对称的语言,19世纪初法国数学家Galois(1811-1832)用它完全解决了5次以上代数方程的根式求解问题,20岁时他为一个女人死于决斗。图论起源于Euler(1707-1783)关于哥尼斯堡七桥问题(推广问题俗称一笔画)的一篇论文。下面我通过分析几个经典锁具来展示撬锁之艺术。先摆上第一把锁:
& s9 V) @( [1 Y4 P7 \破箱人_拼图铁箱 & E$ h3 d( P3 A7 u$ r
$ K9 S0 b& h' u) U5 [
tabris在“AVG谜题探索(01)”[4]中分析过此锁,但文中定理一有错,其实那8个方块的所有排列均可获得。下面给出Jaap的定理,很多旋转类谜题可以由此定理得到其排列的群结构。 / f- k6 T1 \2 Q* e
图上的旋转谜题定理[5]:设图G顶点数为n,每个顶点上放置一个转块,且每一个转块经过某些旋转操作之后都可以到达G的任意一个顶点。若G上存在两个旋转圈使得两圈的公共部分恰为一条路,则除两个特例之外,有3种情形:( u5 |: d5 u0 a
1、若G是圈,群为Zn。
# _2 \ h# C9 ^9 R% `# j" w' l2、若G上无偶旋转圈,群为An。
! `& k. m+ g' M4 a0 d3、否则群为Sn。( Z$ c: l9 a3 |/ s# L
其中Zn为n阶循环群,An为n阶交错群,Sn为n阶对称群。两特例如下图所示,它们对应的旋转圈分别为{(1,2,3,4),(2,6,5,4,3)},{(6,1,4,5),(1,2,3,4)},群都与S5同构。
( U3 B& ?& m+ o! \
; w4 y3 w1 U( B, E 据Jaap定理,拼图铁箱的群为S25,所有排列均可得到。存在一些旋转谜题不满足定理条件,举一个简单的例子:Hungarian Rings。如下图:/ z0 {* W( A f- v; n
0 H4 ?0 D# G+ s所以此定理有待推广。规模较小的旋转谜题用计算代数软件GAP[6]求解只需短短几行代码,使用起来非常方便。可以在[7]下载适用于XP和Vista系统的GAP软件。如果谜题旋转圈较多,输出答案可能很长,操作不方便。最好先凭直觉排好一部分,剩下的子迷题再用软件求解(一般当群为Sn时容易使用此法)。例如,若拼图铁箱与本文截图一致,限制在右下方8个小方格中的子迷题可以用如下三行代码:& x0 X, `9 V7 g) k" G" k
G:=Group((1,2,4,3),(3,4,6,5),(5,6,8,7));
) a- @. E( \! \( q' D+ ^7 qW:=EpimorphismFromFreeGroup(G:names:=["a","b","c"]);5 h+ q1 o6 I/ n" U2 \
P:=PreImagesRepresentative(W,(3,4,8,7));8 D7 Z D, T1 A7 I* n2 z
输出结果: c*b*c*b*c*b*a*b^-1*a*c^-1*b^-1*a*b。; t3 s3 K+ y C9 H; b/ m: j* ~
现在摆出第二把锁:0 f* ~, b% e# p- b* `8 c w
静物_九宫锁
5 b9 C* m- `. \" a0 {* s2 E2 Z9 I* l R' B8 Y
“当我想以一个词来表达音乐时,我找到了维也纳;而当我想以一个词来表达神秘时,我只想到了布拉格(尼采,1844-1900)。”此时此刻,你处于这座神秘之城的地下世界,被潮湿和黑暗裹挟,在迷宫般的下水道中摸索前行。最终一扇铁门挡住去路,门上呈现的就是这么个装置,颓败,锈迹斑斑,结构精巧。放上好不容易收集到的六个小巧的银戒指,装置开启。金属细细的摩擦声与阴郁诡异的背景音乐交织在一起……
- s( z) F" e9 R1 ]: m! `, v _! I5 E x6 l
把钥匙调整到最顶层最少步数可能为21,你可以编程验证,但这不是我关心的问题。我的问题是,如果让九个滑块位居中央,所有的排列方式都能得到吗?否。九个滑块的变换群为A9,只能得到一半排列。证明思路如下:
8 I& X; @/ A/ b; V- @/ o- ~ O
8 B' k: d0 S8 w$ t% @( f0 R: F* B/ J 先证群中不含奇置换:将处于中央位置的9个滑块的置换群看作是它们与12个空滑块的置换群的子群,群中任一置换为一系列基本置换(每个拉杆的拉动操作对应一个基本置换)的乘积,乘积中每个基本置换与其逆元出现次数相同(保证九宫格复位),故为偶置换。为证群是A9,使用某些基本置换的乘积得到一些旋转圈对应的置换。例如用四个基本置换相乘得到右下角三个滑块的顺(逆)时针旋转(其余滑块位置保持不变)。 构造的旋转圈的并含有九宫格对应图的九个顶点,由Jaap定理即可得证。
! k; W6 h! \9 P) Q# ]( F# ~* [9 I8 Y3 Q2 C6 G8 c" I4 k0 `
最初我以为九宫锁为本游戏原创,后来在网上下到Hordern的《Sliding Piece Puzzles》的电子版,插图11中有类似谜题。如下图:左下角谜题为九宫锁的4*4形式。
0 f$ _+ U' w4 s0 V% W3 h
: n1 i' k/ O i: B第三把锁——静物_吊车锁
" x6 r6 p& V3 a( H% I; g; Z) A
! G3 n- u7 r% n 《Sliding Piece Puzzles》插图3中画着蓝精灵的滑块玩具与吊车锁结构一样。 蓝精灵是80后最钟爱的卡通人物之一,一提蓝精灵,那纯净轻快的主题歌似乎又萦绕耳边:“在那山的那边海的那边 有一群蓝精灵 他们活泼又聪明 他们调皮又灵敏……”。可惜这两个家伙的名字我记不起来了。再看插图3,右上角是停车库版的吊车锁,可能某个有眼光的制造商看了《亨利·杜德尼的数学趣题》之停车库趣题后将其做成了玩具。2 K& G6 |' M0 y1 L- z: a; Y3 U$ o& i
# u2 r& n4 M% w1 q% d
吊车锁与15-Puzzle等经典的滑块类谜题可以推广到一般形式。Richard M. Wilson[8] 74年证明了无割点图上仅空一格的滑块谜题的置换群定理,但吊车锁是树上空4格的谜题,定理不适用。84年有三个人给出下面的推广定理,应用于吊车锁,群为S6。( V0 ~* a- }7 P2 \/ C
图上的滑动谜题定理[9]:设图G顶点数为n。在其中k个顶点上放置滑块,每个顶点放一个,k<n,且每一个滑块都可以到达G的任意一个顶点。则除一个特例外,有3种情形:
0 `, z- d: C3 f% W: |1、若G是圈,群为Zk。5 A F# {0 W2 T# H
2、若G是二部图,且k=n-1,群为Ak。2 `. j7 z2 j' {' R, J' }, y5 C
3、否则,群为Sk。 ) E/ ~! b/ i7 p
特例[12]如下图所示,群与S5同构。! }" Y* x* ^4 B3 d% o# e( i- @
; p- U6 z3 a" z8 ^' ]9 i$ b+ ] 如果图上存在滑块不能到达所有顶点,则谜题能分解成一些子迷题,举例如下图所示,原谜题置换群为子迷题置换群的直积。
, q& x; D4 o+ o) i' `5 e* H6 r- n6 y3 W2 u6 M) \5 l t" n
第四把锁——静物_祖父箱子的密码锁
1 |9 l$ }; F: L/ r
& a1 D* g2 S/ L 从符号学的角度看,祖父的箱子放在阁楼里有象征意义:“阁楼(储藏室)代表尘封的回忆或被人忽略的真相,等待有心人去发掘。[10]”此谜题很多人分析过,甚至有用枚举法编程求解的,然而此谜题的推广形式显然有多项式算法。谜题结构很简单,解一个Z4环上的线性方程组既可。下面是具体解法。" R7 X' W, q7 y, o+ ^
8 T( z0 H/ O: K1 F 箱子上有五个的转筒,每个转筒按相同顺序刻有四种图案:黑桃、红桃、梅花、方片。初始状态为(方,红,方,黑,梅),若用鼠标点击某个滚筒,它自身朝左或右绕轴转90度的同时会带动另外某两个筒旋转。规律如下表:
$ A, D; q! w: V+ S
/ N* X! n; Y+ k4 h/ f/ [' @1 z$ r其中m行n列的文字表示用鼠标点击第m个筒时第n个筒的反应(向*转一下),空则表示不变。& d! `4 b A# W" {! S
; l1 y, e: u0 V X8 m注:环上矩阵的初等行变换与数域上矩阵的初等行变换有所不同,当用环中某元素乘某一行时,元素必须是可逆元。8 U/ {/ Q" m/ |& t& x, A
下面给出计算代数软件Magma的求解代码。软件有在线版[11],感兴趣者可以把代码贴进去一试。0 {/ r2 T n( Z# t, h: u) s1 a0 |
K:=RingOfIntegers(4);
( ^% n2 Y& q' l f7 B8 n; H3 AA:=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]]);: U% }% | P- X* b$ V; @
b:=Vector(K, [0,2,2,1,3]);
" ?* S, y) r/ K3 a1 OV:=Solution(A,b);
0 n' d; U; T k9 O2 ?% r" j: zV;
, ^/ m" ?0 x0 ^参考文献:* _) [1 }) |; e2 d0 v1 J' @
[1]《费曼手札》 P60 三联书店 “猫咪”为费曼对妻子阿琳的昵称。0 A9 ^: e( ?/ S
[2] Application of Puzzle Theory http://junk.dk/puzzle/#gui
K8 V, _* E& W3 G8 x[3]《红楼梦》 P765人民文学出版社" Z! b+ T4 J* T E
[4] AVG迷题探索(01) https://www.chinaavg.com/read.php?tid=8281
& B4 m) j' k" M! @7 t5 m( ^[5] Rotational Puzzles on Graphs http://www.jaapsch.net/puzzles/graphpuzz.htm# ]2 }% G& { I. k
[6] http://www.gap-system.org7 Q* L5 b' _6 `/ x! h
[7] http://www.math.colostate.edu/~hulpke/CGT/education.html$ |7 c) e, y% c, D( ^- W1 U
[8] Richard M. Wilson. Graph puzzles, homotopy, and the alternating group 742 u- ]; h" K8 y% T& L1 ?
[9] Daniel Kornhauser, GaryMiller, and Paul Spirakis. Coordinating pebble motion8 ~0 X5 ?9 T1 x. M Q5 A
on graphs, the diameter of permutation groups, and applications
# h$ a; e0 V& |6 o" a- ^[10]《符号与象征》P235 三联书店7 a* |! ?1 A1 F9 M" Y. G
[11] http://magma.maths.usyd.edu.au/calc/
5 V$ G, T# X* R/ r( S8 X& _' p, a5 G[12] Alex Fink and Richard Guy Rick’s Tricky Six Puzzle: S5 Sits Specially in S6 |