數學資料庫手記

Bertrand's Postulate

2009-11-13T12:37:00.000+08:00

Bertrand's Postulate says that for any integer n > 1 there is a prime number p such that n < p < 2n. Here's a link to a beautiful and elementary proof of this fact: http://mathforum.org/library/drmath/view/51527.html.

A beautiful solution

2009-11-12T14:40:00.003+08:00

Suppose you want to prove that the sum of 1/(m^2 + n^2) diverges as m,n ranges over all positive integers. What do you do?

Here's a very beautiful solution, from one of my students in an undergraduate complex analysis class:

Every prime of the form 4k+1 is expressible as the sum of two squares. Hence the previous sum is bounded below by the sum of 1/p, where p ranges over all primes that are congruent to 1 mod 4. The latter sum diverges. Q.E.D.

Daily Life Application of Number Theory

2009-11-04T03:00:00.002+08:00

A message from UC Berkeley (exact situation unknown):

Warning: Due to a known bug, the default Linux document viewer evince prints N*N copies of a PDF file when N copies requested. As a workaround, use Adobe Reader acroread for printing multiple copies of PDF documents, or use the fact that every natural number is a sum of at most four squares.

數學講座

2009-10-23T17:32:00.002+08:00

日期：2009 年 11 月 20 日（星期五）
時間：下午 6 時 30 分至 8 時 30 分
地點：香港城市大學教學樓四樓 LT18 演講廳
講者：曾淵滄博士
講題：投資全攻略

簡介：
本講座旨在從科學角度與重點介紹甚麼是管理科學，亦討論管理科學如何在投資及財務應用方面所扮演之角色。本講座亦專為有志參加快張開辦的統計學課程而設。

有關其他詳情及報名方法，可瀏覽這裡。
（如果無法載入，可複製網址 http://hkage.org.hk/b5/new/Students/ma/0910003/poster.pdf）

死後的paper？

2009-10-19T00:00:00.004+08:00

前兩天聽了一個關於random graph的seminar，回到辦公室就拿起Janson, Luczak和Rucinski的Random Graphs查一些terms的意思。隨手一揭，見到Erdős, Suen和Winkler在1995年一起出了一份paper。當時我想如果這是Paul Erdős的話，他不是已經離世很久了嗎？但查一查wiki，才知道他是在1996年離世的。

但另外查一查DBLP，竟發現Paul Erdős直到2006年為止仍然有聯名的paper發。究竟是因為其他的作者在十多年前和他討論得出成果，所以將Paul Erdős的名字寫在作者欄上，還是這個世界上有另一個Paul Erdos呢？煩請有識之士指點迷津。

AM-GM 不等式的幾個證明（六）

2009-10-14T11:27:00.006+08:00

看見 Kahoo 給了 AM-GM 不等式這麼多個精彩的證明，不禁想再來一個用微分和凸函数 (convex functions) 的。

這裏我們只需留意對任意實數 x 和 a，

這不等式可以用很多不同的方法來證明，其中要想清楚當中的概念的，比較好的方法，是留意是一凸函數，故其導數是遞增的，用中值定理即可推出上述不等式。（也可以不失一般性假設，從而用一元微積分或的 Taylor 展開求得此不等式。）

有了這不等式以後，對正數，

這裏 a 可以是任何實數。把上列的不等式平均起來，得到

------(1)

取，則

從而 AM-GM 不等式得證。事實上不等式 (1) 的右邊是一關於 a 的函數，左邊則跟 a 無關，所以我們會取的 a 使得 (1) 的右邊達至最大值，而這正是我們上面這樣取 a 的原因。

這證明的一個好處，是我們可以用同樣的辦法證明以下這個 AM-GM 不等式的推廣：對任意，和任意正數使得，有

從上面的討論可知，其實 AM-GM 不等式是函數的 convexity 的反映。對任何的凸函數 f，我們都有 Jensen 不等式，詳見 wikipedia。

AM-GM 不等式的幾個證明（五）

2009-10-11T16:42:00.005+08:00

作為本系列的完結篇，我們看看 AM-GM 不等式的一個不用數學歸納法的證明。本證明主要用到排序不等式，此不等式指出若而，那麼當我們把這些 a_i 和 b_i「配對相乘再相加」時，有以下不等式：

這裡 f(1)、f(2)、…、f(n) 是 1, 2, ..., n 的一個任意排列，而以上不等式中的三行分別叫「逆序和」、「亂序和」和「順序和」。不等式看起來有點複雜，但其實背後意念很簡單：假設一批學生分 n 組比賽（人數分別是 a₁、a₂、…、a_n），而每組均選擇 n 種隊服中的一種（價錢分別是 b₁、b₂、…、b_n），那麼最省錢的自然是越多人的組別使用越便宜的隊服（即逆序和），最花錢的自然是越多人的組別使用越貴的隊服（即順序和）。利用排序不等式，不難證明對任意正數 y₁、y₂、…、y_n 皆有

（不失一般性設，並設和，再使用「亂序和 ≧ 逆序和」即可）。

現在我們用以上結果來證明 AM-GM 不等式。不妨設 x₁x₂…x_n = 1（這可通過代換得到），並設

即可得

從而證明了 AM-GM 不等式。

順帶一提，排序不等式的等號成立當且僅當或，大家不妨試試由此導出 AM-GM 不等式的等號成立當且僅當。

Gil Kalai's Seminar

2009-10-06T10:09:00.003+08:00

上週四Hebrew University of Jerusalem和Yale University教授Gil Kalai來了Courant Institute講seminar。大家可能對這個名字有點印象，因為我曾在一篇手記 "Test Your Intuition"中提及他的網誌"Combinatorics and More"。

平時同一時段的"theory seminar"，有多於15人已屬罕見，但今次Prof. Kalai來講seminar卻吸引了38人來。平時有空位剩的房間一下子全院滿座，還有幾個人坐地下聽。

Prof. Kalai講了三個猜想，其中一個比較易懂和有趣，可以在這裏講講。

設。我們可以進行一個"Fourier Transform"，即寫成，當中（這與一般Fourier Series中的的角色相同。）假設，若每一個均獨立地有機會率 t 改變值（即由-1變成1或由1變成-1），若的機會很高，我們就可說 f 是noise stable。

甚麼情況下 f 是noise stable呢？Prof. Kalai舉了一個有趣的例子，就是說美國總統選舉，若Obama得票的數目是單數他就當選，否則McCain當選，這個選舉就很"noisy"，對吧？由此例子見到，noise stable的函數，它的Fourier expansion中，當S是一個較大的集合時，的值就應該很小。

數學講座

2009-10-05T15:39:00.003+08:00

日期：2009 年 11 月 6 日（星期五）
時間：下午 6 時 30 分至 8 時
地點：九龍塘教育服務中心西座四樓演講廳
講者：蕭文強教授
講題：難「分」難「解」的數學
簡介：

日常生活中不時碰到分配問題，例如工作時分配人手、得到獎賞後分配獎品、各選區分配議席、眾人分配美食等等。易乎？難乎？單單懂得除數是否就足夠呢？在這個講座讓我們一起探索一些有趣的例子。

有關其他詳情及報名方法，可瀏覽這裡。
（如果無法載入，可複製網址 http://hkage.org.hk/b5/new/Students/ma/091106mkma/poster_b5.pdf）

AM-GM 不等式的幾個證明（四）

2009-10-01T09:28:00.001+08:00

上回看過 AM-GM 不等式的一個「普通數學歸納法」證明。這裡我們再看三個類似的證明。一如之前，設 x_i 為正數，並已知 AM-GM 不等式對 n=1 和 n=2 成立。

假設 n=k 時 AM-GM 不等式成立，並考慮 n=k+1 時的情況。如果，則 AM-GM 不等式顯然成立，否則不妨設各數中 x₁ 最小，x_k+1 最大，那麼這 k+1 個數的平均（不論是算術平均或是幾何平均）均大於 x₁ 而小於 x_k+1。以下用三個方法證明 n=k+1 的情況。

方法一

設。由歸納假設可知

，

從而，其中最後一個不等式成立是因為

。

方法二

設，則，故此

方法三

除了用數學歸納法外，AM-GM 不等式還可以用其他方法來證明，我們下回再看。

AM-GM 不等式的幾個證明（三）

2009-09-27T11:08:00.003+08:00

在早前的文章中：

AM-GM 不等式的幾個證明（一）
AM-GM 不等式的幾個證明（二）

我們看過 AM-GM 不等式在 n=2 的情況時的一個「無言證明」，和一般情況的一個「反向歸納法」證明。這裡我們看一個使用一般數學歸納法的證明。

設、，其中所有 x_i 皆是正數。正如上回所說，我們有 A₁ = G₁ 和 A₂ ≧ G₂。假設 A_k ≧ G_k。以下證明 A_k+1 ≧ G_k+1：我們有

而

因此 AM-GM 不等式對所有正整數 n 皆成立。使用數學歸納法證明 AM-GM 不等式的技巧還有很多，甚至有些證明可以不必使用數學歸納法，我們下回再看。

洗幾次牌先「夠」？

2009-09-22T08:00:00.005+08:00

一幅啤牌52隻，發展出很多趣的遊戲出來，包括橋牌、「鋤大D」、廿一點等等。每盤遊戲結束，指定動作就是洗牌。相信你一定見到有人隨便「cut兩cut」就算，但亦有人洗一次牌洗成分鐘，有點掃興的味道。

究竟，洗牌要洗幾多次先「夠」？

要回答這條問題前，首先要定義甚麼是「夠」。從概率學上，「夠」可以定義為每一個可能性出現的機會都（大約）相等。1992年Bayer和Diaconis研究了以下一種洗牌方法（以下一段不只針對啤牌；一幅牌可以有n隻）：

首先一幅牌排成一疊，然後每隻牌順序抽出，再擲骰仔決定放左面還是右面：若是單數放左面，若是雙數放右面。然後將左面的牌疊在右面的牌的上方。

這種洗牌方法叫inverse Gilbert-Shannon-Reeds shuffle (inverse GSR shuffle)。Bayer和Diaconis証明了若進行大約次inverse GSR shuffle，副牌就大約「洗勻」了。換言之，對啤牌來說，需要洗牌大約 8.55 次。

當然，現實中用inverse GSR shuffle未免太慢了（擲52次骰仔，每次1秒，再加其餘動作，最少也要1分鐘吧）。但大家想想，若inverse GSR shuffle如兩段前所述，那麼non-inverse GSR shuffle會是怎樣的？大家又是否覺得似曾相識呢？

-----

Below is for more advanced math students. Only people who have some background on Markov Chain theory should continue reading:

For those who know about Markov Chain theory, you may easily see that it is a Markov process. As every element in the symmetric group has an inverse, it is easy to observe that the eigenvector with eigenvalue 1 is indeed the "uniform distribution vector".

The period of the corresponding stochastic matrix must be 1, since there is non-zero probability that the inverse GSR shuffle remains the deck unchanged. Hence by Perron-Frobenius theorem, all other eigenvectors must be with eigenvalue of modulus strictly less than 1. So after shuffling sufficiently many times, no matter how the intial distribution is, it must converge to the unifrom distribution.

In other words, you may say converging to uniform distribution is an immediate result of Perron-Frobenius theorem. Bayer and Diaconis were analyzing how fast the convergence is.

巧合？造馬？

2009-09-17T18:59:00.003+08:00

最近，保加利亞的六合彩（1 至 42 號，每期攪珠抽出六個號碼）連續兩期開出相同的號碼（例如可以參考這篇報導），惹來造馬疑雲。

報導指出，數學家估計兩期相同中獎號碼的機會率是 420 萬分之 1，那是不正確的，因為 C(42,6) = 5245786，因此機會率應是約 520 萬分之 1 才對。（每星期開彩兩次的話，平均每 50000 年這才會發生一次。但如果我們考慮不同國家的彩票的話，出現這情況的頻率會大大提高，例如如果有 1000 個同樣的彩票的話，那麼平均每 50 年便會有一次這樣的事件了。）

有人認為事件乃造馬，其中一個理據是第一次開那六個號碼時沒有人中獎，第二次時卻有 18 人中。這個理據顯然沒有說服力，因為總可能有些人投注時喜歡「照抄」上期的六個號碼，所以有多人中獎並不出奇。（同樣，如果開出「1、2、3、4、5、6」的話，中獎的人必定很多，所以投注這些「特別組合」是不智的。）

那到底事件是巧合還是造馬呢？這個還得等待當地政府的特別調查結果，不過也可以客觀分析一下：整個攪珠過程是電視直播的，現場亦有獨立委員監察，要造馬成功的話，要買通所有監察委員，再要騙過電視觀眾，難度並不低。此外，如果事件真的是造馬的話，那麼造馬的人也未免太傻了：竟然選擇重再之前一期的號碼，不但令事件惹來世界注目，而且正如之前所說，這樣的號碼組合肯定會令中獎人數激增，從而分薄派彩。如果有能力造馬的話，為何不選擇六個平平無奇的號碼，那不但神不知鬼不覺，而且派彩也更加豐厚。

當然，巧合和造馬之間也有一些其他可能性的，例如會否是攪珠機的構造導致某些號碼特別容易被攪出？這個還是留待統計學家、機械學家、工程學家、……用他們的方法驗證吧。

拍賣方法的藝術

2009-09-16T23:00:00.005+08:00

「潛水」了兩個月，事關七月、八月初都在科大寫paper，忙到不得了，而八月中下旬就要準備出國和參加一連串的farewell。對了，我現在身處New York，正在New York University的Courant Institute讀PhD in Computer Science。

雖然讀的博士銜頭表面上轉了科，但做的事還是跟數學脫不了勾；這也証明了在科學的學術界上數學幾乎是無處不在的。最近在看一本上，講algorithmic game theory。我見到一個結果很漂亮的，想在這裏和大家分享一下。

有以下這個情況：有一幅名畫要拍賣，而有n個買家。設買家B_i心中看這幅畫的價值是p_i。若買家最後買不到畫，他最終的「滿足度」為0；若他以價格p買了這幅畫，他的「滿足度」為p_i-p。而買家們的目標都是令滿足度盡量大。所以，買家B_i是絕不會以高於p_i的價錢買畫的，因為他不買的話滿足度為0，但他以高於p_i的價錢買畫，滿足度就變了負數。拍賣以「投暗標」方式進行，即每名買家只可向拍賣行提一次價，而這個價是保密的——其他買家是不知道的。

決定名畫誰屬的第一種方法就是大家所想的：價高者得。這個方法叫first price auction。假設買家們都不知道其他買家心中看名畫的價值，那麼他們應如何出價呢？他們就要估其他畫家看這幅畫的價值，對不對？若看這幅畫價值最高的幾個買家都錯誤地低估其他買家的叫價，名畫賣出的價錢恐怕就要大大降低。

有沒有其他方法令買家投標價就是他們各自的p_i呢？有！這個方法叫second price auction。方法是：各買家投暗標後，投標價最高者以投標第二高價購得名畫。即是說，若四名買家投標價分別是14M、12M、8M和6M，第一名買家將以12M價格購得名畫。

這時，大家要仔細想一想。買家的確是會以各自的p_i投標的；因為無論其他人投標價如何，若他們以低於p_i的價格投標，都不可能會有better benefit。以上一段的例子來說，第一名買家不論以14M或13M投標，他最後的滿足度都是14M-12M = 2M；但若他以11M投標，他們滿足度就是0。以低於p_i投標只會令滿足度有減少的風險。

現在回到first price auction。假設買家們還是不知道其他買家心中對名畫的價格，但現時卻有多一點的資料：買家心中價格滿足一個probability distribution。那麼，買家們應該怎樣投標呢？我們可以見到一個很漂亮與second price auction呼應的答案：假設自己心中價格是最高，然後以second highest bidding的預期值（expected value）投標。舉例說，若那個probability distribution是說買家心中價格在6M至18M之間平均分佈，那麼心中價格是14M的買家就應以(6+14)M/2 = 10M的價格投標。

等巴士之謎

2009-09-12T23:03:00.003+08:00

假設某路線的巴士每 20 分鐘一班。如果乘客到達車站的時間是隨機的，而巴士又永遠準時到站的話，那麼乘客的平均候車時間是 10 分鐘（當然，最短的候車時間是 0 分鐘，最長則是 20 分鐘）。如果班次不準確但車子的數目不變的話（例如有些班次早到數分鐘，有些遲到數分鐘），那麼對乘客的平均候車時間將有何影響？

看下去之前，不妨停下來先想想。

由於車子的數目不變，那麼有些班次早到而有些遲到的話，表面上平均候車時間似乎不變（車子遲來的話，有些人久等了，但有些卻因而趕上該車子，而車子早來的情況也類似），其實不然。

考慮一下這個頗為極端的情況：單數的班次（第 1 班、第 3 班、……）總是遲到 10 分鐘，而雙數的班次則總是早到 10 分鐘。那麼，20 分鐘一班的巴士會變成每 40 分鐘一次過來兩班，但對乘客來說這跟每 40 分鐘一班沒有分別 -- 平均候車時間變成了 20 分鐘！

再考慮另一個情況：單數的班次總是遲到 3 分鐘，而雙數的班次則總是早到 3 分鐘。那麼從某班單數的班次開出到下一個單數班次到站的 40 分鐘可視為一個循環，如果我們假設這 40 分鐘期間每分鐘有一名乘客到達車站的話，那麼他們的候車時間分別為 14、13、…、1、0、25、24、…、1、0 分鐘，不難發現平均候車時間超過 10 分鐘（可以不經計算而看出此事嗎？）。

一般來說，如果巴士並非全部準時到達的話，那麼平均候車時間便會超過 10 分鐘。因為時間是連續的，要嚴謹證明這事有點麻煩，故這裡從略。不過懂得積分（integration）的讀者可以一試，事實上以上結果是排序不等式（rearrangement inequality）的一個「連續版（continuous version）」呢。

AM-GM 不等式的幾個證明（二）

2009-09-06T17:09:00.005+08:00

上回給了 AM-GM 不等式的一個「無言證明」，但那只適用於 n=2 的情況。這次我們看一個完整的證明，方法是用「反向歸納法（backward induction）」。在 AM-GM 不等式的眾多證明中，這可說是最常見的一個。或者換個角度說會較為適合：在反向歸納法的眾多例子中，AM-GM 不等式是最常見的一個。

這裡先概述一下證明的方法。當 n=1 時，AM-GM 不等式顯然成立。當 n=2 時，我們也很容易證明 AM-GM 不等式成立，這是因為

而後者顯然正確。利用以上已證明的 n=2 結果（即兩個正數的算術平均大於或等於它們的幾何平均），我們有

從而 AM-GM 不等式對於 n=4 也成立（注意這裡兩次用到 n=2 時的結果）。由於以上不等式對任意四個正數 x₁、x₂、x₃、x₄ 成立，故特別地當時也成立，從而有

這樣我們便從 n=4 的情況證明了 n=3 的情況！重覆以上的步驟，我們可以從 n=4 的情況推導出 n=8 的情況，再反向推導出 n=7、n=6 和 n=5 的情況，如此類推。這就是反向歸納法背後的理念。有興趣細讀詳情的話，可以參閱數學資料庫這份《數學歸納法》筆記中的 Theorem 3.5 和 Example 3.5。

證明 AM-GM 不等式還有很多其他方法，下回繼續。

AM-GM 不等式的幾個證明（一）

2009-08-31T20:18:00.001+08:00

給定 n 個正數 x₁、x₂、…、x_n，它們的算術平均（arithmetic mean，簡稱 AM）是指它們之和除以 n，而它們的幾何平均（geometric mean，簡稱 GM）則指它們之積的 n 次方根，即

　和　。

AM-GM 不等式指出，n 個正數的算術平均必定大於或等於幾何平均，而且等號成立當且僅當該 n 個數皆相等。例如：2003、3、14 的算術平均約是 673.33，幾何平均約是 43.82。

本系列會探討 AM-GM 不等式的證明方法。今回先來一個「無言的證明（proof without words）」：

當然，以上證明只包括 n=2 的情況，純屬「欣賞指數高」之作。至於「實用指數高」的證明方法，我們下回再談。

MD Academic Seminar

2009-08-16T00:16:00.005+08:00

數學資料庫將於本月底舉行期待已久的 academic seminar！詳情如下：

日期：2009 年 8 月 30 日（星期日）
時間：下午 4 時 30 分至 5 時 30 分
地點：香港中文大學邵逸夫夫人樓（Lady Shaw Building）232 室（見註）
講者：楊葆霖先生（普林斯頓大學數學系博士研究生）

註：從港鐵大學站（中文大學出口）轉右，可乘坐中文大學校巴於第二個站（潤昌堂）下車，步行約兩分鐘即可抵達邵逸夫夫人樓。星期日的校巴於每小時 00、20、40 分在大學站開出，車程約 5 分鐘。

============================================================

講題：淺談拓撲－－沒有長度的幾何

簡介：長度和角度都是幾何中常見的概念。可是如果我們只想探討物件的大約形狀（例如宇宙有多少個「洞」），我們並不真的需要討論長度與角度。拓撲學正是數學中探討這種問題的一門重要學科。講座將深入淺出地介紹拓撲學裏一些重要的概念和例子，並會討論一些初中常見的幾何定理跟拓撲學的關係。

講座適合初中或以上學生。

Topic: A leisurely introduction to topology: geometry without lengths

Abstract: Length and angles are common concepts in geometry. However, if one is only interested in the rough shape of an object (like how many "holes" there are in our universe), then these concepts are actually irrelevant. Topology is the branch of mathematics that studies these questions. In the talk, we shall introduce some useful notions and interesting examples in topology, and discuss how some common theorems in elementary geometry relates to topology.

The talk will be accessible to students in Form 1 or above.

話事啤

2009-08-04T19:18:00.000+08:00

很多以賭博為題的電視劇或電影中都會出現「話事啤」遊戲，劇中出現的賭局往往是「同花順贏四條」之類的「夢幻組合」。大家只要「實戰」一下的話，肯定會發現出現「花」或以上的牌組其實已經極其困難，即使窮畢生的精力，恐怕也未必能遇上這樣的情況。

我們不妨計算一下「花」出現的概率。五張牌的組合共有 C(52,5)=2598960 個，而「花」的組合則有 4x(C(13,5)-10)=5108 個。（這裡「4x」是因為有四門花式可選擇，「C(13,5)」是因為每次從指定花式的 13 張中選 5 張，「-10」是要除去「同花順」的可能性。）因此出現「花」的概率是 5108/2598960，即約 0.1965%，故此平均每 509 手牌才有一次「花」的出現。「夫佬」、「四條」和「同花順」要難得多，例如「同花順」出現的概率只有 40/2598960（約 0.0015%），平均每 64974 手牌才會出現一次。

值得一提，電視劇或電影中不時會出現「三條贏蛇」的場面，而現實中亦有人採納這樣的規則。但經計算可知，「三條」出現的概率是 54912/2598960（約 2.1128%），而「蛇」出現的概率則是 10200/2598960（約 0.3925%），可見得到「三條」比「蛇」容易得多，因此「國際慣例」是「蛇贏三條」的，這也是較合理的規定。

「甚麼也沒有」的概率是多少？只要從 1 減去「一對」、「兩對」、「三條」、「蛇」、「花」、「夫佬」、「四條」和「同花順」的概率，可得 1302540/2598960（約 50.1177%）。細看一下，原來剛好是「花」的概率的 255 倍，這不太可能是巧合吧？再想一想，你是否已經彷然大悟呢？當你再發現「蛇」的概率也正好是「同花順」的 255 倍時，你又是否在驚嘆數學竟可這樣美麗和迷人？

24 小時制與 12 小時制

2009-07-29T21:20:00.004+08:00

我們知道，表示時間一般有兩種方式：24 小時制（例如 06:17、23:20 等）和 12 小時制（例如 06:07 AM、11:20 PM 等）。不同人對兩者有不同的喜好，例如有人認為我們看慣了 12 小時制的時鐘，所以用 12 小時制會較為容易，亦有人認為 24 小時制比較清晰，可以避免混淆。

無疑，兩者都各有其好處。不過我想到一個實際的原因，使用起來還是 24 小時制比較方便的，那在於比較時間的先後次序。當我們有一些日期和時間的數據需要排序時，我們會先看年份，較小者為先，相同則看月份，再相同則看「日」，仍然相同時便要比較時間。如果是 12 小時制的話，那自然是先看上午或下午，再看「時」，再看「分」。大家試試對以下同一天內的時間排列先後次序：

07:23 AM
11:06 PM
12:23 PM
12:45 AM
10:37 AM
10:30 PM
11:01 PM
07:38 AM

大家看出了問題所在嗎？要把 10、11 和 12 排序時，正確的次序是 12、10、11，這和我們平日對數字的自然反應很不同。使用 24 小時制的話，這個問題便迎刃而解。當然，堅持使用 12 小時制也可以解決這個問題的 -- 只要把時鐘上的「12」改成「0」就可以了。XD

IMO Q6 2009

2009-07-21T05:38:00.003+08:00

There is this collaborative project of solving IMO Q6 2009: http://terrytao.wordpress.com/2009/07/20/imo-2009-q6-as-a-mini-polymath-project/. Perhaps some of you will be interested in thinking about the problem together (with all the other math people around the world)? I saw Tim Gowers (a Field's medalist) constantly making comments on the various approaches that people suggest, so it might be interesting to read the comments as people make progress even if you are not actively thinking about it.

Video lectures online

2009-07-17T09:33:00.008+08:00

I was just brought into notice that seven videotaped lectures from 1964 by the renowned physicist Richard Feynman, on "The Character of Physical Law", have been put online for public use. (I learned this from this post by Terry Tao, and if you're interested in these lectures by Feynman you'll also probably be interested in the following more advanced lectures that he gave.) I hope it's not too out of place to put this piece of news here, but having heard this triggered me to look online for some good math lectures as well. I found the following site, which has some good undergraduate level mathematics lectures (probably accessible to some F.6 or F.7 students too):

http://ocw.mit.edu/OcwWeb/web/courses/av/index.htm#Mathematics

In fact I think the first course, on single variable calculus, should be good for students studying Additional mathematics. These are very good learning materials, and hopefully some of you will find it useful.

Test Your Intuition

2009-07-14T18:41:00.006+08:00

有一個網誌叫"Combinatorics and More"。近期網誌主人有一系列"Test Your Intuition"的文章，裏面有一些問題，你要用直觀猜答案。我自己覺得是很好玩的東西。（齋睇blog文唔好玩，要睇埋comments！）

今天我也仿傚一下，出一題test大家的intuition吧！

若將首N個3的倍數都轉成二進制，當N很大的時候（例如N大於1億），你猜數字"0"與數字"1"出現的次數哪個較多？互有領先？還是其中一個出現的次數永遠比另一個多？

（註：不考慮leading zeros！）

充滿數學哲理的名言（二）

2009-07-02T15:45:00.004+08:00

本文再談一個充滿數學哲理的名言：「大膽假設，小心求證」。這句名言是中國近代學者胡適於五四運動期間提出的科學精神。用於數學，這句話特別有意思。最近我在一個測驗中給了學生一道題：

現要在一個 3x3 表格的九格中分別填上 1 至 9。若兩個相鄰的方格的兩數中，一個是另一個的倍數，則這兩個方格稱為「好對」。求「好對」的數目的最大可能值。

這題不難，經過一些試驗後，很多學生都得到一個 9 個「好對」的例子：

８　２　６

４　１　３

５　７　９

當然，這並不足夠，因為題目是求「好對」的數目的最大可能值，你怎知道這是最大呢？於是學生開始「證明」起來：「由於 1 可組成最多好對，為使好對的數目最多，所以 1 應該放在中間；2 可組成第二多的好對，所以應該放在一行或一列的中間，……」

「1 應該放在中間」是很自然的想法，這源自我們「對數學的感覺」。這份「數學感」是很重要的，因為解決數學問題時我們很多事不會預知結果，而是要找出結果再作證明，過程中這份「感覺」往往可以指導我們作出合理的猜測，此乃「大膽假設」。在「有感覺」的前提下，我們的假設不妨大膽一點（注意「大膽假設」異於「隨意猜測」，前者是基於理性的「數學感」的），事實上數學的發展是很靠創意和想像力的，而作出假設也可以給我們清晰的目標。

可是數學對證明的要求是十分嚴謹的，說某些數字「應該」放在某些地方，從證明的角度看其實是「說了等於沒說」，我們得提出確實的證據來說明我們的假設是對的，此乃「小心求證」。事實上這些來自我們的「直覺」的假設有些時候是不正確的，例如：有些人也許會認為「由於 5 和 7 都只能和 1 組成好對，因此 1 應該和 5、7 都相鄰」，這個假設看起來似乎也合理，但卻是錯的（要知道它確實是錯的話，也得「小心求證」！）。

由此可見，「大膽假設」固然重要，但「小心求證」也同樣重要。大家可以動手「小心求證」一下，在上題中「好對」數目的最大可能值的確是 9。這裡方法有很多，最常見的方法是考慮 5 和 7 的位置的可能性，另有一個更漂亮和簡潔的證明，是分別考慮「牽涉 1、2 的好對」和「不牽涉 1、2 的好對」的數目，大家不妨試試。

充滿數學哲理的名言（一）

2009-06-22T20:50:00.004+08:00

有些名言充滿數學哲理，本文選談兩個和概率論有關的名言。

上得山多終遇虎

這句話原指走到山上要面對老虎帶來的危險，即使一次沒有遇到，但如果不斷上山的話，總會有遇到老虎的一天，通常用作比喻做壞事的人終會受到制裁。這話背後有甚麼數學哲理呢？假設每次上山「遇虎」的概率為 p (>0)，且上山 n 次後遇虎最少一次的概率是 P_n，則 P_n = 1 - (1-p)ⁿ，故此不難發現當 n 趨向無限大時，P_n 的值趨向 1，應驗了「終遇虎」的結論！

一鳥在手勝過二鳥在林

這句話相信是出自英語的「One bird in hand is worth two in the bush」，不論中英文版本都有一些「變種」，主要是把「二」變成其他數字，不過意思也都相同，就是說「實在」勝過「浮雲」，有時則用以比喻要珍惜現在，別奢求無法得到的東西。

這話背後又有甚麼數學哲理？一鳥在手是否勝過二鳥在林，表面上視乎「在林」的鳥可以「到手」的概率 p，也就是視乎「二鳥在林」的期望值（expected value）。如果 p>0.5 的話，則「二鳥在林」的期望值是比「一鳥」高的。那麼為甚麼有一鳥在手「勝過」二鳥在林的說法呢？

很多時候，我們下決定時都不只看期望值。舉例說，假設你的身家有 n 元，現讓你從一副紙牌中抽兩張，如果抽到黑桃 A 和紅心 A 的話獎你 100000 n 元，否則輸掉 n 元，遊戲只可玩一次。這個遊戲的期望值是個很大的正數（當然是相對 n 而言），你願意參加嗎？除了期望值外，離差（dispersion）也會影響我們的決定，例如標準差（standard variation）是一個常見的離差指標。一般來說，我們希望離差越小越好，於是以上遊戲中正數的期望值便不足以彌補很大的離差。

這就解釋了一鳥在手為何可以勝過二鳥在林了 -- 因為「一鳥在手」時標準差是零，而「二鳥在林」時標準差是正數呢！