樹洞 Tree Hole 2.0

Reading, Caffeine, Alcohol, Peanuts, Cynicism…

高斯如何計算 1+2+…..+n — January 22, 2018

高斯如何計算 1+2+…..+n

幾乎所有的教材,在講等差級數的時候,都會提到數學家高斯(Carl Friedrich Gauss)十歲時在課堂上解出老師交待的算術難題「1+2+3+ … +99+100=?」的故事,故事版本長短簡繁不一,圍繞這個故事的話題不斷,有心人還製作影片,益發熱鬧絢麗。

在我看過的材料裡,以在YouTube上找到的 Reason for Math DVD 的片段最為精彩。不少高斯加法故事的版本用 a_1 + a_{100}, a_2 + a_{99}, a_{3} + a_{98}.... 的配對策略來講述這個故事,但是這樣的說明失之過簡,遇到要累加奇數項目的時候,這個策略不能奏效,如果我們要計算 1 + 2 + 3 …. + 99 怎麼辦。

這難不倒偉大的 homo sapiens , 有人用 1+2+3…+n 建造一個三角形,接著把兩個三角形疊成一個正方形,然後用正方形面積公式求出答案,這是更完善的策略。Better Explained 網站有一篇文章解釋了解決累加問題思路一步步推進的過程,非常精彩。

 

影片裡,解決這個問題的分析和洞見講述,從影片的三分鐘開始漸入高潮,Better Explained 文章裡面提到的思路解釋,大約從五分多鐘開始用精緻的動畫說明,很有意思。

如果不想再看(聽)一次故事,直接從三分鐘這裡看起。當然,從頭開始欣賞這個影片,也是很棒的體驗。

Advertisements
數學和摺紙 — December 12, 2017

數學和摺紙

今晨在找 Ted 演講影片的時候,意外發現這個,完全符合領導的要求,而且演講者口齒清晰又幽默,堪稱上品。

 

數學歸納法其實是演繹法 — October 24, 2017

數學歸納法其實是演繹法

三年前在多看平臺上看電子書费马大定理:一个困惑了世间智者358年的谜,書中有一段話是「 Wiles 採用稱為歸納法的一般方法作為他證明的基礎」,我當下就在書裡加上註解,反應給出版社,數學歸納法是演繹,不是歸納。後來整句話被修掉,完全不提 Wiles 的方式是基於歸納還是演繹。現在在多看平臺看這本電子書的讀者,還可以看到我加的註,但是本文已經和截圖的內容不同了。

-

為什麼特別注意到數學歸納法,因為 Udi Manber 有本演算法課本 Introduction to Algorithms: Creative Approach,花了很長的篇幅講數學歸納法。很久以前準備演算法考試的時候,從圖書館借了這本書參考。看到計算機科學家,以不同於數學家的敘述方式講數學歸納法,覺得很有意思,後來那本書只有那一章是真正認真讀完的。

在準備考試期間,順便查了包括維基百科在內的許多網路資料,寫了讀書筆記《Creative Approach 有什麼不同 (2) – 談談數學歸納法

所謂的歸納推理,是基於對特定目標觀察的結果,把「性質」或「關係」類推至類型,或者是基於對反覆現象的觀察,所推理出來的規律或公式。歸納推理的結論只是有較大的機率為真,但不代表一定為真。

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

維基百科關於數學歸納法的中文頁面,講的更是斬釘截鐵,但是這一刀似乎切的太猛:

数学归纳法并非不严谨的归纳推理法,它属于完全严谨的演绎推理法。事實上,所有數學證明都是演繹法。

-

今早在圖書館找資料,看到曹亮吉教授寫的推廣書籍《阿草的葫蘆 — 文化活動中的數學 》,書裡講到數學家不是只在乎演繹,同樣也會使用歸納思考方式;同樣地,其他自然科學領域也不是只歸納不演繹。但是他同樣直接了當的說:數學歸納法,是個如假包換演繹法

專業數學家鐵口直斷,period。

-

不知道給「假設 n 成立,證 n + 1 也成立」這種證明方式取名 mathematical induction 的是那位先賢,如假包換的標題黨啊!

為什麼是 37% — October 16, 2017

為什麼是 37%

Hannah Fry 的《愛情數學》第七章寫到如何應用「最優停止理論(Optimal Stopping)」,決定什麼該「定下來」,確定結婚的對象。如果你一生中打算談 n 次戀愛,或者你打算從25歲到35歲之間盡可能認識更多的人,到了35歲再決定你的他(她),怎麼做可以讓你找到最佳拍檔的機率最高。。

-

這個題目有許多不同版本,比如說 Algorithms to Live By: The Computer Science of Human Decisions 就問如果你搬到一個新城市,需要找地方住,找到你最合意的公寓的找房策略是什麼?或者你想找一個新祕書,你要面試多少人才找到合適的祕書呢(這問題有個名字叫「祕書問題」)。

If you want the best odds of getting the best apartment, spend 37% of your apartment hunt (eleven days, if you’ve given yourself a month for the search) noncommittally exploring options. Leave the checkbook at home; you’re just calibrating. But after that point, be prepared to immediately commit—deposit and all—to the very first place you see that beats whatever you’ve already seen. This is not merely an intuitively satisfying compromise between looking and leaping. It is the provably optimal solution.

-

那麼這個問題的最佳策略是什麼呢?從數學觀點,確實有最佳策略,就是大名鼎鼎的37%法則。Hannah Fry 告訴我們,如果你一生要談10次戀愛,找到最佳對象的機率發生在拒絕4個人之後;如果你有無數個伴侶,拒絕前37%的人,成功率最高。如果以時間軸來考量,在你遊戲花叢時間的前37%,千萬不要定下來,但是過了 37% 的時間,遇到第一個比前 37% 時間遇到的「可能對象」都好的先生或女士,就是他(她)啦。

37 這個數字,怎麼算出來的?Hannah Fry 在書裡講的很簡略,告訴我們最優停止理論給了我們一個極為簡潔的公式,用這個公式算出來的數字就是 37%。書末的參考文獻指向一篇1997年出版的論文《Searching for the Next Best Mate1》,這篇論文的摘要(abstract)也只是直接說出 37 這個數字,沒有解釋來由。這篇論文的訂價是 24.95 歐元(Oops),直接放棄購買或下載的打算。

…In this paper, we analyze the third approach of mate choice as applicant screening and show through simulation analyses that a traditional optimal solution to this problem-the 37% rude-can be beaten along several dimensions by a class of simple “satisficing” algorithms we call the Take the Next Best mate choice rules. Thus, human mate search behavior should not necessarily be compared to the lofty optimal ideal, but instead may be more usefully studied through the development and analysis of possible “fast and frugal” mental mechanisms.

透過谷歌,在 plus.math.org 找到兩篇文章《Strategic dating: The 37% rule》和《Kissing the frog: A mathematician’s guide to mating》解釋答案為什麼是 37%,看完推導,只能說一個字:維基百科的解釋看起來不一樣,其實精神和 plus.math.org 提出來的解法是一致的。翻譯成數學語言,就是訂出你的「停止」策略,然後計算成功的機率,若你的約會對象有 N 個選擇,當你審視過 r 個約會對象後,找到你的最佳拍檔的機率可以寫成下面的算式:

-

簡而言之,這公式其實就是求 1/x 的積分,當 N 接近無窮大,最後我們得到

-

P 的最佳值在 x=1/e 的時候出現,大約等於 0.3679


  1. Todd P.M. (1997) Searching for the Next Best Mate. In: Conte R., Hegselmann R., Terna P. (eds) Simulating Social Phenomena. Lecture Notes in Economics and Mathematical Systems, vol 456. Springer, Berlin, Heidelberg 
德瑞克方程式與費米方法 — October 11, 2017

德瑞克方程式與費米方法

1961 年,天文學家 Frank Drake,提出一個問題,銀河系裡有多少願意和我們聯繫的文明?他不僅提出問題,還提供了一個答案,建議大家使用一個估算方式。我們稱這個計算方法叫德瑞克方程式(Drake Equation),方程式的計算很簡單,沒有用到高深的數學技巧,就是簡單的乘法而已:

-

本公式的每個參數解釋是這樣的:

  • N = 銀河系統中可以通訊的文明數目
  • R* = 每年銀河系產生的星體數目(平均)
  • fp = 恆星系統擁有行星環繞的比例
  • ne = 行星系統裡有多少「宜居」的行星
  • fl = 「宜居」行星發展出生命的比例
  • fi = 擁有生命的星球,能發展出智慧文明的比例
  • fc = 擁有智慧文明,且發展出對外通訊技術的比例
  • L = 該對外通訊科技延續的時間(the length of time over which such civilizations release detectable signals)

把算式右邊的數值乘起來,就是銀河系中可以聯絡的文明數目的估計值。當時德瑞克估計可能願意和我們聯絡的文明數約有 10 個,時至今日,最新的估計值已經降低到 2.3 了。

上週提到 Peter Backus 在 2010 年用德瑞克方程式的精神,估算他的「可能伴侶」的數字,Hannah Fry 在她的書 Mathematics of Love 中說 Peter Backus 估算他追女機率的計算方式就是費米方法,為什麼 Hannah Fry 這麼說?費米方法是什麼?

關於 Enrico Fermi1 的傳說很多,費米方法是他衆多傳說之一,傳說是這樣的,據說他在芝加哥大學的課堂上,問他的學生「芝加哥市裡有多少鋼琴調音師?」,當他的學生們抓耳撓腮之際,他對學生說明了估算的訣竅,很快學生就掌握了這個方法的精髓。

在美國亞馬遜網站評價非常高的 Superforecasting 這本書用淺顯易懂的文字解釋費米方法的精神,這裡引用大陸中信出版社出的簡體中文版翻譯本《超預測》的文字:

-

為了計算芝加哥鋼琴調音師的人數,我們必須知道什麼呢?唔,鋼琴調音師的數量取決於給鋼琴調音的工作量和僱用一位調音師可以做的工作。因此,如果我知道以下4個數據,這個問題就迎刃而解:

(1)芝加哥的鋼琴數量;

(2)每年給鋼琴調音的次數;

(3)給鋼琴調音需要的時間;

(4)鋼琴調音師每年平均工作時間。

有了前三個數據,我可以算出在芝加哥鋼琴調音的總工作量。接著,用這個數值除以最後一個數據。就這樣,我可以非常自信地說出芝加哥有多少位鋼琴調音師。

我們很容易就看出,這個邏輯和上面德瑞克方程式的計算方式完全一樣,德瑞克方式就是費米方法論的一個具體範例。回到 Peter Backus 的伴侶數目問題,彼得先生在小論文《為什麼我沒有女朋友》裡的計算方式是這樣的,

  1. 住在我附近的女性有多少?(倫敦:400萬)
  2. 多少人有可能年齡上適合?(20%:80萬)
  3. 多少人有可能是單身?(50%:40萬)
  4. 多少人有可能擁有大學文憑?(26%:104,000)
  5. 多少人有可能有魅力?(5%:5,200)
  6. 多少人有可能覺得我有魅力?(5%:260)
  7. 多少人有可能和我合得來?(10%:26)

像剝洋蔥一樣,一層層剝下來,他得到 26 這個答案。在英國境內找到這 26 個可能對象,難不難?比發現外星文明還難嗎?

答案在每個人心中,至於彼得自己的答案,從他 2013 年就結婚的事實,我們可以「感受」到彼得的答案是什麼!


  1. Enrico Fermi 是1938年諾貝爾物理獎得主