九连环游戏

十、九连环游戏

一、“九连环”游戏概述

在众多的科学玩具中，我们祖先发明的“九连环”，算是一种难得的、令人拍案称奇的珍品！

“九连环”由九个相同的，如下图一个扣着一个，且带着活动柄的金属环，和一把剑形的框套组成(下图).所有金属环上的活动柄都固定在一根横木条上.

游戏的目的，是要把九个金属环逐一地从剑形框套中脱下来，形成环和框分离的状态；或者从原先分离的状态出发，恢复成上图所示的一环扣一环的样子.

“九连环”在我国民间流传极广，源远流长.在许多古代文学名著中(如《红楼梦》等)，都有关于玩“九连环”游戏的描写.“九连环”游戏，大约在16世纪以前，便已传到国外.最早见自1550年出版的著名意大利数学家卡当(Cardano，1501—1576)的著作，称之“中国九连环”.

下面，我们研究解“九连环”的一般规律.

为使脱环的动作数量化，我们把下页图所示的两种脱环手法，每一种都定义为一个“基本动作”：

很显然，脱下第1个环，只需要一个基本动作(1).而要脱下头2个环，必须先用一个基本动作(2)，把第2个环退到剑形框下，再用一次基本动作(1)，脱下第1个环.也就是说，要脱下头两个环共需两个基本动作.

如果我们把脱下头k个环所需要的基本动作数记为f(k)，那么上述结果便可记为

f(1)＝1，f(2)＝2.

通过细心而逐步地尝试，可知要脱下“九连环”中的第1至第9个环，至少需要用的基本动作数分别为

1，2，5，10，21，42，85，170，341.

观察这一列数，不难发现以下的规律，即：

A.处于偶数位的数，都等于前一位数的两倍；

B.处于奇数位的数，都等于前一位数的两倍加上1.

对于“九连环”游戏，我们要研究的问题有三个：

(1)怎样证明脱环的基本动作数，符合上述规律？

(2)对于任给的“n”，f(n)＝？

(3)所谓“状态”指的是：在脱环过程的某一时刻，有一些环已退到剑形框下，而另一些环却仍在框上的态势.

一个重要且困难的问题是：从任何一种状态出发，到达另一种状态，所需要的基本动作数是多少？

例1　如下页图，“九连环”中的第7个环，已脱至剑形框下.试问，从初始的状态(九环均在剑形框上)开始，需要经过几步的脱环动作，才能达到图中的状态？

解　假定从初始的状态开始，达到图中的状态需要经过X步的脱环动作.那么，接下去可再用f(6)步基本动作将头6个环脱下.至此，连同第7个环，头7个环都已退到剑形框下.

由于从初始的状态开始，到脱下头7个环，所需的基本动作数为f(7).从而有

X＋f(6)＝f(7).

解得X＝f(7)－f(6)＝85－42＝43.

即从初始的状态达到图中的状态需要运作43步.

正如前面所说，要做到“九连环”玩具的九个环与剑形框柄脱离，必须进行341次基本动作.由于脱环的过程必须做到眼、手、脑并用，而且基本动作之多，少说也要花上五分钟时间，因此从事这项游戏，对于人们的智力和耐性，都是一个极好的锻炼.

“九连环”是一种值得保藏的益智玩具.建议读者买一把小学生用的短木尺及九个钥匙环，再找几段铁丝，模仿本节开头的图样，做它一副.我想，这副由你亲手制作的玩具，其受益者肯定不止你一个！

二、“九连环”问题的瓦里斯模型

1685年，英国数学家瓦里斯(J.Wallis)对“九连环”提出了以下的数学模型：

设想“九连坏”的脱环，按照以下的程序：

假定头k个环已如下页图(1)，用f(k)次基本动作脱下，(图中k＝3)；那么接下去可以如图(2)，用1个“基本动作(2)”，把第(k＋2)个环退到剑形框下；再接下去把原已脱下的k个环还原.显然，所用的基本动作数与当初脱下时所用的基本动作数同为f(k).最后，再如图(3)，用f(k＋1)次基本动作把头(k＋1)个环脱下.

以上的一连串动作，显然对已脱下的第(k＋2)个环毫无影响.这意味着，此时我们实际上已经把头(k＋2)个环脱了下来.

由于脱下头两个环是很容易的事，所以脱其他的环，便可以按照上面的程序，一步一个脚印地进行下去.

(1)

(2)

(3)

由上述程序，可得

f（k＋2）＝f（k）＋1＋f（k）＋f（k＋1）

　　　　 ＝f（k＋1）＋2f（k）＋1.

把上式变形为

将以上k个等式相加，并消去等式两端相同的项，得

u_k＋1＝2^ku₁＋（1＋2＋2²＋…＋2^k－1）.

∵　u₁＝f（2）＋f（1）＝2＋1＝3，

∴　u_k＋1＝3·2^k＋2^k－1＝2^k＋2－1.

这样，我们便有以下两个关于f(k)递推式子：

将以上两式相加，得

同理，当k＝2m＋1时有

综上，对于任意的正整数n，我们有

由以上公式，可以算出九连环数列｛f(n)｝：

1，2，5，10，21，42，85，170，341，….

例2　九连环数列｛f(n)｝中的变量n，可以是任意的正整数.为什么我们“九连环”玩具中的环数要采用“9”，而不用较小的“6”，“7”，或较大的“12”，“15”呢？

解　一般人玩“九连环”的脱环速度，一秒钟大约可以完成一个基本动作.对于较小的n，当n＝6，7时，

f(6)＝42，f(7)＝85.

即整个游戏只要一分钟左右.当人们刚准备投入时便告结束，显然不太适宜.而且环数太少，也显得比较单薄.所以，n不能取太小.

但n也不宜取太大，因为随着n的增大，脱环所需的基本动作数f(n)将成倍地增大，当n＝12，15时，

f(12)＝2730，f(15)＝21845.

前者需不间断地脱45分钟，后者更需要脱一整天，而且还不允许中途出点差错，这就更加地不适宜了.再说，环数太多，操作起来似乎也不太方便.

所以玩具的环数，以8～10为宜.其中n＝9时，f(9)＝341，游戏的全过程大约只需要5分钟，不多不少，恰到好处.

问题10—01：

[难度系数：★☆☆☆☆]

如图，“九连环”的头七个环，已退到剑形框下，框套上还有第8、第9两个环.

试问，应如何把最后这两个环也退下，使环与框彻底分离？

答案在第221页.

问题10—02：

[难度系数：★★☆☆☆]

已知：除第7个环外，其余的环都在剑形框上(见例1图).

试问，从上述状态开始，还需多少步基本动作，才能使“九连环”的九个环都从剑形框套中脱下来，形成环和框分离的状态？

答案在第221—222页.

三、“九连环”问题的梵塔模型

本节我们将用一种前人所没有触及的崭新方法，来解决古老的“九连环”问题.为此，我们先从“梵塔问题”和“西萨·班问题”讲起.

[梵塔问题]

“梵塔问题”也称“河内问题”，它源于以下的古老传说.在世界中心贝那勒斯(印度北部的佛教圣地)的圣庙里，安放着一块黄铜板，板上插着三根宝针，细如韭叶，高约腕尺.

梵天在创造世界的时候，在其中的一根针上，从下到上串上由大到小的64片金叶.这就是梵塔.当时梵天授言：不论黑夜白天，都要有一个值班的僧侣，按照梵天不渝的法则，把这些金叶在三根针上移来移去，一次只能够移一片，并且要求不管在哪根针上，小片永远在大片上面.当所有的64片，都从梵天创造世界所放的那根针，移到另外一根针时，世界就将在一声霹雳中消灭.梵塔、庙宇和众生，都将同归于尽！

这，便是世界的末日.……

“梵塔问题”可以通过以下的方法加以解决.

直接作转移尝试可知：如果A针上只有一片，要把它转移到C针上去，只需移动1次；如果A针上有两片，要把它转移到C针上去，需移动3次.

下面让我们看看，如果A针上有三片，要把它全部转移到C针上去，需要怎么移动？不难推知，移动的方法是：先用3次移动，把头两片转移到B针；用1次移动将第三片移到C针；最后再用3次移动，把B针上的两片转移到C针.至此完成全部三片的转移.完成三片转移的动作次数，等于完成两片转移的动作次数的两倍加上1次.即

N₃＝2N₂＋1＝2×3＋1＝7.

上述规律显然适用于任意片.由此可以逐步推出：

N₄＝2N₃＋1＝2×7＋1＝15，

N₅＝2N₄＋1＝2×15＋1＝31，

N₆＝2N₅＋1＝2×31＋1＝63，

N₇＝2N₆＋1＝2×63＋1＝127，

N₈＝2N₇＋1＝2×127＋1＝255，

N₉＝2N₈＋1＝2×255＋1＝511.

如果我们眼睛更亮一点，不难得出以下结论：要把A针上的k片，全部转移到C针上去，需要移动的次数N_k为

N_k＝2^k－1.

从本题解答中的分析，要把梵塔上64片金叶，全部转移到另一根针上去，需要移动的次数为

N₆₄＝2⁶⁴－1≈1.84×10¹⁹.

以一秒钟移动一次计算，这需要夜以继日地搬动5800亿年！

[西萨·班问题]

“西萨·班问题”的历史，似乎与“梵塔问题”一样地悠久.它源于另一个古老的传说：

传说，印度的舍罕国王打算重赏国际象棋的发明人宰相西萨·班.这位聪明的大臣跪在国王面前奏道：“陛下，请你在这张棋盘的第一个小格内，赏给我一粒麦子，在第二个小格内给两粒，在第三个小格内给四粒，照这样下去，每一小格内都比前一小格加一倍.陛下啊，把这样摆满棋盘上所有64格的麦粒，都赏给您的仆人吧？”

国王慷慨许诺了西萨·班的要求.他觉得宰相的要求未免寒酸.

计算麦粒的工作开始了.国王很快得知：即使拿出全印度的粮食，也兑现不了他对象棋发明人许下的诺言.

那么，国王应给象棋发明人多少粒麦子呢？

不难算知麦粒的数量S为

S＝1＋2＋2²＋2³＋…＋2⁶³.

∵　2S＝2＋2²＋2³＋…＋2⁶³＋2⁶⁴，

∴　S＝2S－S＝2⁶⁴－1＝18446744073709551615.

这个数量相当于当今全世界二千年小麦的产量.

“西萨·班问题”和“梵塔问题”这两个全然不同的问题，居然会有相同的答案，这中间不会没有关系.

事实上，西萨·班的要求可以改为另一种方式叙述：

在棋盘的第一格内，放一粒麦子；然后把第一格麦粒数的两倍，放入第二格；然后再把第二格麦粒数的两倍，放入第三格；如此等等，把每一格麦粒数的两倍，放入下一格.……

下面转到“梵塔问题”，也把它改为放麦粒叙述.

如果把完成头k片金叶从A针搬到C针，所需用的移动数当成第k格麦粒数的话，读者很快就会发现，这里的规律现在变成：

在棋盘的第一格内，放一粒麦子；然后把第一格麦粒数的两倍，放入第二格后加上一粒；接着再把第二格麦粒数的两倍，放入第三格后又加上一粒；如此等等，把每一格麦粒数的两倍，放入下一格后都再加一粒.……

这样做无疑等于在开始时棋盘中的每一格，都先放上一粒麦子，然后按“西萨·班问题”同样的做法，在第二格、第三格、……放置麦粒.两个问题之间的区别，仅仅在于棋盘上初始的设置(下简称“初始盘”)不同，如此而已.

为叙述方便，今后我们把不同初始盘状态的这一整类麦粒计数问题，统称为“梵塔模型”.

下图是“西萨·班问题”的初始盘，和“梵塔问题”的初始盘之间的比较.

由于初始盘的不相同，“梵塔问题”比之“西萨·班问题”，在每格的计数上多了由初始麦粒派生出的系列如下：

例如，当n＝64时，第64格的“麦粒数”N64为

N₆₄＝2⁶³＋2⁶²＋2⁶¹＋…＋2²＋2＋1＝2⁶⁴－1.

这就是“梵塔问题”的答案.

现在转到“九连环”问题，也把它改为放麦粒叙述.

如果把脱下头k个环，所需用的基本动作数，当成第k格麦粒数的话，那么脱环的规律现在变成：

在棋盘的第一格内，放一粒麦子；然后把第一格麦粒数的两倍，放入第二格内；接着再把第二格麦粒数的两倍，放入第三格后又加上一粒；把第三格麦粒数的两倍，放入第四格内；然后再把第四格麦粒数的两倍，放入第五格后又加上一粒；……，如此等等.总之，每到奇数格都多加上一粒.

这样做相当于初始盘如右图所示的“梵塔模型”.只是“九连环”的n等于“9”罢了.

对于右图的初始盘，每格的计数上由初始麦粒派生出的系列如下：

很明显，对于“九连环”的“梵塔模型”，当n为奇数和当n为偶数时计算的方法不一样(奇数时最后一项为“1”；偶数时最后一项为“2”).所以，对于一般的n，第n格“麦粒数”f(n)为

例如，n＝9时，f(9)＝341.这就是要脱下“九连环”的全部九个环，所需的基本动作数.

问题10—03：

[难度系数：★★☆☆☆]

已知：“梵塔模型”的初始盘状态如右图.

试对于一般的k，求第k格“麦粒数”f(k)的公式，并写出头9格的“麦粒数”.

答案在第222页.

四、“九连环”问题的格罗斯模型

如果说“九连环”的“梵塔模型”最富新意的话，那么19世纪英国数学家格罗斯提出的模型，则最为优美.

格罗斯模型的精巧之处在于，用了一种绝妙的限定，让九连环的每一种状态，与一个二进位数对应起来.而每一个基本动作，都使该二进位数变化1(即相差为1).

为了更直观地介绍格罗斯模型，我们对图形略加简化：用小圆圈表示环，用水平棒表示剑形框.如果环套在剑形框上，就把小圆圈画在棒的上边；如果环已脱下，就把小圆圈画在棒的下边.

现在回到格罗斯模型的设置上来：

格罗斯用数码“1”和“0”，交替地表示从棒的左端起穿在棒上的那些环，并用与左方邻环(不论套在棒上与否)的数码相同的数码表示不在棒上的环.如果最左端的环不在棒上，就用“0”表示它.

例如，下图所画的是连续十次的脱环基本动作，列在右边的是格罗斯模型中相应状态所对应的二进位数.

不难想象，当所有的环都不在棒上时，对应状态的二进位数为“000000000₍₂₎”，而当所有的环都在棒上时，对应状态的二进位数为“101010101₍₂₎”.所以，由前一个局势变为后一个局势，需要做的基本动作数，等于前后两个二进位数的差：

这一结果，在前面的瓦里斯模型中，读者已经得到过.

不仅如此，格罗斯模型的优点还在于：可以从任何一个状态出发，计算出由此到达另一个状态，或由此脱下全部的环，还需要多少基本动作.这是瓦里斯方法所望尘莫及的.

事实上，假定相应于两状态的格罗斯模型的二进位数分别为A(2)和B₍₂₎，则由状态A(2)到状态B(2)所需的基本动作数为

例3　在下图的“九连环”玩具中，已脱下头四个环.

试用格罗斯模型，求从“九连环”的初始状态(九个环都在剑形框上)，到题中头四个环脱下的状态所需的基本动作数.

解　设“九连环”的初始状态为(A)，题图的状态为(B).即

相应于它们的二进位数如下：

所以，由状态(A)到状态(B)所需的基本动作数为10.这一结果，与读者在本节开头的图例中，所看到的是一样的.

例4　如下页上图，“九连环”的头七个环，已退到剑形框下.

试用格罗斯模型，求把最后两个环也退下，使环与框彻底分离，还需要多少基本动作？

解　设题图的状态为(A)，“九连环”环、框分离的状态为(B).即

相应于它们的二进位数如下：

所以，把最后两个环也退下，还需要256个基本动作.

问题10—04：

[难度系数：★★☆☆☆]

如下图，在“九连环”玩具中，头三个环和第七个环已退至剑形框下.

试用格罗斯模型，求使环与框分离，还需要多少基本动作？

答案在第223页.

[答案和提示]

10—01

解　先用一次基本动作(2)把第九个环退到剑形框下；然后用f(7)＝85步基本动作，将头七个环复原到剑形框上.此时，除第九个环在剑形框下外，其余八个环都在剑形框上.

最后，再用f(8)＝170步基本动作，将头八个环退到剑形框下.这时，环与框已完全分离.

不难算出，前后所用的基本动作数为256.

10—02

解　有两种算法.算得所用的基本动作数为298.

(1)直接算法：

如右图，先通过f(6)＝42步基本动作，将头六个环退到剑形框下.这时，头七个环已退到剑形框下.

接下去，用1次基本动作(2)，把第九个环也退到剑形框下.然后让已退到剑形框下的头七个环复原，这需要用f(7)＝85步基本动作.至此，除第九个环外，其他八个环都在剑形框上.

最后，用f(8)＝170步基本动作，把头八个环退到剑形框下.这样，九个环已都与剑形框分离.综上，所用的基本动作数X为

X＝f(6)＋1＋f(7)＋f(8)＝42＋1＋85＋170＝298.

(2)间接算法：

从初始状态开始，到九个环都退下需要用f(9)＝341步基本动作.而头七个环退到剑形框下需要用f(7)＝85步基本动作.注意到头六个环原先是在剑形框上，所以要扣去f(6)＝42步基本动作.即得所用的基本动作数X为

X＝f(9)－[f(7)－f(6)]＝341－85＋42＝298.

10—03

解　比较一下本问题的初始盘，与“n连环”初始盘之间的关系.

不难看出，前者初始盘麦粒的位置，比后者初始盘麦粒的位置全部向后移了一格.这意味着本问题中的第k格麦粒数，应与“n连环”中第(k－1)格麦粒数相等.

由于“n连环”中第k格的麦粒数为

所以本题中第k格的麦粒数为

把k＝1至9代入上公式，可得头9格的麦粒数分别为

ψ（1）＝0；　ψ（2）＝1；　ψ（3）＝2；

ψ（4）＝5；　ψ（5）＝10；　ψ（6）＝21；

ψ（7）＝42；　ψ（8）＝85；　ψ（9）＝170.

10—04

解　令题图的状态为(A)，环、框分离的状态为(B)，则(A)、(B)的图式如下

状态(A)和状态(B)相应的二进位数如下：

即还需要303个基本动作，才能使环与框分离.