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