文章: plus.maths.org/content/tower-hanoi-where-maths-meets-psychology

譯者: 向海飛 校對: 向海飛

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

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

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

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

遊戲規劃 The Game Plan

觀察遊戲結構的最佳方法是繪製網絡或圖形，顯示所有可能的構圖和移動。假設用三張碟片和三根樁來玩這個遊戲。將碟1、碟2和碟3標上序號，其中碟1最小, 碟3最大。也為樁1,樁2和樁3打上標記。現在假設碟1和碟3在樁1上，碟2在樁3上。使用三元組（1,3,1）對這種情況進行編碼。

連接各狀態轉移節點

現在在紙上把每個三元組畫到圈內。如果單步移動碟片能夠從一個圈轉移到另一個圈，則將二者連起來。例如起始狀態（1,1,1）（所有碟片在樁1）連到了（2,1,1）（碟1在樁2，其他碟都在樁1）和（3,1,1）（碟1在樁3，其他碟都在樁1）上。總共有 3³=27種可能存在的狀態。它們構成如下狀態轉換圖：

漢諾塔遊戲的狀態轉移圖 H3

這張圖叫做漢諾塔遊戲狀態轉移圖，以H3表示。下標3表明遊戲中有3個碟子。

有了狀態轉換圖就很容易描述某人的遊戲過程。“心理學家熱衷於使用狀態轉移圖，因為可以用它畫出被試者的動作序列，”欣茨解釋道，“你能從中輕易看出他有沒有做出最優操作，或者，如果沒有，他在哪裡遇到問題，在哪裡長時間思考等。因此可以從個人或眾人的測試結果中掌握許多信息，假如你把眾人的些操作過程圖疊加到一起來看的話。”

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

4碟子漢諾塔遊戲的狀態轉移圖H4中包含3個H3圖

類似地，H5圖由3個H4圖構成，H6圖由3個H5圖構成，以此類推。這是由遊戲的遞歸特性決定的：如果忽略最大的碟子，n+1碟漢諾塔遊戲就變成了n碟漢諾塔遊戲。比如說在4碟漢諾塔遊戲中，最大的碟4在樁1，對餘下3張碟的任何合法操作，也同樣是忽略碟4後3碟漢諾塔遊戲中的一個合法操作。因此，如果看H4圖中碟4在樁1的狀態節點（這些狀態節點的標籤以1結尾），會看到一個H3圖。類似地，碟4在樁2時、碟4在樁3時，會分別看到各自對應的H3圖。

如何在這些狀態轉移圖上移動？若想移動碟4，必得其他3碟同在另外兩樁之一上面才行。每份H3圖中都有2個節點對應此種情況（分別表示另外兩樁之一上有全部剩餘碟子），從任一H3圖出發分別有一條邊通往其他兩個H3圖（代表碟4移動）。因此各H3圖被兩兩分組並聯通。同理，當n為整數時，Hn+1圖中包含3個Hn圖。

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

如果已經掌握瞭解決漢諾塔遊戲的方法，那麼增加碟子數並不會相應加大遊戲難度。但若規定：遊戲開始和結束時，並非所有碟子都以塔式疊於同一根樁上，那麼事情就複雜了。“此時遊戲變得相當困難，”欣茨說。“心理學家在測試中使用了這種變體遊戲，但他們對其結構理解不深。我們幫助其建立了這種圖表式的數學模型，使得可以用數學方法分析遊戲結構。”

比如，通過狀態轉移圖可以立即看出，無論怎樣規定起止條件，無論用多少碟子，總是可以找到遊戲答案。因為很容易從遞歸結構中推斷出每個Hn圖都是聯通的：任何兩個節點之間都有通路。

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

三角形連接 Triangle Connections

數學家發現，增加碟子的數量會引發一些有趣的問題。假設遊戲中有無數個碟片，那麼狀態轉移圖會是怎樣的？好吧，看看下面的圖片。

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

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

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

當逐漸增加漢諾塔遊戲中的碟子時，對應的狀態轉換圖經過適當縮放，看起來就越來越像謝爾賓斯基三角形。當n趨於無窮時，得到的圖形和謝爾賓斯基三角形的結構是一樣的。

它與數學家喜歡的另一種三角形：帕斯卡三角形，有著同樣有趣的聯繫。（我們不會在這裡定義它，如果你還沒見過它，這裡有個很好的解釋[1]）如果取帕斯卡三角形的前2^n行，並連接水平和對角相鄰的奇數，那麼得到的圖和漢諾塔Hn圖結構完全一樣。

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

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

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

加樁 Adding Pegs

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

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

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

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

欣茨是一位數學物理學家，但他迷戀漢諾塔遊戲純屬消遣。他說：“與圖論專家---他們是我在這本書的合著者---和心理學家之間的合作非常吸引人。”他與心理學家一起製作的評估工具現在正在被使用，例如測試患有痴呆症或中風的人，看看大腦的哪些區域受到了損傷。

它不僅僅有用。“數學家伊恩•斯圖爾特（Ian Stewart）曾經說過，人們對數學很感興趣，因為它很有趣，很漂亮，而且很有用。”欣茨說。“但我想補充第4點：人們喜歡數學，因為它令人驚奇。”作為一個數學對象，漢諾塔遊戲當然符合所有這4點的要求。(完)

閱讀更多 遇見數學 的文章

關鍵字: 心理學 漢諾塔 數學