益智游戏“汉诺塔”中的矩阵运算

王在华， 李 静

(陆军工程大学 基础部，南京211101)

1 引 言

数学能引起人们的兴趣至少有三种原因：数学是有趣的，数学是美的，数学是有用的[1].对多数人来说，趣味性最容易感受到.因而，趣味性是中小学数学教师在设计教学内容时必须考虑的重要因素.进入大学阶段后，教学内容的趣味性逐渐被淡化，而对数学美的欣赏、对数学理论的普遍性和统一性的追求、以及运用数学理论与方法解决实际问题成为数学课程教学中更为重要的内容.实际上，淡化趣味性并不是说趣味性不好，而是难以找到契合大学数学课程教学内容、符合大学数学课程教学特点的趣味性问题.因此，发掘适合大学数学课程教学的趣味性问题仍然可成为大学数学老师开展教学研究的重要方向之一.

汉诺塔问题源于印度一个古老的传说故事，其大意是：大梵天创造世界的时候做了三根金刚石柱子，分别称为A，B，C，在柱A上从下往上看按照从大到小顺序摞着64片可以移动的黄金圆盘.大梵天命令婆罗门把圆盘按规则从柱A移动至柱C上，圆盘在柱C上堆放的顺序与原来在柱A上堆放的顺序完全相同.圆盘移动规则是：每次只能移动一片圆盘，且小圆盘上不能放大圆盘，但可利用三根柱子做中转.

这个传说中的圆盘移动任务看似简单，实际上是不可能完成的.事实上，一般地，设柱A上有符合要求的圆盘n片，将n片圆盘按要求移动到柱C上的问题称为n阶汉诺塔问题，记最少移动次数为f(n).对n阶汉诺塔问题，要完成这个移动圆盘的任务，可以分为三个阶段性任务：首先将柱A最上面的n-1片圆盘移动到柱B，最少移动次数是f(n-1)，然后将留在柱A上最大的圆盘移动到柱C，移动次数是1，再将柱B上的n-1片圆盘移动到柱C，最少移动次数为f(n-1)，于是有差分方程

f(n)=2f(n-1)+1.

由于f(1)=1，并且f(n)≡-1满足差分方程：-1=2×(-1)+1，所以有

f(n)-(-1)=2(f(n-1)-(-1))，

于是f(n)-(-1)=2n-1(f(1)-(-1))，从而求得f(n)=2n-1.特别地，由公式可得

f(2)=3，f(3)=7，f(4)=15，f(5)=31.

完成2阶汉诺塔问题的移动方案一目了然，只要三步即可，但完成5阶汉诺塔问题最少需要31步，需要一定的耐心.假设移动一次圆盘平均用时1秒，一年365天工作不停歇，可移动365×24×60×60=31536000次，那么按最少次数完成64阶汉诺塔所需要的年数近似为

这是一个天文数字，使得移动圆盘的任务无法完成.

2018年出版的专著[1]对汉诺塔的历史、求解方法以及不同角度的数学联系与推广进行了详细的介绍，内容丰富，图文并茂，对关注趣味性问题的数学研究与教学的数学教师来说，是一本不可多得的参考书.另外，汉诺塔问题作为递归算法的一个重要范例在计算机软件设计等课程得到了充分讨论.本文的目的是用线性代数的观点重新考察汉诺塔问题，采用矩阵描述汉诺塔的状态及圆盘移动过程，利用矩阵幂运算寻找完成圆盘移动任务的所有移动方案.

2 汉诺塔运动的矩阵描述

线性代数课程的基本内容是利用矩阵(包括其特例，向量)及其运算来研究线性方程组、线性变换与线性空间以及在二次型化简中的应用.线性代数思维的特点是将具有某种特性的数据作为一个整体以矩阵的形式呈现出来，并利用矩阵运算寻找问题的解答.

对汉诺塔问题，为了从整体上表示圆盘位置以及位置的变化，用数字1，2，…，n表示从小到大的圆盘，并且将柱A，B，C上的圆盘标号存放在矩阵的第一列、第二列和第三列，这样，n阶汉诺塔作为一个整体可用一个n×3矩阵S=[sij]n×3来表示.若k号圆盘在矩阵的(i，j)位置，则定义sij=k(k=1，2)，否则取sij=0，表示此位置没有圆盘.这样的矩阵称为n阶汉诺塔的状态矩阵.移动圆盘的过程可用圆盘移动矩阵T=[tij]n×3来表示.用-表示圆盘移出，+表示圆盘移入，若k号圆盘由(i1，j1)位置移动到(i2，j2)位置，则有ti1j1=-k，ti2j2=+k，其他元素都取为零.状态矩阵与圆盘移动矩阵可以各自独立构造，结构清晰，易于构造.

以2阶汉诺塔为例，初始状态矩阵和目标状态矩阵分别为

按要求通过移动圆盘使初始状态矩阵S1变为目标状态矩阵S2，移动圆盘三次即可，对应的圆盘移动矩阵分别为

特别有意思的是，移动圆盘的过程可以用矩阵加法来表示，将初始状态矩阵S1变为目标状态矩阵S2只需要做三次矩阵加法即可，即

或者简记为

S1+T1+T2+T3=S2.

同样，矩阵加法与减法互为逆运算，将状态S2变为状态S1可用下式来表示：

S2-T3-T2-T1=S1.

完成2阶汉诺塔游戏的思路和过程非常简单，从玩游戏的角度讲是一种极其平凡的情形，不值得研究，但其中蕴含的数学思想具有普遍性，适合于解决任意阶汉诺塔问题.例如，对三阶汉诺塔，其状态矩阵是三阶矩阵，初始状态矩阵和目标状态矩阵分别是

要将柱A上标号为1，2的圆盘移动到柱B上，对应的圆盘移动矩阵分别是

此时有

文[2]采用矩阵描述汉诺塔的不同状态，并给出了低阶汉诺塔从初始状态矩阵对目标状态矩阵的圆盘移动方案中的各状态矩阵，但没有引入圆盘移动矩阵及矩阵之间的加法运算，也没有交代如何才能找到完成汉诺塔问题的圆盘移动方案.

3 利用邻接矩阵的幂矩阵寻找圆盘移动方案

2阶汉诺塔问题的圆盘移动方案可按三个步骤计算出来.

第一步 列出可能的状态矩阵.这里，除了前面出现的状态矩阵S1，S2，S3，S4外，还会想到下面的可能状态：

当然，还可以有两个圆盘全在柱B上的情形，但此时再要将圆盘全移动到柱C上，移动圆盘的总次数肯定不是最少的，所以可忽略这种情形.

第二步 构造邻接矩阵.在这类问题中，只移动一步的前后状态矩阵是很容易确定的.例如，只移动一步，就可以将S1变为S3，将S5变为S6，但不可能将S1变为S4，也不可能将S5变为S7.如果移动一步可将Si变为Sj，则定义vij=1，否则定义vij=0，从而得矩阵

其中非零vij的取值皆为1，保留这个记号可强化它的实际含义，即表示由Si移动一次圆盘变成Sj.矩阵V在图论中称为由顶点集{S1，S2，…，S8}构成的图(Graph)的邻接矩阵[3].这个矩阵把只经过一次圆盘移动即可从某个状态到另一个状态的所有可能以一个整体形式呈现出来.反之，这个矩阵规定了八个状态矩阵S1，S2，…，S8之间单步移动的所有可能情况.

这表明要完成2阶汉诺塔游戏，至少需要移动三次柱上的圆盘.移动次数最少的移动方案是S1→S3→S4→S2.如果容许4次移动，则移动圆盘的方案有两种：S1→S3→S4→S8→S2和S1→S5→S3→S4→S2，其中的S4→S8→S2和S1→S5→S3各自增加了一次无用的移动，相应的移动方案都不是最优的.

与8阶邻接矩阵得到的结果完全相同.

对高阶汉诺塔问题，同样可以按上述三个步骤求得圆盘移动方案，只不过其中确定可能的状态矩阵和计算邻接矩阵的幂矩阵的过程更繁琐一些.不仅如此，本文方法还可以求解一大类问题：“在有限个状态中，不同状态之间有单向或双向连接，寻找由某个特定状态经过这些连接到另一个特定状态的所有可能连接方式”.处理这类问题的困难在于第一步，即确定一个合适的可能状态集，并且不遗漏单步将可能状态中某个状态变为另一个状态的所有可能性.一旦完成这个步骤，构造邻接矩阵及计算其幂矩阵都可由计算机软件自动完成.

4 结 论

汉诺塔是一个深受小朋友喜爱的经典益智游戏，其背后蕴含深刻的数学思想.不同于以往的文献，本文采用矩阵描述汉诺塔状态和圆盘移动过程，其构造既直观又简单，进而将圆盘从一个位置移动到另一个位置转化为矩阵的加法，其过程简洁且含义清晰.进一步，本文通过构造若干可能状态矩阵之间的邻接矩阵，计算其幂矩阵，来寻找圆盘的移动方案.实际上，利用邻接矩阵的m次幂矩阵可求得从任意指定的一个状态经过m次移动圆盘到任意指定的另一状态的所有可能移动方案，这种方法是非常简单和有效的.包括“农夫过河”[1，4]、“嫉妒的丈夫(jealous husbands)”[1]等趣味问题都可以采用这种方法得到解决.这些内容可以成为以兴趣促进大学生学好线性代数课程的有益素材.

汉诺塔问题的解决有助于理解和掌握矩阵运算及线性代数思想，类似的例子诸如三阶幻方(九宫格)、点灯游戏、猴子分桃、韩信点兵、Fibonacci数列等都是线性代数课程教学的好素材[5-8].三阶幻方更是一个不可多得的好例子，几乎可以贯穿工科线性代数课程的始终，它不仅可以用来阐述或检验线性方程组的通解理论，还可以用于阐述或检验线性相关、线性无关、线性空间、矩阵运算、向量范数、特征值与特征向量等概念.以趣味问题为抓手，以提高学生学习线性代数课程的兴趣和效果为目标，大学数学教师大有可为.

致谢专著[1]关于趣味问题的评述引发作者对汉诺塔问题的进一步思考，在此表示感谢！