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