2009年7月21日 星期二
IMO Q6 2009
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.
2009年7月17日 星期五
Video lectures online
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.
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.
2009年7月14日 星期二
Test Your Intuition
有一個網誌叫"Combinatorics and More"。近期網誌主人有一系列"Test Your Intuition"的文章，裏面有一些問題，你要用直觀猜答案。我自己覺得是很好玩的東西。（齋睇blog文唔好玩，要睇埋comments！）
今天我也仿傚一下，出一題test大家的intuition吧！
若將首N個3的倍數都轉成二進制，當N很大的時候（例如N大於1億），你猜數字"0"與數字"1"出現的次數哪個較多？互有領先？還是其中一個出現的次數永遠比另一個多？
（註：不考慮leading zeros！）
今天我也仿傚一下，出一題test大家的intuition吧！
若將首N個3的倍數都轉成二進制，當N很大的時候（例如N大於1億），你猜數字"0"與數字"1"出現的次數哪個較多？互有領先？還是其中一個出現的次數永遠比另一個多？
（註：不考慮leading zeros！）
2009年7月2日 星期四
充滿數學哲理的名言（二）
本文再談一個充滿數學哲理的名言：「大膽假設，小心求證」。這句名言是中國近代學者胡適於五四運動期間提出的科學精神。用於數學，這句話特別有意思。最近我在一個測驗中給了學生一道題：
現要在一個 3x3 表格的九格中分別填上 1 至 9。若兩個相鄰的方格的兩數中，一個是另一個的倍數，則這兩個方格稱為「好對」。求「好對」的數目的最大可能值。
這題不難，經過一些試驗後，很多學生都得到一個 9 個「好對」的例子：
８ ２ ６
４ １ ３
５ ７ ９
當然，這並不足夠，因為題目是求「好對」的數目的最大可能值，你怎知道這是最大呢？於是學生開始「證明」起來：「由於 1 可組成最多好對，為使好對的數目最多，所以 1 應該放在中間；2 可組成第二多的好對，所以應該放在一行或一列的中間，……」
「1 應該放在中間」是很自然的想法，這源自我們「對數學的感覺」。這份「數學感」是很重要的，因為解決數學問題時我們很多事不會預知結果，而是要找出結果再作證明，過程中這份「感覺」往往可以指導我們作出合理的猜測，此乃「大膽假設」。在「有感覺」的前提下，我們的假設不妨大膽一點（注意「大膽假設」異於「隨意猜測」，前者是基於理性的「數學感」的），事實上數學的發展是很靠創意和想像力的，而作出假設也可以給我們清晰的目標。
可是數學對證明的要求是十分嚴謹的，說某些數字「應該」放在某些地方，從證明的角度看其實是「說了等於沒說」，我們得提出確實的證據來說明我們的假設是對的，此乃「小心求證」。事實上這些來自我們的「直覺」的假設有些時候是不正確的，例如：有些人也許會認為「由於 5 和 7 都只能和 1 組成好對，因此 1 應該和 5、7 都相鄰」，這個假設看起來似乎也合理，但卻是錯的（要知道它確實是錯的話，也得「小心求證」！）。
由此可見，「大膽假設」固然重要，但「小心求證」也同樣重要。大家可以動手「小心求證」一下，在上題中「好對」數目的最大可能值的確是 9。這裡方法有很多，最常見的方法是考慮 5 和 7 的位置的可能性，另有一個更漂亮和簡潔的證明，是分別考慮「牽涉 1、2 的好對」和「不牽涉 1、2 的好對」的數目，大家不妨試試。
現要在一個 3x3 表格的九格中分別填上 1 至 9。若兩個相鄰的方格的兩數中，一個是另一個的倍數，則這兩個方格稱為「好對」。求「好對」的數目的最大可能值。
這題不難，經過一些試驗後，很多學生都得到一個 9 個「好對」的例子：
８ ２ ６
４ １ ３
５ ７ ９
當然，這並不足夠，因為題目是求「好對」的數目的最大可能值，你怎知道這是最大呢？於是學生開始「證明」起來：「由於 1 可組成最多好對，為使好對的數目最多，所以 1 應該放在中間；2 可組成第二多的好對，所以應該放在一行或一列的中間，……」
「1 應該放在中間」是很自然的想法，這源自我們「對數學的感覺」。這份「數學感」是很重要的，因為解決數學問題時我們很多事不會預知結果，而是要找出結果再作證明，過程中這份「感覺」往往可以指導我們作出合理的猜測，此乃「大膽假設」。在「有感覺」的前提下，我們的假設不妨大膽一點（注意「大膽假設」異於「隨意猜測」，前者是基於理性的「數學感」的），事實上數學的發展是很靠創意和想像力的，而作出假設也可以給我們清晰的目標。
可是數學對證明的要求是十分嚴謹的，說某些數字「應該」放在某些地方，從證明的角度看其實是「說了等於沒說」，我們得提出確實的證據來說明我們的假設是對的，此乃「小心求證」。事實上這些來自我們的「直覺」的假設有些時候是不正確的，例如：有些人也許會認為「由於 5 和 7 都只能和 1 組成好對，因此 1 應該和 5、7 都相鄰」，這個假設看起來似乎也合理，但卻是錯的（要知道它確實是錯的話，也得「小心求證」！）。
由此可見，「大膽假設」固然重要，但「小心求證」也同樣重要。大家可以動手「小心求證」一下，在上題中「好對」數目的最大可能值的確是 9。這裡方法有很多，最常見的方法是考慮 5 和 7 的位置的可能性，另有一個更漂亮和簡潔的證明，是分別考慮「牽涉 1、2 的好對」和「不牽涉 1、2 的好對」的數目，大家不妨試試。
2009年6月22日 星期一
充滿數學哲理的名言（一）
有些名言充滿數學哲理，本文選談兩個和概率論有關的名言。
上得山多終遇虎
這句話原指走到山上要面對老虎帶來的危險，即使一次沒有遇到，但如果不斷上山的話，總會有遇到老虎的一天，通常用作比喻做壞事的人終會受到制裁。這話背後有甚麼數學哲理呢？假設每次上山「遇虎」的概率為 p (>0)，且上山 n 次後遇虎最少一次的概率是 Pn，則 Pn = 1 - (1-p)n，故此不難發現當 n 趨向無限大時，Pn 的值趨向 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）是一個常見的離差指標。一般來說，我們希望離差越小越好，於是以上遊戲中正數的期望值便不足以彌補很大的離差。
這就解釋了一鳥在手為何可以勝過二鳥在林了 -- 因為「一鳥在手」時標準差是零，而「二鳥在林」時標準差是正數呢！
上得山多終遇虎
這句話原指走到山上要面對老虎帶來的危險，即使一次沒有遇到，但如果不斷上山的話，總會有遇到老虎的一天，通常用作比喻做壞事的人終會受到制裁。這話背後有甚麼數學哲理呢？假設每次上山「遇虎」的概率為 p (>0)，且上山 n 次後遇虎最少一次的概率是 Pn，則 Pn = 1 - (1-p)n，故此不難發現當 n 趨向無限大時，Pn 的值趨向 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）是一個常見的離差指標。一般來說，我們希望離差越小越好，於是以上遊戲中正數的期望值便不足以彌補很大的離差。
這就解釋了一鳥在手為何可以勝過二鳥在林了 -- 因為「一鳥在手」時標準差是零，而「二鳥在林」時標準差是正數呢！
2009年6月20日 星期六
Convolution Technique in Generating Function (2)
It is quite unexpected that the second part of this passage is posted three months later. Anyway, let me post the link to the first part of this passage. Here, I am going to discuss another counting problem which we can use convolution technique to solve.
Let me recall the key idea again. Convolution of generating functions can be useful when we try to count a class of combinatorial objects, while these objects can be constructed by joining two smaller objects of size k and M-k.
Here comes the question, which looks really unfavourite when you first see it. An n by n square matrix M satisfies the following conditions: (1) every entry is a non-negative integer; (2) the sum of entries in each column is n-1; (3) for any two entries which are both positive, denote the coordinates by
and 
, then 
.
Below shows a few 4 by 4 matrices which satisfy the three conditions:
, 
, 
The first two conditions can be easily visualized. The third condition can be visualized as follows: for any non-zero entry, its north-west and south-east direction entries must be all zero.
I will generalize by counting the number of p (number of columns) by q (number of rows) matrices satisfying the three conditions (note: the sum of each column is fixed to be n-1). Let the number of such p by q matrices be
. Then our target is finding 
.
Suppose
denote the entry in the first column such that it is the toppest entry in the first column with non-zero entries (i.e. 
for all 
.) So the matrix looks like:
The black parts will be with all zero entries (by definition of and by condition 3). So the construction of this matrix can be divided into two parts:
a) constructing a 1 by k sub-matrix such that
with 
and 
.
b) constructing the (p-1) by (q-k+1) sub-matrix A such that the three conditions are satisfied.
By simple combinatorics, there are
ways to construct part a) (if you do not see why, read the notes "Combinations and Permutations" in Mathematical Database; in particular, it is page 10 to 14) and by definition, there are 
ways to construct part b). As k can be any value between 1 and q (inclusive), we have the recurrence relation:
Compare this recurrence to the one for Catalan numbers. Do you see the similarity? If so, try to continue. I will complete this passage a few days later (hopefully...).
Let me recall the key idea again. Convolution of generating functions can be useful when we try to count a class of combinatorial objects, while these objects can be constructed by joining two smaller objects of size k and M-k.
Here comes the question, which looks really unfavourite when you first see it. An n by n square matrix M satisfies the following conditions: (1) every entry is a non-negative integer; (2) the sum of entries in each column is n-1; (3) for any two entries which are both positive, denote the coordinates by
and , then .Below shows a few 4 by 4 matrices which satisfy the three conditions:
, , The first two conditions can be easily visualized. The third condition can be visualized as follows: for any non-zero entry, its north-west and south-east direction entries must be all zero.
I will generalize by counting the number of p (number of columns) by q (number of rows) matrices satisfying the three conditions (note: the sum of each column is fixed to be n-1). Let the number of such p by q matrices be
. Then our target is finding .Suppose
denote the entry in the first column such that it is the toppest entry in the first column with non-zero entries (i.e. for all .) So the matrix looks like:
The black parts will be with all zero entries (by definition of and by condition 3). So the construction of this matrix can be divided into two parts:a) constructing a 1 by k sub-matrix such that
with and .b) constructing the (p-1) by (q-k+1) sub-matrix A such that the three conditions are satisfied.
By simple combinatorics, there are
ways to construct part a) (if you do not see why, read the notes "Combinations and Permutations" in Mathematical Database; in particular, it is page 10 to 14) and by definition, there are ways to construct part b). As k can be any value between 1 and q (inclusive), we have the recurrence relation:Compare this recurrence to the one for Catalan numbers. Do you see the similarity? If so, try to continue. I will complete this passage a few days later (hopefully...).
2009年6月10日 星期三
概率證明
有些時候，我們可以利用概率的性質來證明一些組合題。即使題目本身看來和概率毫不相干，但加入了概率的考慮往往可以讓我們得出一個簡潔的證明。以下提供一個例子。
問題：
某學校響應微調政策，開辦的 n 個科目均設中文班和英文班。每位同學均可自由選讀不同的科目，數量不限，但同一科目不可同時報讀中文班和英文班。已知對任意兩個科目，均存在一名學生以不同語文同時修讀兩科。若每科最多有 10 名學生修讀，求 n 的最大可能值。
大家看下去前，不妨先停下來自己動動腦筋。
解答：
n 的最大可能值是 1024。
我們首先注意到 n=1024 是可能的：如果全校有 10 位學生，每人均報讀全部 1024 個科目，且學生 i 報讀第 j 個科目的中文班當且僅當 j 的二進制表示中右方數起的第 i 個位是 1（否則報讀第 j 個科目的英文班），則不難檢查得知這符合題中的條件。
以下證明 n 不可大於 1024。假設學生入學時會被隨機編成「中文人」或「英文人」。設 Ei 表示事件「第 i 個科目的學生全部選讀了對應自己身份的語文班」，則由於每科最多有 10 名學生修讀，故 P(Ei) ≧ 1/210 = 1/1024。再者，由「對任意兩個科目，均存在一名學生以不同語文同時修讀兩科」可知 E1、E2、…、En 是互斥事件，故此
從而必有 n≦1024。
這個帶點神秘感的概率題解，某程度上其實對應一些數算的技巧，再用概率加以包裝。概率證明還可以處理一些更複雜的情況，例如可以使用 Lovasz local lemma 來處理一些難以準確計算的概率，有興趣的讀者可點擊上方的連結細看。順帶一提，證明以上定理的 Lovasz 曾在國際數學奧林匹克（IMO）奪得三金一銀，而他的兒子至今亦已在 IMO 奪得一金一銀！
問題：
某學校響應微調政策，開辦的 n 個科目均設中文班和英文班。每位同學均可自由選讀不同的科目，數量不限，但同一科目不可同時報讀中文班和英文班。已知對任意兩個科目，均存在一名學生以不同語文同時修讀兩科。若每科最多有 10 名學生修讀，求 n 的最大可能值。
大家看下去前，不妨先停下來自己動動腦筋。
解答：
n 的最大可能值是 1024。
我們首先注意到 n=1024 是可能的：如果全校有 10 位學生，每人均報讀全部 1024 個科目，且學生 i 報讀第 j 個科目的中文班當且僅當 j 的二進制表示中右方數起的第 i 個位是 1（否則報讀第 j 個科目的英文班），則不難檢查得知這符合題中的條件。
以下證明 n 不可大於 1024。假設學生入學時會被隨機編成「中文人」或「英文人」。設 Ei 表示事件「第 i 個科目的學生全部選讀了對應自己身份的語文班」，則由於每科最多有 10 名學生修讀，故 P(Ei) ≧ 1/210 = 1/1024。再者，由「對任意兩個科目，均存在一名學生以不同語文同時修讀兩科」可知 E1、E2、…、En 是互斥事件，故此
1 ≧ P(E1∪E2∪…∪En) = P(E1) + P(E2) + ... + P(En) ≧ n/1024，
從而必有 n≦1024。
這個帶點神秘感的概率題解，某程度上其實對應一些數算的技巧，再用概率加以包裝。概率證明還可以處理一些更複雜的情況，例如可以使用 Lovasz local lemma 來處理一些難以準確計算的概率，有興趣的讀者可點擊上方的連結細看。順帶一提，證明以上定理的 Lovasz 曾在國際數學奧林匹克（IMO）奪得三金一銀，而他的兒子至今亦已在 IMO 奪得一金一銀！
訂閱：
文章 (Atom)