漢諾塔：閃爍在數(shù)學(xué)和心理學(xué)交匯之地奇妙問題

"當(dāng) 64 金片移動完成時宇宙會在一瞬間閃電式毀滅."

數(shù)學(xué)家和心理學(xué)家們的研究鮮有交集，即便有，也難想象其中有漢諾塔問題會閃爍其中。然而，漢諾塔問題在這兩個領(lǐng)域都很有吸引力。心理學(xué)上，它有助評估一個人的認(rèn)知能力。數(shù)學(xué)上，它展示了大量優(yōu)美特征，帶你直面驚人棘手的待解難題。

其游戲規(guī)則直截了當(dāng)。有三根樁和一些碟片（最早是八個），碟片按照大小順序疊在其中一根樁上，最大的碟片放在最底部。你的任務(wù)是把整疊碟片移動到另一根樁上，一次只許移動一張，期間不許大碟壓小碟。

數(shù)學(xué)家安德里亞斯·M·欣茨（Andreas M. Hinz）從數(shù)學(xué)和心理學(xué)的角度來看待這款游戲。他即將出版一本關(guān)于漢諾塔游戲的書，而且他與心理學(xué)家合作開發(fā)了一種評估病人的新工具。他解釋說，漢諾塔問題對心理學(xué)家來說如此有趣緣于其簡潔性?！斑@個游戲很容易解釋，你可以看到人們在思考，”他說?！?被試人員)在實驗組織者面前做動作，這樣你就能看清他嘗試的每一步、每一個策略。這就是心理學(xué)家如此喜歡它的原因所在?！?/p>

這個游戲特別適用于評估人們的任務(wù)規(guī)劃和任務(wù)細(xì)分能力：要移動整個塔，先得移動塔的頂端，同樣的規(guī)則也適用于后續(xù)子問題。修改問題也容易：可以添加更多碟片，或者規(guī)定新的開始和結(jié)束條件，比如說不讓所有碟片最終堆疊在一個樁上。事實證明，這兩種特性：游戲的遞歸特性及其可變性，也引出了一些非常有趣的數(shù)學(xué)問題。

游戲規(guī)劃

The Game Plan

觀察游戲結(jié)構(gòu)的最佳方法是繪制網(wǎng)絡(luò)或圖形，顯示所有可能的構(gòu)圖和移動。假設(shè)用三張碟片和三根樁來玩這個游戲。將碟1、碟2和碟3標(biāo)上序號，其中碟1最小, 碟3最大。也為樁1,樁2和樁3打上標(biāo)記?，F(xiàn)在假設(shè)碟1和碟3在樁1上，碟2在樁3上。使用三元組（1,3,1）對這種情況進(jìn)行編碼。三元組中數(shù)值的位置編號對應(yīng)于碟片編號，數(shù)值表示該碟片所在的樁。因為已知必須按大小順序排列，所以在哪根樁上放置幾號碟片就不會搞混。因此任一合法的碟片碼放方式都可以明確地以有序三元組來編碼。

連接各狀態(tài)轉(zhuǎn)移節(jié)點

現(xiàn)在在紙上把每個三元組畫到圈內(nèi)。如果單步移動碟片能夠從一個圈轉(zhuǎn)移到另一個圈，則將二者連起來。例如起始狀態(tài)（1,1,1）（所有碟片在樁1）連到了（2,1,1）（碟1在樁2，其他碟都在樁1）和（3,1,1）（碟1在樁3，其他碟都在樁1）上?？偣灿?33=27種可能存在的狀態(tài)。它們構(gòu)成如下狀態(tài)轉(zhuǎn)換圖：

漢諾塔游戲的狀態(tài)轉(zhuǎn)移圖 H3

這張圖叫做漢諾塔游戲狀態(tài)轉(zhuǎn)移圖，以H3表示。下標(biāo)3表明游戲中有3個碟子。

有了狀態(tài)轉(zhuǎn)換圖就很容易描述某人的游戲過程?！靶睦韺W(xué)家熱衷于使用狀態(tài)轉(zhuǎn)移圖，因為可以用它畫出被試者的動作序列，”欣茨解釋道，“你能從中輕易看出他有沒有做出最優(yōu)操作，或者，如果沒有，他在哪里遇到問題，在哪里長時間思考等。因此可以從個人或眾人的測試結(jié)果中掌握許多信息，假如你把眾人的些操作過程圖疊加到一起來看的話?！?/p>

玩3張碟子的漢諾塔游戲十分簡單，那么4碟、5碟、6碟或任意n碟時情況如何呢？從轉(zhuǎn)移圖來看答案非常漂亮：4碟子漢諾塔游戲的狀態(tài)轉(zhuǎn)移圖H4中包含3個H3圖，每個H3圖與其他兩個H3圖都由單邊相連。

4碟子漢諾塔游戲的狀態(tài)轉(zhuǎn)移圖H4中包含3個H3圖

類似地，H5圖由3個H4圖構(gòu)成，H6圖由3個H5圖構(gòu)成，以此類推。這是由游戲的遞歸特性決定的：如果忽略最大的碟子，n+1碟漢諾塔游戲就變成了n碟漢諾塔游戲。比如說在4碟漢諾塔游戲中，最大的碟4在樁1，對余下3張碟的任何合法操作，也同樣是忽略碟4后3碟漢諾塔游戲中的一個合法操作。因此，如果看H4圖中碟4在樁1的狀態(tài)節(jié)點（這些狀態(tài)節(jié)點的標(biāo)簽以1結(jié)尾），會看到一個H3圖。類似地，碟4在樁2時、碟4在樁3時，會分別看到各自對應(yīng)的H3圖。

如何在這些狀態(tài)轉(zhuǎn)移圖上移動？若想移動碟4，必得其他3碟同在另外兩樁之一上面才行。每份H3圖中都有2個節(jié)點對應(yīng)此種情況（分別表示另外兩樁之一上有全部剩余碟子），從任一H3圖出發(fā)分別有一條邊通往其他兩個H3圖（代表碟4移動）。因此各H3圖被兩兩分組并聯(lián)通。同理，當(dāng)n為整數(shù)時，Hn+1圖中包含3個Hn圖。

2012年7月，在克拉科夫（Krakow）的歐洲數(shù)學(xué)大會（European Congress of Mathematics）上，欣茨在介紹他的書《The Tower of Hanoi — Myths and Maths》（漢諾塔——神話和數(shù)學(xué)）

如果已經(jīng)掌握了解決漢諾塔游戲的方法，那么增加碟子數(shù)并不會相應(yīng)加大游戲難度。但若規(guī)定：游戲開始和結(jié)束時，并非所有碟子都以塔式疊于同一根樁上，那么事情就復(fù)雜了?！按藭r游戲變得相當(dāng)困難，”欣茨說?！靶睦韺W(xué)家在測試中使用了這種變體游戲，但他們對其結(jié)構(gòu)理解不深。我們幫助其建立了這種圖表式的數(shù)學(xué)模型，使得可以用數(shù)學(xué)方法分析游戲結(jié)構(gòu)?！?/p>

比如，通過狀態(tài)轉(zhuǎn)移圖可以立即看出，無論怎樣規(guī)定起止條件，無論用多少碟子，總是可以找到游戲答案。因為很容易從遞歸結(jié)構(gòu)中推斷出每個Hn圖都是聯(lián)通的：任何兩個節(jié)點之間都有通路。

但是最小移動次數(shù)的最優(yōu)解怎樣求呢？一般的起止條件是所有碟子都在一個樁上，因此可以算出最小移動步數(shù)是 2n-1。這也是最糟的：任意起止條件下，最小移動步數(shù)至少是2^(n-1)?？梢杂脭?shù)學(xué)歸納法證明：首先證明該公式對于初值 n=1 成立，然后證明如果公式對n成立則必定對 n+1 也成立。（自己證明試試，或看看這個證明）plus.maths.org/content/optimal-solution

三角形連接

Triangle Connections

數(shù)學(xué)家發(fā)現(xiàn)，增加碟子的數(shù)量會引發(fā)一些有趣的問題。假設(shè)游戲中有無數(shù)個碟片，那么狀態(tài)轉(zhuǎn)移圖會是怎樣的？好吧，看看下面的圖片。

謝爾賓斯基三角形Sierpiński's triangle

這便是謝爾賓斯基三角形。通過另一種無限遞歸過程就能生成它。從一個（填滿的）等邊三角形開始，去掉其三條邊的中點的連線所圍的倒三角形（只移走該倒三角形的內(nèi)部而留下其三條邊）?，F(xiàn)在剩下了 3 個填滿的等邊三角形。同樣地，再從這 3 個三角形中逐一移除其各自的中心倒三角形，于是便剩下9個三角形。繼續(xù)進(jìn)行，總是從剩余的各個三角形中移除其中間倒三角形，不斷重復(fù)進(jìn)行。最終你會得到謝爾賓斯基三角形。

謝爾賓斯基三角形是最著名的分形之一。它是自相似的：任何一個三角形不管它有多小，如果放大其內(nèi)部，你看到的都和整張圖完全一樣。謝爾賓斯基三角形屬于一個介于相鄰維度之間的奇怪世界：它比光滑的一維曲線維度更高，但面積是零，所以也就不是二維對象。數(shù)學(xué)家們推廣了維度的概念，以抓住此類復(fù)雜事物的本質(zhì)。從廣義的維度概念來看，謝爾賓斯基三角形的維度是log3/log2≈1.585。

當(dāng)逐漸增加漢諾塔游戲中的碟子時，對應(yīng)的狀態(tài)轉(zhuǎn)換圖經(jīng)過適當(dāng)縮放，看起來就越來越像謝爾賓斯基三角形。當(dāng)n趨于無窮時，得到的圖形和謝爾賓斯基三角形的結(jié)構(gòu)是一樣的。

它與數(shù)學(xué)家喜歡的另一種三角形：帕斯卡三角形，有著同樣有趣的聯(lián)系。（我們不會在這里定義它，如果你還沒見過它，這里有個很好的解釋[1]）如果取帕斯卡三角形的前2^n行，并連接水平和對角相鄰的奇數(shù)，那么得到的圖和漢諾塔Hn圖結(jié)構(gòu)完全一樣。

[1] mathforum.org/dr.math/faq/faq.pascal.triangle.html

帕斯卡三角形的前八行中相鄰的奇數(shù)項相連

這種聯(lián)系不僅漂亮而且實用。在某個領(lǐng)域內(nèi)難以證明的結(jié)果，在其他領(lǐng)域內(nèi)或許易于證明，于是就可以進(jìn)行問題轉(zhuǎn)化。例如，假設(shè)你在謝爾賓斯基三角形中旅行，但是從未走出分形之外。那么兩點之間的平均距離是多少？沒有人能夠回答這個問題，直到欣茨用漢諾塔狀態(tài)轉(zhuǎn)移圖來計算它：結(jié)果是466/885（假設(shè)謝爾賓斯基三角形最外層的邊長是1）。

加樁

Adding Pegs

增加碟片的情況討論夠多了，增加一根樁會怎樣呢？游戲本身變得更容易了，因為有了更多空間來移動碟子。但這些圖表也失去了它們的整潔結(jié)構(gòu)?，F(xiàn)在有更多的碟子組合以讓你移動最大碟片——小的碟片不再需要被堆在一根樁上了。

這意味著，最大碟片在樁1的狀態(tài)圖，和最大碟片在樁2的狀態(tài)圖之間的連接邊不止1條，因此使得整體狀態(tài)圖更復(fù)雜。“4根樁的狀態(tài)轉(zhuǎn)移圖通常不再是平面結(jié)構(gòu)，”欣茨說?！斑@意味著，你不可能把它們畫在一張紙上而不讓邊交叉。這得要3個維度才行。我們還不能很好地理解這些圖表，因為它們緊密地交織在一起?！?/p>

欣茨和書的共同作者在一起。從左到右：Ciril Petr, Andreas M. Hinz, Sandi Klav?ar和Uros Milutinovi?

這種復(fù)雜性意味著看似簡單的問題可能難以解決。例如，沒人知道在正常起止條件下，最短解決方案有多長。有一些策略策略可以解決多樁難題，著名的弗瑞姆-斯圖爾特猜想（Frame-Stewart conjecture ）聲稱這些策略是最優(yōu)的。但是，盡管這個猜想已經(jīng)有70多年的歷史了，但這個問題還沒有解決。在計算機(jī)的幫助下，它的正確性已經(jīng)被證明在30個碟子之內(nèi)是正確的。

欣茨是一位數(shù)學(xué)物理學(xué)家，但他迷戀漢諾塔游戲純屬消遣。他說：“與圖論專家---他們是我在這本書的合著者---和心理學(xué)家之間的合作非常吸引人?！彼c心理學(xué)家一起制作的評估工具現(xiàn)在正在被使用，例如測試患有癡呆癥或中風(fēng)的人，看看大腦的哪些區(qū)域受到了損傷。

它不僅僅有用。“數(shù)學(xué)家伊恩?斯圖爾特（Ian Stewart）曾經(jīng)說過，人們對數(shù)學(xué)很感興趣，因為它很有趣，很漂亮，而且很有用?！毙来恼f?！暗蚁胙a(bǔ)充第4點：人們喜歡數(shù)學(xué)，因為它令人驚奇?！弊鳛橐粋€數(shù)學(xué)對象，漢諾塔游戲當(dāng)然符合所有這4點的要求。(完)