益智游戲“漢諾塔”中的矩陣運算

王在華， 李 靜

(陸軍工程大學 基礎部，南京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]關于趣味問題的評述引發作者對漢諾塔問題的進一步思考，在此表示感謝！