益智游戲“漢諾塔”中的矩陣運(yùn)算

王在華， 李 靜

(陸軍工程大學(xué) 基礎(chǔ)部，南京211101)

1 引 言

數(shù)學(xué)能引起人們的興趣至少有三種原因：數(shù)學(xué)是有趣的，數(shù)學(xué)是美的，數(shù)學(xué)是有用的[1].對(duì)多數(shù)人來(lái)說(shuō)，趣味性最容易感受到.因而，趣味性是中小學(xué)數(shù)學(xué)教師在設(shè)計(jì)教學(xué)內(nèi)容時(shí)必須考慮的重要因素.進(jìn)入大學(xué)階段后，教學(xué)內(nèi)容的趣味性逐漸被淡化，而對(duì)數(shù)學(xué)美的欣賞、對(duì)數(shù)學(xué)理論的普遍性和統(tǒng)一性的追求、以及運(yùn)用數(shù)學(xué)理論與方法解決實(shí)際問(wèn)題成為數(shù)學(xué)課程教學(xué)中更為重要的內(nèi)容.實(shí)際上，淡化趣味性并不是說(shuō)趣味性不好，而是難以找到契合大學(xué)數(shù)學(xué)課程教學(xué)內(nèi)容、符合大學(xué)數(shù)學(xué)課程教學(xué)特點(diǎn)的趣味性問(wèn)題.因此，發(fā)掘適合大學(xué)數(shù)學(xué)課程教學(xué)的趣味性問(wèn)題仍然可成為大學(xué)數(shù)學(xué)老師開(kāi)展教學(xué)研究的重要方向之一.

漢諾塔問(wèn)題源于印度一個(gè)古老的傳說(shuō)故事，其大意是：大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子，分別稱為A，B，C，在柱A上從下往上看按照從大到小順序摞著64片可以移動(dòng)的黃金圓盤.大梵天命令婆羅門把圓盤按規(guī)則從柱A移動(dòng)至柱C上，圓盤在柱C上堆放的順序與原來(lái)在柱A上堆放的順序完全相同.圓盤移動(dòng)規(guī)則是：每次只能移動(dòng)一片圓盤，且小圓盤上不能放大圓盤，但可利用三根柱子做中轉(zhuǎn).

這個(gè)傳說(shuō)中的圓盤移動(dòng)任務(wù)看似簡(jiǎn)單，實(shí)際上是不可能完成的.事實(shí)上，一般地，設(shè)柱A上有符合要求的圓盤n片，將n片圓盤按要求移動(dòng)到柱C上的問(wèn)題稱為n階漢諾塔問(wèn)題，記最少移動(dòng)次數(shù)為f(n).對(duì)n階漢諾塔問(wèn)題，要完成這個(gè)移動(dòng)圓盤的任務(wù)，可以分為三個(gè)階段性任務(wù)：首先將柱A最上面的n-1片圓盤移動(dòng)到柱B，最少移動(dòng)次數(shù)是f(n-1)，然后將留在柱A上最大的圓盤移動(dòng)到柱C，移動(dòng)次數(shù)是1，再將柱B上的n-1片圓盤移動(dòng)到柱C，最少移動(dòng)次數(shù)為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階漢諾塔問(wèn)題的移動(dòng)方案一目了然，只要三步即可，但完成5階漢諾塔問(wèn)題最少需要31步，需要一定的耐心.假設(shè)移動(dòng)一次圓盤平均用時(shí)1秒，一年365天工作不停歇，可移動(dòng)365×24×60×60=31536000次，那么按最少次數(shù)完成64階漢諾塔所需要的年數(shù)近似為

這是一個(gè)天文數(shù)字，使得移動(dòng)圓盤的任務(wù)無(wú)法完成.

2018年出版的專著[1]對(duì)漢諾塔的歷史、求解方法以及不同角度的數(shù)學(xué)聯(lián)系與推廣進(jìn)行了詳細(xì)的介紹，內(nèi)容豐富，圖文并茂，對(duì)關(guān)注趣味性問(wèn)題的數(shù)學(xué)研究與教學(xué)的數(shù)學(xué)教師來(lái)說(shuō)，是一本不可多得的參考書.另外，漢諾塔問(wèn)題作為遞歸算法的一個(gè)重要范例在計(jì)算機(jī)軟件設(shè)計(jì)等課程得到了充分討論.本文的目的是用線性代數(shù)的觀點(diǎn)重新考察漢諾塔問(wèn)題，采用矩陣描述漢諾塔的狀態(tài)及圓盤移動(dòng)過(guò)程，利用矩陣冪運(yùn)算尋找完成圓盤移動(dòng)任務(wù)的所有移動(dòng)方案.

2 漢諾塔運(yùn)動(dòng)的矩陣描述

線性代數(shù)課程的基本內(nèi)容是利用矩陣(包括其特例，向量)及其運(yùn)算來(lái)研究線性方程組、線性變換與線性空間以及在二次型化簡(jiǎn)中的應(yīng)用.線性代數(shù)思維的特點(diǎn)是將具有某種特性的數(shù)據(jù)作為一個(gè)整體以矩陣的形式呈現(xiàn)出來(lái)，并利用矩陣運(yùn)算尋找問(wèn)題的解答.

對(duì)漢諾塔問(wèn)題，為了從整體上表示圓盤位置以及位置的變化，用數(shù)字1，2，…，n表示從小到大的圓盤，并且將柱A，B，C上的圓盤標(biāo)號(hào)存放在矩陣的第一列、第二列和第三列，這樣，n階漢諾塔作為一個(gè)整體可用一個(gè)n×3矩陣S=[sij]n×3來(lái)表示.若k號(hào)圓盤在矩陣的(i，j)位置，則定義sij=k(k=1，2)，否則取sij=0，表示此位置沒(méi)有圓盤.這樣的矩陣稱為n階漢諾塔的狀態(tài)矩陣.移動(dòng)圓盤的過(guò)程可用圓盤移動(dòng)矩陣T=[tij]n×3來(lái)表示.用-表示圓盤移出，+表示圓盤移入，若k號(hào)圓盤由(i1，j1)位置移動(dòng)到(i2，j2)位置，則有ti1j1=-k，ti2j2=+k，其他元素都取為零.狀態(tài)矩陣與圓盤移動(dòng)矩陣可以各自獨(dú)立構(gòu)造，結(jié)構(gòu)清晰，易于構(gòu)造.

以2階漢諾塔為例，初始狀態(tài)矩陣和目標(biāo)狀態(tài)矩陣分別為

按要求通過(guò)移動(dòng)圓盤使初始狀態(tài)矩陣S1變?yōu)槟繕?biāo)狀態(tài)矩陣S2，移動(dòng)圓盤三次即可，對(duì)應(yīng)的圓盤移動(dòng)矩陣分別為

特別有意思的是，移動(dòng)圓盤的過(guò)程可以用矩陣加法來(lái)表示，將初始狀態(tài)矩陣S1變?yōu)槟繕?biāo)狀態(tài)矩陣S2只需要做三次矩陣加法即可，即

或者簡(jiǎn)記為

S1+T1+T2+T3=S2.

同樣，矩陣加法與減法互為逆運(yùn)算，將狀態(tài)S2變?yōu)闋顟B(tài)S1可用下式來(lái)表示：

S2-T3-T2-T1=S1.

完成2階漢諾塔游戲的思路和過(guò)程非常簡(jiǎn)單，從玩游戲的角度講是一種極其平凡的情形，不值得研究，但其中蘊(yùn)含的數(shù)學(xué)思想具有普遍性，適合于解決任意階漢諾塔問(wèn)題.例如，對(duì)三階漢諾塔，其狀態(tài)矩陣是三階矩陣，初始狀態(tài)矩陣和目標(biāo)狀態(tài)矩陣分別是

要將柱A上標(biāo)號(hào)為1，2的圓盤移動(dòng)到柱B上，對(duì)應(yīng)的圓盤移動(dòng)矩陣分別是

此時(shí)有

文[2]采用矩陣描述漢諾塔的不同狀態(tài)，并給出了低階漢諾塔從初始狀態(tài)矩陣對(duì)目標(biāo)狀態(tài)矩陣的圓盤移動(dòng)方案中的各狀態(tài)矩陣，但沒(méi)有引入圓盤移動(dòng)矩陣及矩陣之間的加法運(yùn)算，也沒(méi)有交代如何才能找到完成漢諾塔問(wèn)題的圓盤移動(dòng)方案.

3 利用鄰接矩陣的冪矩陣尋找圓盤移動(dòng)方案

2階漢諾塔問(wèn)題的圓盤移動(dòng)方案可按三個(gè)步驟計(jì)算出來(lái).

第一步 列出可能的狀態(tài)矩陣.這里，除了前面出現(xiàn)的狀態(tài)矩陣S1，S2，S3，S4外，還會(huì)想到下面的可能狀態(tài)：

當(dāng)然，還可以有兩個(gè)圓盤全在柱B上的情形，但此時(shí)再要將圓盤全移動(dòng)到柱C上，移動(dòng)圓盤的總次數(shù)肯定不是最少的，所以可忽略這種情形.

第二步 構(gòu)造鄰接矩陣.在這類問(wèn)題中，只移動(dòng)一步的前后狀態(tài)矩陣是很容易確定的.例如，只移動(dòng)一步，就可以將S1變?yōu)镾3，將S5變?yōu)镾6，但不可能將S1變?yōu)镾4，也不可能將S5變?yōu)镾7.如果移動(dòng)一步可將Si變?yōu)镾j，則定義vij=1，否則定義vij=0，從而得矩陣

其中非零vij的取值皆為1，保留這個(gè)記號(hào)可強(qiáng)化它的實(shí)際含義，即表示由Si移動(dòng)一次圓盤變成Sj.矩陣V在圖論中稱為由頂點(diǎn)集{S1，S2，…，S8}構(gòu)成的圖(Graph)的鄰接矩陣[3].這個(gè)矩陣把只經(jīng)過(guò)一次圓盤移動(dòng)即可從某個(gè)狀態(tài)到另一個(gè)狀態(tài)的所有可能以一個(gè)整體形式呈現(xiàn)出來(lái).反之，這個(gè)矩陣規(guī)定了八個(gè)狀態(tài)矩陣S1，S2，…，S8之間單步移動(dòng)的所有可能情況.

這表明要完成2階漢諾塔游戲，至少需要移動(dòng)三次柱上的圓盤.移動(dòng)次數(shù)最少的移動(dòng)方案是S1→S3→S4→S2.如果容許4次移動(dòng)，則移動(dòng)圓盤的方案有兩種：S1→S3→S4→S8→S2和S1→S5→S3→S4→S2，其中的S4→S8→S2和S1→S5→S3各自增加了一次無(wú)用的移動(dòng)，相應(yīng)的移動(dòng)方案都不是最優(yōu)的.

與8階鄰接矩陣得到的結(jié)果完全相同.

對(duì)高階漢諾塔問(wèn)題，同樣可以按上述三個(gè)步驟求得圓盤移動(dòng)方案，只不過(guò)其中確定可能的狀態(tài)矩陣和計(jì)算鄰接矩陣的冪矩陣的過(guò)程更繁瑣一些.不僅如此，本文方法還可以求解一大類問(wèn)題：“在有限個(gè)狀態(tài)中，不同狀態(tài)之間有單向或雙向連接，尋找由某個(gè)特定狀態(tài)經(jīng)過(guò)這些連接到另一個(gè)特定狀態(tài)的所有可能連接方式”.處理這類問(wèn)題的困難在于第一步，即確定一個(gè)合適的可能狀態(tài)集，并且不遺漏單步將可能狀態(tài)中某個(gè)狀態(tài)變?yōu)榱硪粋€(gè)狀態(tài)的所有可能性.一旦完成這個(gè)步驟，構(gòu)造鄰接矩陣及計(jì)算其冪矩陣都可由計(jì)算機(jī)軟件自動(dòng)完成.

4 結(jié) 論

漢諾塔是一個(gè)深受小朋友喜愛(ài)的經(jīng)典益智游戲，其背后蘊(yùn)含深刻的數(shù)學(xué)思想.不同于以往的文獻(xiàn)，本文采用矩陣描述漢諾塔狀態(tài)和圓盤移動(dòng)過(guò)程，其構(gòu)造既直觀又簡(jiǎn)單，進(jìn)而將圓盤從一個(gè)位置移動(dòng)到另一個(gè)位置轉(zhuǎn)化為矩陣的加法，其過(guò)程簡(jiǎn)潔且含義清晰.進(jìn)一步，本文通過(guò)構(gòu)造若干可能狀態(tài)矩陣之間的鄰接矩陣，計(jì)算其冪矩陣，來(lái)尋找圓盤的移動(dòng)方案.實(shí)際上，利用鄰接矩陣的m次冪矩陣可求得從任意指定的一個(gè)狀態(tài)經(jīng)過(guò)m次移動(dòng)圓盤到任意指定的另一狀態(tài)的所有可能移動(dòng)方案，這種方法是非常簡(jiǎn)單和有效的.包括“農(nóng)夫過(guò)河”[1，4]、“嫉妒的丈夫(jealous husbands)”[1]等趣味問(wèn)題都可以采用這種方法得到解決.這些內(nèi)容可以成為以興趣促進(jìn)大學(xué)生學(xué)好線性代數(shù)課程的有益素材.

漢諾塔問(wèn)題的解決有助于理解和掌握矩陣運(yùn)算及線性代數(shù)思想，類似的例子諸如三階幻方(九宮格)、點(diǎn)燈游戲、猴子分桃、韓信點(diǎn)兵、Fibonacci數(shù)列等都是線性代數(shù)課程教學(xué)的好素材[5-8].三階幻方更是一個(gè)不可多得的好例子，幾乎可以貫穿工科線性代數(shù)課程的始終，它不僅可以用來(lái)闡述或檢驗(yàn)線性方程組的通解理論，還可以用于闡述或檢驗(yàn)線性相關(guān)、線性無(wú)關(guān)、線性空間、矩陣運(yùn)算、向量范數(shù)、特征值與特征向量等概念.以趣味問(wèn)題為抓手，以提高學(xué)生學(xué)習(xí)線性代數(shù)課程的興趣和效果為目標(biāo)，大學(xué)數(shù)學(xué)教師大有可為.

致謝專著[1]關(guān)于趣味問(wèn)題的評(píng)述引發(fā)作者對(duì)漢諾塔問(wèn)題的進(jìn)一步思考，在此表示感謝！