統計是科幻？

在編輯 anobii 書庫上的資料時，發現有人把「統計，讓數字說話!」這本書分類為「科幻與奇幻」，嘿嘿，這又是看圖不說話的一個好例子。

[Video] Nature by Numbers

我想大家應該都同意數學是科學之母，其實數學無處不在，在我們身邊的大自然裡，在我們伸手可及的生活裡。一個老外 Cristóbal Vila 製作了一個短片，把自然界裡可見的數字和幾何現象，做了很棒的呈現：

（影片的背景可參考這個網站）

Bourbaki Archives

從 Ars Mathematica 知道 Bourbaki Archive 的消息，一時頗為感慨，“誤入塵網中”的我，早以把大學時代唸的東西還給天地了，但是聽到這個消息還是很高興。

Via Peter Woit I see that there is a project to put the archives of Bourbaki online. These are the internal manuscripts that the group generated while writing their famous series of books.

Bourbabi 是誰？1950年前後，一群法國數學家決定以集合論為基礎，用純演繹的方式，重寫整套數學，他們用共同的筆名 N. Bourbaki發表著作。他們的著作從最抽象的數學體系談起，然後才逐漸待殊化，這 種由廣入狹的次序，把數學組織得既簡潔又亮麗，所以數學家們對此頗為欣賞。這群數學家每年夏天，聚集在一個避暑勝地，每天上午討論怎樣寫書，下午開數學講論會 (colloquium)。 在上午的寫書討論中，必須一致通過才算定稿，完成的著作共有數十冊。

在學術界大受好評之後，這群數學家表示想為中小學寫數學教科書，當時的法國政府表示非常歡迎，美國數學界受了 Bourbaki 這一舉動刺激（其實更多人認為是受了俄國的 Sputnik 衛星事件的刺激），由 Edward G. Begle 所領導的 School Mathematics Study Group（ SMSG 中小學數學研究組) 也開發了一套數學教科書，這就是所謂的新數學。但是 Bourbaki 的中小學教科書計劃並沒有如預期獲得成功，而邯鄲學步的新數學，更被美國教育界視為一場災難。事實上,數學家所能欣賞的和企業界所需要的數學有一段距離，和中小學生所能研讀的有更大的一段距離，這場失敗不算意外。

雖然中小學教科書的嘗試不若他們在學術界的嘗試那麼成功，不過他們的主張對學術界的影響是深遠的，他們寫書的方式，更是數學界學子代代相傳的傳奇。

(以上說明改寫自王九逵教授發表於科學月刊第三十一卷第三期的集合論與數學教育 )

小數點後多少位才夠

前些日子，家裡的長官因為指導學生科展的緣故，需要計算根號二、根號三的數值到小數點後三千位，在網路上找了兩天，始終找不到合適的資料。幾經思索，她發現找到資料的最佳方法，就是把任務交代下去，於是這個任務就落到我頭上，並且責令鄙人於兩日內限時完成任務。

每個對程式設計有興趣有野心的初學者，都曾經想過寫作自己的程式庫，任意位數四則運算無疑是一個不錯的練手標的，甫接到任務指令時，原也興致勃勃，覺得正是好好活動筋骨的機會，大不了自己寫個模組，再到網上找個 Newton's Method(牛頓法) 的算法就可交差。

仔細研究維基百科裡關於 Arbitrary-precision arithmetic 的說明，發現事情可沒有那麼容易，僅僅是要把任意位數乘法做出來，連規劃帶測試除錯，恐怕就不是一個晚上可以完工的。依照維基百科的說明，高明的算法，甚至要用到快速傅立葉轉換咧，這豈是一個週末項目（weekend project）的格局。所以，上策還是做個善用工具的人吧！

就在同一份資料裡，介紹了一些好心人撰寫並公開使用權的程式庫，我一一查訪，發現一個 Python 的模組mpmath , 完全符合需求。安裝 mpmath 非常容易，下載解壓縮之後，只要在檔案所在的目錄下，執行 sudo python setup.py install 就成了；需要引用這個模組的函數前，記得先載入 （from mpmath import *）這個模組，就算完成一切準備動作。

真正的重頭戲也簡單得不得了，閱讀文件之後發現，只要在進行運算前宣告本次運算的位數精度，比如說要計算三千位（3000 digits）的數字，就執行 mp.dps = 3000。mpmath 只問你要計算多少位元（digit），不管你要把小數點放在哪裡， dps 宣告數值是多少，mpmath 就給你那麼長的數字。

求根號二的過程簡單到出乎意料，先載入 mpmath （from mpmath import *）, 宣告需要的精度（mp.dps=100），宣告一個多精度的浮點數（a=mpf(2.0)），然後直接用 ** 運算子求出答案（開根號是二分之一次方），用經過最佳化的 sqrt() 函數也可以達成相同目標。運算過程看下面截圖就一目了然：


我另外寫了一個 Newton's Method 的副程式，驗算的結果發現，不管求到小數點後多少位（我最多測到5000位），a**0.5 的答案和牛頓法求出來的結果是完全一樣的，而且用函式庫內建的函式速度更快。結論很簡單：在這個年代，要做個善用工具的人，才能快速完成任務。

[Video] Having sex is like doing my math homework

 

Lyrics:

whats a pirate minus the ship? just a creative homeless guy,
and an anteater plus a large hungry mutant ant? an ironic way to die
and whats domain, domain, range (xxy) a kid with too much in his pants
and two balls minus one, six titles at the tour de france.

split a decision with long division,
take the circumference of your circumcision
live like your data and when you're all "set"
put it all together and whatever you get.

is new math...

whats a bag of chips divided by five, thats a nike worker's meal
and santa clause mutliplied by "i" well i guess that makes him real,
and the square root of the NBA is Africa in a box,
how do u trace a scatter plot? give the pencil to michael j fox.

take the approximate moral proportion of the probable problem of a pro-life abortion
live like your data, and when youre all "set"
put it all together and whatever you get...

is new math.

and if you made a factor tree of the factors that caused my girl to leave me youd have a tree...
full of asian porn.
C-A-L-C-U-LATOR (see you later) mathetmatical minds make industrial smog.
and whats the opposite of lnx, duraflame the unnatural log.

support the farmers with a pro-tractor,
link kennedy and lincoln with a common factor (fact, or)
live like ur data...blah blah

word problems

if theres a fat guy in a pastry shop with a twenty dollar bill and he's ready to buy,
in order to predict his volume change you need to know the value of pi (pie)
and theres a metal train that a mile long and at the very back end a lightning bolt struck her,
how long til it reaches adn kills the driver, provided that he's a good conductor,
and if ten percent of men are gay and twenty percent of men are chinese, what are the odds that a men chosen at random spends his freetime and mealtime while on his knees
and if kim is half as old as bobby who is two years older then twelve year old tori,
for how many more 30 day months will their threesomes be considered statutory rape

cause having sex is like quadratic expansion if it cant be split then its time to stop,
and having sex is like doing fractions, its improper for the larger one to be on top,
and having sex is like math homework, i do it best when i'm alone in my bed.
and squarin numbers are just like women, if they're under thirteen just do them in your head....

 

Share this post :

Mathemagician !!

「這麼高位數的計算，我是沒有問題啦，可惜，有些計算機（calculator）沒法子計算這麼多位數字！」，舞台上表演者面帶笑容的示範如何計算三位數字、四位數字，甚至五位數字的平方(square)。

結合數學與魔術，把數字與計算當作表演的道具，舞台上的 Arthur Benjamin 是一位在大學教書的數學系教授，他稱呼自己是 mathematician 和 magician 的結合： Mathemagician。

這樣具有舞台魅力的老師，上課應該會很有趣吧，不知道在他教授的組合學（Combinatorics）課堂裡，他的學生會不會總是鼓譟著要求他在課堂上露兩手？

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 來證明所欲證明的標的。事實上，在作數學歸納法證明時，有許多技巧上的變化，比如說：

☆（１）先證明ｎ＝１，ｎ＝２時命題成立；

　（２）假設ｎ＝ｋ－１，ｎ＝ｋ－２的時候命題成立

　（３）證明在此情形下，ｎ＝ｋ時命題也成立。

或者像這樣

☆（１）先證明ｎ＝１到ｍ時命題成立；

　（２）假設ｎ＝ｋ的時候命題成立

　（３）證明在此情形下，ｎ＝ｋ＋ｍ時命題也成立。

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

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)。

為什麼寫

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

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，這一點也不好笑，如果你還沒有聽說過用帽子顏色表示思考類型的故事，那你一定太年輕）。

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