這是一個稱為河内塔的精巧智力題。它由法國數學家愛德華·盧卡斯于1883年發明：

“

給定一個由8個圓盤組成的塔，這些圓盤按照大小遞減的方式套在三根樁柱中的一根上。

我們的目的是要将整個塔移動到另一根樁柱上，每次隻能移動一個圓盤，且較大的圓盤在移動過程中不能放置在較小的圓盤上面。

問要完成這項任務移動多少次才是必須且足夠的？

”

盧卡斯給這個玩具賦予了一個羅曼蒂克的傳說，說的是一個大得多的婆羅賀摩塔（Tower of Brahma），它由64個純金的圓盤堆放在三座鑽石做成的方尖塔上．他說，上帝一開始把這些金圓盤放到了第一座方尖塔上，并命令一組牧師按照上面的規則把它們移動到第三座方尖塔上。據說牧師們夜以繼日地工作，當他們完成任務時，那座塔就将坍塌，世界也将毀滅。

這個智力題有解，隻是并非顯而易見，不過隻要稍加思考（或者此前看見過這個問題）就能使我們确信的确如此。現在問題來了：我們能做到的最好的解法是什麼？也就是說，要完成這項任務移動多少次才是必須且足夠的？

解決這樣問題的最好方法是對它稍加推廣．婆羅賀摩塔有64個圓盤，河内塔有8個圓盤，讓我們來考慮一下，如果有n個圓盤将會怎樣？

這樣推廣的一個好處是，我們可以大大簡化問題。事實上，先研究小的情形是大有裨益的。移動隻有一兩個圓盤的塔十分容易。再通過少量的嘗試就能看出如何移動有3個圓盤的塔。

求解問題的下一步是引入适當的記号：命名并求解。我們稱Tn是根據盧卡斯的規則将n個圓盤從一根樁柱移動到另一根樁柱所需要的最少移動次數．那麼，T1顯然是1，而T2=3。

考慮所有情形中最小的情形還可以輕松得到另一條信息，即顯然有T0=0，因為一個有n=0個圓盤的塔根本無需做任何挪動！聰明的數學家們不會羞于考慮小問題，因為當極端情形（即便它們是平凡的情形）弄得明明白白時，一般的形式就容易理解了。

現在讓我們改變一下視角，來考慮大的情形：怎樣才能移動一個大的塔呢？移動3個圓盤的試驗表明，獲勝的思路是将上面兩個圓盤移動到中間的樁柱上，然後移動第三個圓盤，接着再把其餘兩個放到它上面。這就為移動n個圓盤提供了一條線索：首先把n-1個小的圓盤移動到一個不同的樁柱上（需要Tn-1次移動），然後移動最大的圓盤（需要一次移動），最後再把那n -1個小的圓盤移回到最大圓盤的上面（這需要另外的Tn-1次移動）．這樣，至多需要2Tn-1 1次移動就能移動n（n ＞ 0）個圓盤了：

這個公式用的是符号“≤”，而不是“ = ”，因為我們的構造僅僅證明了2Tn-1 1次移動就足夠了，而沒有證明2Tn-1 1次移動是必需的。智者或許能想到一條捷徑。

還有更好的方法嗎？實際上沒有。我們遲早必須移動最大的那個圓盤．當我們這樣做的時候，那n-1個小的圓盤必須已經在某根樁柱上，而這至少需要Tn-1次移動才能把它們放置到那兒。如果我們不太精明，則移動最大的圓盤可能會多于一次。但是在最後一次移動最大的那個圓盤之後，我們必須把那n-1個小的圓盤（它們必須仍然在同一根樁柱上）移回到最大圓盤的上面，這也需要Tn-1次移動．從而

把這兩個不等式與n = 0時的平凡解結合在一起就得到

（注意，這些公式與已知的值T1= 1以及T2=3相一緻．關于小的情形的經驗不僅能幫助我們發現一般的公式，而且還提供了一種便利的核查方法，看看我們是否犯下愚蠢的錯誤。在以後涉及更為複雜的操作策略時，這樣的核查尤為重要．）

像式（1.1）這樣的一組等式稱為遞歸式（recurrence，也稱為遞歸關系或者遞推關系）。它給出一個邊界值，以及一個用前面的值給出一般值的方程。有時我們也把單獨的一般性方程稱為遞歸式，盡管從技術上來說它還需要一個邊界值來補足。

我們可以用遞歸式對任何n計算Tn。然而，當n很大時，并沒有人真願意用遞歸式進行計算，因為太耗時了。遞歸式隻給出了間接、局部的信息。得出遞歸式的解我們會很愉悅。這就是說，對于Tn ，我們希望給出一個既漂亮又簡潔的“封閉形式”，它使我們可以對其進行快捷計算，即便對很大的n 亦然．有了一個封閉形式，我們才能真正理解Tn 究竟是什麼．

那麼怎樣來求解一個遞歸式呢？一種方法是猜出正确的解，然後證明我們的猜想是正确的。猜測解的最好方法是（再次）研究小的情形。我們就這樣連續計算T3= 2*3 1 = 7，T4=2*7 1 = 15， T5= 2*15 1=31， T6=2*31 1=63。啊哈！這看起來肯定像是有

至少這對n≤6是成立的。

數學歸納法（mathematical induction）是證明某個命題對所有滿足n≥n0 的整數n都成立的一般方法．首先我們在n取最小值n0時證明該命題，這一步驟稱為基礎（basis）；然後對n＞n0 ，假設該命題對n0與n-1之間（包含它們在内）的所有值都已經被證明，再證明該命題對n 成立，這一步驟稱為歸納（induction）。這樣一種證明方法僅用有限步就得到無限多個結果。

遞歸式可以用數學歸納法完美地确立起來．例如在我們的情形中，式（1.2）很容易由式（1.1）推出：其基礎是顯然的，因為T0=2º-1=0．而如果我們假設當n被n-1取代時式（1.2）成立，則對n＞ 0用歸納法就得出

從而式（1.2）對n 也成立。好的！我們對Tn 的探求就此成功結束。

牧師的任務自然還沒有完成，他們仍在負責任地移動圓盤，而且還會繼續一段時間，因為對n =64有2的64次方-1次移動（大約1.8*10的19次方次）。即便是按照每微秒移動一次這個不可能實現的速度，也需要5000多個世紀來移動婆羅賀摩塔。而盧卡斯的智力問題更切合實際，它需要2的8次方-1=255次移動，快手大概四分鐘就能完成。

河内塔的遞歸式是在各種應用中出現的諸多問題的一個典範。在尋求像Tn 這樣有意義的量的封閉形式的表達式時，我們經過了如下三個階段。

(1) 研究小的情形．這有助于我們洞察該問題，而且對第二和第三階段有所幫助。

(2) 對有意義的量求出數學表達式并給出證明。對河内塔，這就是遞歸式（1.1），它允許我們對任何n 計算Tn （假設我們有這樣的意向）。

(3) 對數學表達式求出封閉形式并予以證明。對河内塔，這就是遞歸解（1.2）。

第三階段是我們要由始至終集中探讨的。實際上，我們将頻繁跳過第一和第二階段，因為我們以給定一個數學表達式作為出發點。即便如此，我們仍然會深入到各個子問題中，尋求它們的解将會貫穿所有這三個階段。

我們對于河内塔的分析引導出了正确的答案，然而它要求“歸納的跳躍”，依賴于我們對答案的幸運猜測。我們的一個主要目的就是說明不具備超人洞察力的人如何求解遞歸式。例如，我們将會看到，在遞歸式（1.1）中方程的兩邊加上1可以使其變得更簡單

現在如果令Un=Tn 1 ，那麼就有

不必是天才，就能發現這個遞歸式的解正是Un=2ⁿ，從而有Tn=2ⁿ-1。即便是一台計算機也能發現這個結論。

用一把比薩刀直直地切n刀，可以得到多少塊比薩餅？或者說得更有學術味兒點：平面上n條直線所界定的區域的最大個數L_n是多少？這個問題于1826年被一位瑞士數學家斯坦納首先解決。

我們再次從研究小的情形開始，記住，首先研究所有情形中之最小者。沒有直線的平面有1個區域，有一條直線的平面有2個區域，有兩條直線的平面有4個區域（每條直線都在兩個方向無限延伸）：

我們一定會想到有Ln=2ⁿ，當然！增加一條新的直線直接使區域的個數加倍。遺憾的是，這是錯誤的．如果第n條直線能把每個已有區域分為兩個，那麼就能加倍。它肯定能把一個已有區域至多分成兩個，這是因為每一個已有區域都是凸的（一條直線可以把一個凸區域分成至多兩個新區域，這些新的區域也将是凸的）．但是當增加第三條直線（圖中的那條粗線）時，我們很快就會發現，不論怎樣放置前面兩條直線，它隻能至多分裂3個已有的區域：

從而L₃=4 3=7是我們能做到的最好結果。

略加思考之後，我們給出适當的推廣。第n（n ＞ 0）條直線使得區域的個數增加k 個，當且僅當它對k 個已有區域進行了分裂；而它對k 個已有區域進行分裂，當且僅當它在k-1個不同的地方與前面那些直線相交。兩條直線至多相交于一點，因而這條新的直線與那n - 1條已有直線至多相交于n - 1個不同的點，故必定有k≤n 。我們就證明了上界

此外，用歸納法容易證明這個公式中的等号可以達到。我們徑直這樣來放置第n 條直線，使得它不與其他直線中的任何一條平行（從而它與它們全都相交），且它不經過任何已經存在的交點（從而它與它們全都在不同的點相交）。于是該遞歸式即為

核查一下就發現，已知的L₁、L₂和L₃的值在這裡完全正确，所以我們接受這一結果。

現在需要一個封閉形式的解。我們可以再次來玩猜測遊戲，但是1,2,4,7,11,16,…看起來并不熟悉，故而我們另辟蹊徑。我們常常可以通過将它從頭到尾一直“展開”或者“解開”來弄清楚遞歸式，如下：

換句話說，Ln比前n個正整數的和Sn大1。

量Sn不時地冒出來，故而值得對較小的值做出一張表。這樣，我們下次看到它們時，或許會更容易辨認出這些數：

這些值也稱三角形數，因為Sn是一個有n行的三角形陣列中保齡球瓶的個數。例如，通常的四行陣列

有S4=10個瓶子。

為計算Sn，我們可以利用據說是高斯在1786年就想出來的一個技巧，那時他隻有9歲（阿基米德也曾在他關于螺旋線的經典著作的命題10和命題11中用到過）：

隻要把Sn和它的反向書寫相加，就能使得右邊n列的每一列中的諸數之和都等于n 1．簡化即得

好的，我們就有解答

作為專家，我們或許很滿意于這個推導，并認為它是一個證明，盡管在做展開和合并時我們付出了一點點努力。但是學數學的學生應該能夠适應更嚴格的标準，故而最好用歸納法構造出一個嚴格的證明。歸納法的關鍵步驟是

現在對于封閉形式（1.6）就不再有疑問了。

我們談到了“封閉形式”而沒有具體說明它的含義。通常，它的含義是極其明晰的像（1.1）和（1.4）這樣的遞歸式不是封閉形式的，它們用其自身來表示一個量；但是像（1.2）和（1.6）這樣的解是封閉形式的。像1 2 ...... n 這樣的和不是封閉形式——它們用“…”企圖蒙混過關，然而像n（n 1）/2這樣的表達式則是封閉形式的。我們可以給出一個粗略的定義：如果可以利用至多固定次數（其次數與n無關）的“人人熟知的”标準運算來計算量f (n)的表達式，那麼這個表達式是封閉形式的。例如，2ⁿ -1和n（n 1）/2都是封閉形式，因為它們僅僅顯式地包含了加法、減法、乘法、除法和幂指運算。

簡單封閉形式的總數是有限的，且存在沒有簡單封閉形式的遞歸式。當這樣的遞歸式顯現出重要性時（由于它們反複出現），我們就把新的運算添加到整套運算之中，這可以大大擴展用“簡單的”封閉形式求解的問題的範圍。例如，前n個整數的乘積n!已經被證明是如此重要，故而現在我們都把它視為一種基本運算。于是公式n!就是封閉形式，盡管與它等價的1* 2*......* n并非是封閉形式。

現在，我們簡要談談平面上直線問題的一個變形：假設我們用折線代替直線，每一條折線包含一個“鋸齒”。平面上由n條這樣折線所界定的區域的最大個數Zn是多少？我們或許期待Zn大約是Ln的兩倍，或者也可能是它的三倍．我們看到：

從這些小的情形出發并稍加思考，我們意識到，除了這“兩條”直線不經過它們的交點延伸出去而使得區域相融合之外，一條折線與兩條直線相似：

區域2、3和4對于兩條直線來說它們是不同的區域，但在一條折線的情形下是單獨的一個區域，于是我們失掉了兩個區域．然而，如果放置得當——鋸齒點必須放在它與其他直線的交點“之外”——那就是我們失去的全部，也就是說，對每條折線我們僅僅損失兩個區域．從而

比較封閉形式（1.6）和（1.7），我們發現對于大的n 有

所以用折線所能得到的區域是用直線所能得到的區域的大約四倍。

——

是不是不知不覺看完了？這樣學數學是不是很有效率，以後再也不會看見數學公式就頭疼了。

——本文内容節選自《具體數學：計算機科學基礎》

下面把這本書分享給大家，由當今頂級數學家和計算機科學家聯合著作。

書中主要講解了計算機科學中用到的數學知識及技巧，教人如何把實際問題一步步演化為數學模型，然後通過計算機解決它，特别着墨于算法分析方面。

本書成形于斯坦福大學的同名課程講義，該課自1970年以來每年都會開設。每年大約有50名學生選學這門課，有本科生，主要是研究生。

具體數學究竟是什麼呢？我們在書中能獲得什麼？

它融合了連續數學和離散數學。更具體地說，它是利用一組求解問題的技術對數學公式進行有控制的操作。理解了本書的内容之後，你所需要的就是一顆冷靜的頭腦、一大張紙以及較為工整的書寫，以便對看上去令人恐怖的和式進行計算，求解複雜的遞歸關系，以及發現數據中隐藏的精妙規律。你會對代數技巧得心應手，從而常常會發現，得到精确的結果比求出僅在一定意義下成立的近似解更為容易。

具體數學的英文Concrete取自連續（CONtinuous）和離散（disCRETE）兩個單詞，具體數學是通向抽象數學的橋梁

這本書要探讨的主題包括和式、遞歸式、初等數論、二項式系數、生成函數、離散概率以及漸近方法。其重點是強調處理技術，而不是存在性定理或者組合推理，目的是使每一位讀者熟悉離散性運算（如最大整數函數以及有限求和），就好像每一位學習微積分的學生都熟悉連續性運算一樣（如絕對值函數以及不定積分）。

“略過看似基礎内容的高水平讀者，比略過看似複雜内容的較低水平讀者，可能錯失更多的東西。”——G. 波利亞[297]

注意，這些主題與當今大學本科中的“離散數學”課程的内容截然不同。因此，這門課程需要一個不同的名稱，而“具體數學”可謂恰如其分。

這本書還包含了500多道習題，分成如下六大類。

• 熱身題：這是每一位讀者在第一次閱讀本書時就應完成的習題基礎題：這些習題揭示出了，通過自己的推導而不是他人的推導來學習最好作業題：是加深理解當前章節内容的問題考試題：一般同時涉及兩章以上的内容，可作為家庭測試題（不作為課堂上的限時考試）附加題：它們超出了學習本書的學生的平均水平，以耐人尋味的方式擴展了書中的知識研究題：或許非人力所能解，但是這裡給出的題似乎值得一試身手（不限時）

書的最後，附錄A中給出了所有習題的答案，常常還附有相關的解題思路。附錄C中，作者還嘗試說明每道習題的出處，因為一個富有教益的問題常常融會了大量的創造性思想或者運氣。很遺憾，數學家們有個不好的傳統：借用了習題，而不表示感謝。我們相信，相反的做法，例如棋類書籍和雜志中的做法（通常都會指出最初棋類問題的名字、時間和地點），要遠勝于此。

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部