Creative Approach 有什麼不同 (2) – 談談數學歸納法

之前我曾談過Udi Manber 寫作的演算法書籍 Introduction to Algorithms: Creative Approach花了一整章介紹數學歸納法,作者設計這本書的思路,是很值得思索和品味的。

歸納還是演繹

首先我們要搞清楚,數學歸納法,不是哲學上所講的歸納推理( inductive reasoning) ,反而比較接近哲學領域所講的演繹 (deduction)推理。所謂的歸納推理,是基於對特定目標觀察的結果,把「性質」或「關係」類推至類型,或者是基於對反覆現象的觀察,所推理出來的規律或公式。歸納推理的結論只是有較大的機率為真,但不代表一定為真

而演繹推理則是從已知事實為前提,必然得出的結論,如果前提為真,則結論必然為真。數學歸納法是基於一組已知的前提,推演出一個必然為真的結論,所以這個證明方法的精神是 deductive reasosing ,不是 inductive reasoning。

數學歸納法的基本敘述

Udi Manber 在他的裡第二章末,參考文獻與進階讀物一節裡提到,數學歸納法是由 Francesco Maurolico 所發展出來的,事實上,數學歸納法的基礎可以上溯至更早的希臘時代的歐幾里德Euclid),維基百科可以找到數學歸納法的歷史介紹,簡明扼要但資料豐富,有意者可自行深入研究。

最常見的數學歸納法敘述,是說一個關於自然數的命題 P,當這個命題符合以下兩個條件時,則這個命題對自然數恆真:

  • P(0) 成立 (有的情況是講P(1))
  • 當 P(n) 成立,則 P(n+1) 也成立

或者我們用英文的敘述(對於看不慣中文翻譯的人來說,用符號和英文反而更親切,不是嗎?):

  • The basis: P(0) is true.
  • The inductive step: If p(n) holds, then P( n + 1) holds too.

換句話說,當上面兩個條件成立,P(n) is true for all natual numbers 。

用矛盾法(contradiction)證明數學歸納法的正確性

從高中到大學,我們學習數學歸納法,都是被動的背誦數學歸納法的證明手法,鮮少在課堂上探討歸數學納法可以證明命題敘述對在自然數這個集合裡一定是正確的。其實我們可以用矛盾(又稱歸謬證明法Proof by contradiction)法來驗證證明這個方法的正確性。

我們的前提如下:

  1. P(0)
  2. For all n ≥ 0, P(n) ⇒ P(n + 1)

然後我們現在要證明對所有大於零的自然數,P 這個命題恆真,就是
For all m ≥ 0, P(m) is true ……………………………….. (3)

接下來就是證明的核心,假設 (3)是錯誤的,那我們一定可以找到一個最小的數 m’ 使得 P(m’) 不成立,我們現在要證明這個假設是有衝突的,所以 (3) 不可能是錯的,(3)必須是真的。

首先, m’ 不可能是 0,因為前提 (1) 已經告訴我們 P(0)必須成立,所以這個 m’ 如果存在,一定大於 0。當我們找到這個所謂的 m’ ,我們知道前提 P(m’ – 1) 是成立的,因為 m’ 是最小的令命題 P 不成立的數字,但是前提(2)告訴我們,P(m’-1+1)=P(m) 這個敘述必必須為真。這和我們的假設是衝突的,所以不可能找到令 (3)不成立的數字m’。換言之,P(x)這個敘述對於所有自然數都成立,我們已經證明數學歸納法在前提確立的狀況下,是打不破的。

皮阿諾公設(Peano’s Axioms)

用今日數學的術語來說,數學歸納法就是皮阿諾公設(Peano’s Axioms)中的第五公設。所謂公設(或稱公理 axiom),就是在某些學門中不需要證明,但卻必須被承認的敘述或命題,有的書籍翻譯為公理。公理是一門學問的基礎,這門學科的所有理論、定理,必然可以由這些最基礎的公理推演而來,如果基礎不被承認,這門學科也就無從存在,公設的重要性由此可見。

義大利數學家 Giuseppe Peano (皮阿諾) 在 1889 年以拉丁文寫作一本小冊子 Arithmetices principia, nova methodo exposita ( The principles of arithmetic, presented by a new method ),這本書將自然數的性質抽象化得到一組公設。希望藉著這組公設,透過邏輯的推演,可以演繹出自然數的所有性質。 皮阿諾把每一個自然數的下一個稱為這數的「後繼者」(successor),用後繼者的說法, 這組皮阿諾公設可以寫成下面的形式(括弧裡是用符號的寫法,其中 n+ 表示自然數 n 的後繼者):

  1. 0是一個自然數。
  2. 若x是一個自然數,則另有一個自然數X'(緊隨X之後)。X’稱為X的直接繼數。
  3. 0不是任何數的後繼者
  4. 對任何自然數X與y,若X’=Y’,則X=Y。
  5. [歸納原理]若P是一個性質(Property),並且(i)0其有性質P;(ii)若任何自然數X具有性質P:則X’具有性質P,則所有自然數其有性質P。

數學歸納法不同的面貌

標準的數學歸納法證明,可以分為三個部分

  • The Base Case (in the domino analogy, this shows the first domino will fall)
  • The Induction Hypothesis (in the domino analogy, we assume that a particular domino will fall)
  • The Inductive Step (in the domino analogy, we prove that the domino we assume will fall will cause the next domino to fall)

只要遵循以上三部曲的建構方式,通常都能順利找到證明的思路,發展出 induction step 來證明所欲證明的標的。事實上,在作數學歸納法證明時,有許多技巧上的變化,比如說:

☆(1)先證明n=1,n=2時命題成立;

(2)假設n=k-1,n=k-2的時候命題成立

(3)證明在此情形下,n=k時命題也成立。

或者像這樣

☆(1)先證明n=1到m時命題成立;

(2)假設n=k的時候命題成立

(3)證明在此情形下,n=k+m時命題也成立。

數學歸納法,並不是只有一個面貌,經過長久的發展,數學歸納法已經發展出許多的變異模式,適用於不同的場合與目的,甚至有些數學家開發出將數學歸納法延伸至自然數以外領域的模型出來。以最精簡的符號來表達,我們一般常見的數學歸納法的變化形式可能包括以下幾種情形:

Standard Formulation

  • The basis: P(0) is true.
  • Induction hypothesis: assume P(n=m) holds.
  • The inductive step: If p(m) holds, show that P( m + 1) holds too.

Strong Induction

  • The basis: P(0) is true.
  • Induction hypothesis: assume for all n <= m, P(n) holds.
  • The inductive step: If p(n) holds, show that P( n + 1) holds too.

Reverse Induction

  • P(M) is true for some M
  • If P(n=k+1) holds, show that the property holds for n = k.

依照上述證明方式,我們得到結論: The property holds for all values n <= M

Transfinite Induction

Transfinite induction 一般而言是應用在 well-ordered set 上,通常只有真正念數學的人,才會關心這個咚咚吧? 根據 PlanetMath 的說明, Transfinite induction 的定義如下:

證明的陷阱,切記!切記!

前輩數學家華羅庚曾經講過一個故事 :一位買主買了一隻公雞回家。第一天,餵公雞一把米;第二天,又餵公雞一把米;第三天,還是餵公雞一把米。連續十天,每天都餵給公雞一把米。公雞就這十天的經驗,下了一個結論說:每天一定有一把米可吃。但是就在得出這個結論後不久,家裏來了一位客人,公雞就被宰殺成為盤中飧請客人了(這個故事可以在昌爸工作坊找到)。

有人建議把數學歸納法想像成骨牌效應(falling dominos ),一張骨牌倒下來,下一張骨牌接著倒下去,就這麼一張一張倒下去,用遠不會停。問題就在這邊,我們必須確認一張骨牌一定接著一張,才能確保數學歸納法的正確與適用。

換句話說, P(n) 成立,不代表 P(n+1) 一定成立,千萬不要認為理所當然,我們的任務是確認 P(n) ⇒ P(n + 1),不是默認 P(n) ⇒ P(n + 1)。

為什麼寫

原本只是打算在複習演算法時,順手記錄看書時的想法,但是在唸時,看到第二章,在回顧自己學習數學歸納法的過程時,冒出許多想法,所以就順手把找到的東西發展出一篇完整的東西。

Creative Approach 有什麼不同

為了準備資格考,在圖書館借了 Introduction to Algorithms: A Creative Approach 的中譯本(沒法子,找不到原版),實驗室的同學翻了翻,覺得這本書一點兒都不出奇,和別的演算法書籍沒有什麼不同,尤其和這些年被奉為聖經的 CLRS 演算法大磚頭相比,相形下有點單薄了。

的確,中文書名建構式演算法,實在不怎麼響亮,而且在建構式數學已經被污名化的今日,這樣的書名實在是讓人很難不看低這本書。

但是在我的眼裡,這本書不同的地方可多著咧。

首先,作者的來頭不一般,這本書的作者 Udi Manber 可不是蛋頭型的學者,他不僅在學術上的成就卓著,是演算法界大師級的學者,他還是一個活力十足的行動派。 Udi Manber 是agrep 和 GLIMPSE 的(共同)作者。agrep 是他和吳昇(他的著作)老師在九零年代初共同發展的,他們共同寫作的 Agrep – A Fast Approximate Pattern-Matching Tool,依照 Google Scholar 的搜尋結果,被引用次數達到 143 次,以一篇年紀這麼大的文章,被引用次數達到這個程度,是很不容易的。簡單說,他是搜尋引擎相關技術演算法的先驅者之一。

離開學界,進入產業界,他也是一條過江猛龍。1998 年,他加入雅虎,職位是 chief scientist ;2002 年,他加入亞瑪遜網路書店,擔任 chief algorithms officer,這個 CAO 職位,還引起 IT 媒體界一陣騷動,紛紛評論這個職位對於企業的意義和影響(impact)。在 Amazon 期間,他還是搜尋引擎 A9 的 CEO。後來,毫不令人意外地,他在 2006 年加入了 Google ,擔任工程部門的副總裁(之一),當我在媒體上看到 Google Snatches A9 Chief 的新聞標題, 心裡不由得覺得又是這樣,有股無可名狀的淡淡異樣感受在心頭走過。

其次,另外一個特別的地方是,這本書用了整整一章的篇幅,介紹數學歸納法(mathematical induction)。數學歸納法是一個非常重要的證明技法,這個方法衝破思考的侷限,將思考的限制從有限,推展到無限的領域。思考範圍的突破,是數學歸納法很重要的貢獻,而且掌握數學歸納法的證明形式與技法,對於掌握邏輯推演的技巧,也有不小的貢獻。

很可惜,國內除了數學科系之外,鮮少在課堂上針對數學歸納法,作深刻透徹的說明,所以許多學習數學歸納法的學生,很難真正理解這個證明技法在學習上的意義,更別談從這裡發展出「作」證明題的一套適合個人的思路。

所以,這本書的寫作思路,和其它的演算法書籍,的確是不同的。接下來,我想應該花點時間整理數學歸納法了吧(待續stay tuned …)。

Hat Problem: why you should care ?

這是一篇舊聞了,是紐約時報 2001年4月10日,科學版上的一篇文章。但是剛在 Digg 上發現,看到有超過七百人次「頂」這篇 Why Mathematicians Now Care About Their Hat Color,連上紐約時報仔細拜讀,才真正認識了這個不簡單的策略遊戲。

遊戲規則

數學界一般認為猜帽子顏色的遊戲是由 Dr. Todd Ebert (DBLP)在1998年,他的博士論文中提出來的。

這是一個團隊參與的遊戲,參與人數從三人到更多人都可以,遊戲的勝負是以整個團隊的結果來決定結果。在遊戲過程中,參與者每人頭上都戴著紅色藍色的帽子,參與者只能看到別人的帽子顏色,但是不能看到自己的帽子顏色。每個參與者必須猜測自己頭上帽子的顏色,參與者之間不能有任何形式的溝通,只能觀察別人的帽子,然後猜測自己的頭頂是什麼顏色。

猜測的選項有三個,紅色、藍色或棄權(pass),如果覺得自己無法下決定,可以選擇 PASS。當參與團隊中每個有作出猜測的人(棄權的人就不管了)的猜測結果都正確,則這個團體可以獲得獎金。

依照遊戲規則,在觀察和猜測時,遊戲玩家間不得有任何溝通行為,但是在遊戲開始前,這個團隊可以作「策略」討論,遊戲開始後,所有成員根據大家事先協商的策略,來決定自己的行動(猜測或放棄)。這個遊戲的核心就是 :有沒有一個「贏的策略」?這個策略的成功機率有多高?

三個人的策略

以最簡單的三人情況來說,三個人都是紅色或藍色的機率各是八分之一,所以有四分之三(扣掉全藍及全紅的情況)的機會,是兩個人的帽子顏色相同,第三個人是另外一種顏色。因此有個可能比較容易贏的策略,每個參與者觀察另外兩個人的帽子顏色,如果這兩個人的帽子顏色不同,則猜測者選擇放棄;如果另兩個人的帽子顏色相同,猜測者猜自己的帽子是另外一種顏色。

雖然當三個人的帽子顏色相同時,以上辦法是絕對沒有機會贏的, 不過這是參與者數目為三人的最佳解決方案(optimal solution),以下是從網路上找到的證明。

Each guess has a 50-50 chance of being correct. This means that when we consider possible outcomes there must be an equal number of correct and incorrect guesses. Notice that in each win there is a single correct guess and in each loss there are three incorrect guesses. Winning one more game requires one more correct guess (a total of 7), but now we have only 1 possible game to lose and 7 incorrect guesses to make. There are only 3 players so this is impossible.

By Brody Dylan Johnson at Saint Louis University


更多人的狀況

網路上有許多人改編這個遊戲,改變帽子的顏色,參與的人數,從電視遊戲大獎賽到囚犯問答,但是問題的本質仍然相同,這些不同的描述方式,可以在網路上找到(例如 New York Times, ABC News, Die Ziet)。

三個人的遊戲,只是這個遊戲的基本版。超過三個人的狀況,讓事情變得複雜許多。有人認為這是典型的 Game Theory 問題,也有人思索這個問題的 social 版本,但是也有人認為這一個數學模式(Model)的問題,有數學家「認真」的去找答案,真的在編碼理論(Coding Theory)中找到解決問題的方向。

Dr. Hendrik Lenstra, a professor of mathematics at Berkeley, and Dr. Gadiel Seroussi, director of information theory research at HP Labs, have developed a new type of covering code to define an even better strategy for large numbers of players.

以上的解法,使用編碼理論中的 Hamming Code,來描述問題,這種作法在參與人數是2的次方數減一(例如 3, 7, 或 15 )的時候幾乎無懈可擊,但是其他的狀況就不是那麼容易處理。而且數學家還無法證明這個解決方案是否為最佳解(optimal)。還有一點值得一提,這個問題的重要關鍵在於「團隊」,只有整個團隊都正確,才能贏得這個遊戲。所以,除了數學模式之外,我們還有多少種可能的觀點?這是更有趣的問題。

Googling the Hat Problem

在寫這篇短文的時候,使用 Google 作了一個簡單的小研究。發現在網路上除了英文的資料外,竟然有許多簡體中文的討論群組或網站,提到這個帽子問題,倒是繁體中文的資料少之有少。這個觀察結果,可能比起帽子問題,還要有趣,或者說更讓人頭痛

或許我們可以提出幾個猜測,大陸網站的內容,屬與原創製作的比例是令人存疑的,所以這麼多的帽子資料,究竟是否能代表他們熱愛這類益智問題,是令人存疑的。而繁體中文資料的貧乏,則是我們這個環境的網路文化的縮影,究竟這是什麼意思,我不知道。

不管這個觀察結果,是否隱喻我們不喜歡動腦筋。不過,我很好奇老外為何喜歡以帽子作為思考或比喻的輔助,數學家擔心帽子的顏色,搞企管的人則用帽子教人如何作個好主管(No,這一點也不好笑,如果你還沒有聽說過用帽子顏色表示思考類型的故事,那你一定太年輕)。

唯一的結論是,台灣人比較(不)愛戴帽子(不,我沒有談政治)…