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