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

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

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

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

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

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

游戲規(guī)劃

The Game Plan

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

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

現(xiàn)在在紙上把每個(gè)三元組畫到圈內(nèi)。如果單步移動(dòng)碟片能夠從一個(gè)圈轉(zhuǎn)移到另一個(gè)圈，則將二者連起來。例如起始狀態(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個(gè)碟子。

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

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

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

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

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

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

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

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

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

三角形連接

Triangle Connections

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

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

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

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

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

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

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

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

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

加樁

Adding Pegs

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

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

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

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

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

它不僅僅有用?！皵?shù)學(xué)家伊恩?斯圖爾特（Ian Stewart）曾經(jīng)說過，人們對(duì)數(shù)學(xué)很感興趣，因?yàn)樗苡腥ぃ芷?，而且很有用?！毙来恼f?！暗蚁胙a(bǔ)充第4點(diǎn)：人們喜歡數(shù)學(xué)，因?yàn)樗钊梭@奇?！弊鳛橐粋€(gè)數(shù)學(xué)對(duì)象，漢諾塔游戲當(dāng)然符合所有這4點(diǎn)的要求。(完)