本文再談一個充滿數學哲理的名言：「大膽假設，小心求證」。這句名言是中國近代學者胡適於五四運動期間提出的科學精神。用於數學，這句話特別有意思。最近我在一個測驗中給了學生一道題：
現要在一個 3x3 表格的九格中分別填上 1 至 9。若兩個相鄰的方格的兩數中，一個是另一個的倍數，則這兩個方格稱為「好對」。求「好對」的數目的最大可能值。
這題不難，經過一些試驗後，很多學生都得到一個 9 個「好對」的例子：
８ ２ ６
４ １ ３
５ ７ ９
當然，這並不足夠，因為題目是求「好對」的數目的最大可能值，你怎知道這是最大呢？於是學生開始「證明」起來：「由於 1 可組成最多好對，為使好對的數目最多，所以 1 應該放在中間；2 可組成第二多的好對，所以應該放在一行或一列的中間，……」
「1 應該放在中間」是很自然的想法，這源自我們「對數學的感覺」。這份「數學感」是很重要的，因為解決數學問題時我們很多事不會預知結果，而是要找出結果再作證明，過程中這份「感覺」往往可以指導我們作出合理的猜測，此乃「大膽假設」。在「有感覺」的前提下，我們的假設不妨大膽一點（注意「大膽假設」異於「隨意猜測」，前者是基於理性的「數學感」的），事實上數學的發展是很靠創意和想像力的，而作出假設也可以給我們清晰的目標。
可是數學對證明的要求是十分嚴謹的，說某些數字「應該」放在某些地方，從證明的角度看其實是「說了等於沒說」，我們得提出確實的證據來說明我們的假設是對的，此乃「小心求證」。事實上這些來自我們的「直覺」的假設有些時候是不正確的，例如：有些人也許會認為「由於 5 和 7 都只能和 1 組成好對，因此 1 應該和 5、7 都相鄰」，這個假設看起來似乎也合理，但卻是錯的（要知道它確實是錯的話，也得「小心求證」！）。
由此可見，「大膽假設」固然重要，但「小心求證」也同樣重要。大家可以動手「小心求證」一下，在上題中「好對」數目的最大可能值的確是 9。這裡方法有很多，最常見的方法是考慮 5 和 7 的位置的可能性，另有一個更漂亮和簡潔的證明，是分別考慮「牽涉 1、2 的好對」和「不牽涉 1、2 的好對」的數目，大家不妨試試。
2009年7月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
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
Suppose
The black parts will be with all zero entries (by definition of a) constructing a 1 by k sub-matrix such that
b) constructing the (p-1) by (q-k+1) sub-matrix A such that the three conditions are satisfied.
By simple combinatorics, there are
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 奪得一金一銀！
2009年5月24日 星期日
Two Problems about Countability
Recently I heard two related problems about countability. They should be good exercises for mathematial analysis amateur.
Below N denotes the set of natural numbers.
The first question is, is there exists an uncountable collection of finite subsets of N, such that for any two subsets A and B in the collection, one is the subset of another?
The second question is, is there exists an uncountable collection of subsets of N, such that for any two subsets A and B in the collection, one is the subset of another?
------
The first question is very easy. The second question is a bit tricky.
Below N denotes the set of natural numbers.
The first question is, is there exists an uncountable collection of finite subsets of N, such that for any two subsets A and B in the collection, one is the subset of another?
The second question is, is there exists an uncountable collection of subsets of N, such that for any two subsets A and B in the collection, one is the subset of another?
------
The first question is very easy. The second question is a bit tricky.
2009年5月22日 星期五
四捨五入
日前有報章報導，東亞銀行的網上系統有漏洞，只要不斷透過四捨五入造成的誤差，便可安坐家中賺取利潤。本文談談「四捨五入」這個數學上常用的取近似值的方法。
四捨五入的原理很簡單，基本上就是「向較接近的一方取近似值，以減少誤差」。例如，要把123.456 取小數點後一位的近似值，則因為 123.456 界乎 123.4 和 123.5 之間，而且較接近後者，因此我們取 123.5 作為近似值。
這裡有一個小問題，就是「較接近的一方」並不一定存在，例如把 123.450 捨入至 123.4 和 123.5 都是「同樣接近」的，故此我們根據「五入」的規則，把 123.450 向上捨入至 123.5。但這樣做的話得出的近似值會偏大。如果只是把 123.450 變成 123.5 當然問題不大，不過如果是 1.5 變 2，或 10.5 變 11 的話，而且經常要「五入」的話（這樣的例子是存在的，例如以 0.5 分為評分單位但最終分數必定是整數的考試），那就很不同了。
為了解決這個「偏大」的問題，一個「修正版」的四捨五入法是「四捨六入五留雙（banker's rounding）」。名字本身有點誤導：雖然叫「六入」，但其實是「(5+ε)入」，例如 123.456 仍會「(5.6)入」至 123.5。只是當出現 123.450 這些「打和」的情況時，才採用「五留雙」的規則：如果 5 字前的位是雙數則保留，單數則進位，故基於「4」是雙數，123.450 會向下捨入至 123.4，而 123.550 則會上捨入至 123.6。至於「banker」是否真的採用此規則，大家不妨測試一下。
那麼為甚麼要「留雙」而不是「留單」呢？我有以下猜測。在以上 123.456 的例子中，如果採用四捨五入法取小數點後一位的近似值，則會變成 123.5，如果再把近似值取最接近整數，則變成 124。問題是最接近 123.456 的整數應是 123 才對。再細看一下，我們發現其實 123.44...445 已經可以「合法地」變成 124：只要逐位「五入」即可，而且即使採用「四捨六入五留單」，同樣的情況仍會發生。採用「五留雙」的話，這樣的情況會得到一點點的改善（雖然也好不到哪裡）：123.4500...001 才可以「合法地」變成 124！
四捨五入的原理很簡單，基本上就是「向較接近的一方取近似值，以減少誤差」。例如，要把123.456 取小數點後一位的近似值，則因為 123.456 界乎 123.4 和 123.5 之間，而且較接近後者，因此我們取 123.5 作為近似值。
這裡有一個小問題，就是「較接近的一方」並不一定存在，例如把 123.450 捨入至 123.4 和 123.5 都是「同樣接近」的，故此我們根據「五入」的規則，把 123.450 向上捨入至 123.5。但這樣做的話得出的近似值會偏大。如果只是把 123.450 變成 123.5 當然問題不大，不過如果是 1.5 變 2，或 10.5 變 11 的話，而且經常要「五入」的話（這樣的例子是存在的，例如以 0.5 分為評分單位但最終分數必定是整數的考試），那就很不同了。
為了解決這個「偏大」的問題，一個「修正版」的四捨五入法是「四捨六入五留雙（banker's rounding）」。名字本身有點誤導：雖然叫「六入」，但其實是「(5+ε)入」，例如 123.456 仍會「(5.6)入」至 123.5。只是當出現 123.450 這些「打和」的情況時，才採用「五留雙」的規則：如果 5 字前的位是雙數則保留，單數則進位，故基於「4」是雙數，123.450 會向下捨入至 123.4，而 123.550 則會上捨入至 123.6。至於「banker」是否真的採用此規則，大家不妨測試一下。
那麼為甚麼要「留雙」而不是「留單」呢？我有以下猜測。在以上 123.456 的例子中，如果採用四捨五入法取小數點後一位的近似值，則會變成 123.5，如果再把近似值取最接近整數，則變成 124。問題是最接近 123.456 的整數應是 123 才對。再細看一下，我們發現其實 123.44...445 已經可以「合法地」變成 124：只要逐位「五入」即可，而且即使採用「四捨六入五留單」，同樣的情況仍會發生。採用「五留雙」的話，這樣的情況會得到一點點的改善（雖然也好不到哪裡）：123.4500...001 才可以「合法地」變成 124！
2009年5月11日 星期一
Some linear algebra
These days some of my friends discussed some linear algebra problems with me. I found them quite interesting, so let me post some of them here.
1. If A and B are square matrices of the same size, then the spectrums of AB and BA are the same. More precisely, the generalized eigenvalues of AB and BA over the complex numbers occur with the same multiplicity. This is clear when A is invertible, because then AB and BA are similar. If A is not invertible, then we can approximate A by invertible matrices. The spectrum of AB is just the zeroes of det(xI-AB) (counted with multiplicities). The claim then follows easily. This generalizes the fact that the traces and determinants of AB and BA are the same.
2. If A and B are real square matrices of the same size and if there is a complex matrix U such that
, then there is a real matrix M such that 
. In other words, if two real matrices are similar over the complex numbers, then they are similar over the reals. Proof: Look at the equation MA = BM, where M is a square matrix of the same size as A and B. This is a linear system of equations in the entries of M with real coefficients. Hence if S_c is the complex vector space of complex matrices that satisfy this equation and S_r is the real vector space of real matrices that satisfy the same equation, then the complex dimension of S_c is the same as the real dimension of S_r. Now by assumption this dimension is at least 1. We want to find a real matrix in S_r that is invertible. Let 
be a basis of S_r over the reals. Then this is also a basis of S_c over the complex. By assumption there is a linear combination 
over the complex numbers whose determinant is non-zero. Hence the polynomial )
in 
does not vanish identically over 
. It follows that this polynomial cannot vanish identically over 
. Hence there is a real linear combination of that is invertible. This finishes the proof.
3. This is more or less for my own benefit, to recall the following proof of the well-known fact that any normal matrix is diagonalizable over C. Key: Assume A is normal, i.e. A commutes with A*. Then if x is an eigenvector of A, x is also an eigenvector of A*. In fact if Ax = tx, then
x, (A-tI)x\rangle = \langle(A^*-\overline{t} I)x, (A^*-\overline{t} I) x\rangle )
when A commutes with A*. This allows us to proceed by induction on the dimension of the vector space: first pick any eigenvector x of A. Then its orthogonal complement is preserved by A, because x is also an eigenvector of A*. Hence we can reduce to one dimension lower, and by induction this completes the proof.
1. If A and B are square matrices of the same size, then the spectrums of AB and BA are the same. More precisely, the generalized eigenvalues of AB and BA over the complex numbers occur with the same multiplicity. This is clear when A is invertible, because then AB and BA are similar. If A is not invertible, then we can approximate A by invertible matrices. The spectrum of AB is just the zeroes of det(xI-AB) (counted with multiplicities). The claim then follows easily. This generalizes the fact that the traces and determinants of AB and BA are the same.
2. If A and B are real square matrices of the same size and if there is a complex matrix U such that
3. This is more or less for my own benefit, to recall the following proof of the well-known fact that any normal matrix is diagonalizable over C. Key: Assume A is normal, i.e. A commutes with A*. Then if x is an eigenvector of A, x is also an eigenvector of A*. In fact if Ax = tx, then
when A commutes with A*. This allows us to proceed by induction on the dimension of the vector space: first pick any eigenvector x of A. Then its orthogonal complement is preserved by A, because x is also an eigenvector of A*. Hence we can reduce to one dimension lower, and by induction this completes the proof.
訂閱：
文章 (Atom)
