巧解九连环

九连环是由九个相同的，一个扣着一个且带着活动柄的金属环，和一把剑形的框套组成。所有金属环上的活动柄，都固定在一根横木条上。游戏者的目的，是要把九个金属环逐一地从剑形框中脱下来，形成环和框分离的状态；或者从原先分离的状态出发，恢复成上图一环扣一环的样子。

九连环在我国民间源远流长。大约在 16 世纪以前，传到国外。最早见自

公元 1550 年出版的，著名意大利数学家卡当（Cardano，1501～1576）的著

作，称之“中国九连环”。公元 1685 年，英国数学家瓦里斯对此作了详细的数学说明。19 世纪的格罗斯，用二进位数给了它一个十分优美的解答。

下面让我们研究一下解九连环的一些规律。为方便起见，我们把脱下 k 个环所需要的基本动作数记为 f（k）。上图所示的两种脱环手法，每一种我们都称为一个基本动作。很显然，脱下一个环只需要一个基本动作（Ⅰ）， 即而脱下两个环，则需先把第二个环退到剑形框下（基本动作Ⅱ），然而再脱第一个环（基本动作Ⅰ），因此共需两个基本动作，即有为了求得 f（n） 的一般表达式，今设头 k 个环已用 f（k）次的基本动作脱下。现在，用基本动作Ⅱ把第 k＋2 个环退到剑形框下；接下去又用 f（k）次基本动作将原来已经脱下的 k 个环还原；最后再用 f（k＋1）次基本动作把头 k＋1 个环脱下。以上的一连串动作，显然对已脱下的第 k＋2 环毫无影响。因此，此时我们实际上已经把头 k＋2 个环脱了下来。注意到脱下头 k＋2 个环所需的基本动作数为 f（k＋2），从而有：

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

＝f k＋1）＋2f（k）＋1 把上式变形为

[f（k＋2）+f（k＋1）]=2[f（k＋1）+f（k）]＋1令 Uk=f（k+1）＋（k）

则 uk＋1＝2uk+1

同理 2uk＝22uk-1＋2； 22uk-1=23uk-2+22；

⋯ ⋯

2k-1u2=2ku1+2k-1

将以上 k 个等式相加，并消去等式两端相同的项得： uk+1＝2ku1＋（1＋2＋22＋⋯+2k-1）

∵u1=f（2）+f（1）=2＋1＝3

∴uk＋1＝3·2k+2k－1=2k+2-1

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

f（k + 2） + f（k + 1） = 2^k+2 - 1

f（k + 2） - f（k + 1） = 2f（k） + 1

将以上两式相加得： f（k＋2）＝f（k）＋2k+1 f（2m+2）＝f（2m）+22m+1

=f（2m－2）+22m+1+22m－1

=⋯⋯

=f（2）+（22m+1+22m-1+⋯+23）

=2+23+25+⋯+22m+1

2

= 3 (2

2 m+ 2

− 1)

即此时有f（k）

2

= 3 (2

^k − 1)

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

f（k）＝ 1 (2^k+1 − 1)

3

综上，对于任意的自然数 n，我们有：

1 (2ⁿ⁺¹ − 1); (n为奇数)

f(n) 3

2

 (2ⁿ − 1); ( n为偶数)

 3

由以上公式，可以计算出九连环数列{f (k)}：

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

因此，巧解九连环，必须进行 341 次基本动作。由于脱环的过程必须做到眼、手、脑并用，而且基本动作之多，少说也要花上五分钟的时间，所以从事这项游戏，对于人们的智力和耐性，都是一个极好的锻炼！