由今日起，大家除了可以使用 http://mathdb.blogspot.com/ 到達本手記外，亦可使用 http://blog.mathdb.org/ 來本手記。
當然，大家記緊也多來數學資料庫 和 Math Forum 哦。
2007年12月26日 星期三
聖誕禮物——笑話三個
小一的時候，小權參加算術比賽，贏了個冠軍回家。媽媽很開心，問比賽有甚麼問題？
小權答：「他問 6 乘 10 是多少。我答62，他就給了我這個獎杯了。」
媽媽很驚訝：「6 乘 10 的答案明明是60，你答錯了為甚麼還有獎？」
小權答：「因為全班同學的答案中，我的答案最接近，所以便得獎了。」
小二的時候，小權又參加算術比賽，又贏了冠軍回家。今次媽媽沒有先開心，又問比賽有甚麼問題。
小權答：「他問 6 除 0 是多少。全班靜了兩分鐘，我也想了很久吧，但之前未教過怎樣除 0 嘛，於是我便舉手答老師：『不知道。』」
媽媽更是糊裏糊塗了。小權續答：「怎知老師聽了以後，不斷拍掌，於是同學們又拍掌。老師把獎杯交給我，還說我是個超級天才。我想是因為我誠實，所以拿獎杯吧。」
小三的時候，小權再參加算術比賽，今次沒贏了，還垂頭喪氣地回家。今次媽媽不在，爸爸見小權不開心，便問他發生甚麼事。小權說他被記了一個小過。爸爸便問發生甚麼事。
小權說：「他首先問 2 乘 3 是多少。我便答 6 了。」
爸爸說：「對呀。又不是答錯，記甚麼小過？」
小權說：「然後他便問我 3 乘 2 是多少。」
爸爸搶著說：「TLM！2 乘 3 咪即係 3 乘 2 囉！個老師 BC 架？」
小權說：「我也是這樣跟老師說……」
小權答：「他問 6 乘 10 是多少。我答62，他就給了我這個獎杯了。」
媽媽很驚訝：「6 乘 10 的答案明明是60，你答錯了為甚麼還有獎？」
小權答：「因為全班同學的答案中，我的答案最接近，所以便得獎了。」
小二的時候，小權又參加算術比賽，又贏了冠軍回家。今次媽媽沒有先開心，又問比賽有甚麼問題。
小權答：「他問 6 除 0 是多少。全班靜了兩分鐘，我也想了很久吧，但之前未教過怎樣除 0 嘛，於是我便舉手答老師：『不知道。』」
媽媽更是糊裏糊塗了。小權續答：「怎知老師聽了以後，不斷拍掌，於是同學們又拍掌。老師把獎杯交給我，還說我是個超級天才。我想是因為我誠實，所以拿獎杯吧。」
小三的時候，小權再參加算術比賽，今次沒贏了，還垂頭喪氣地回家。今次媽媽不在，爸爸見小權不開心，便問他發生甚麼事。小權說他被記了一個小過。爸爸便問發生甚麼事。
小權說：「他首先問 2 乘 3 是多少。我便答 6 了。」
爸爸說：「對呀。又不是答錯，記甚麼小過？」
小權說：「然後他便問我 3 乘 2 是多少。」
爸爸搶著說：「TLM！2 乘 3 咪即係 3 乘 2 囉！個老師 BC 架？」
小權說：「我也是這樣跟老師說……」
2007年12月24日 星期一
從ACM回來的數學題（二）
題外話1：大家有留意的話，這個blog是由一班數學資料庫成員合作而寫的。昨日的數學資料庫例會之後，我們的作者名單增加了四個人。可以預料手記的更新將會更為頻密，為廣大網友提供更多的數學資訊。
題外話2：數學資料庫在昨日下午已經換上全新的主頁設計。自己覺得這個設計蠻好的。以往的設計需要網友們scroll down才能見到每一個項目的更新，現在則不用了。而主頁那種顏色的配搭我覺得還真美的。在此要感謝MD的會員Vris花了很多時間去設計這個新主頁。
入正題。上回預告，今次講第二題。
越南Danang的ACM/ICPC Problem C。題目是這樣的：我們稱一組連續k個質數為一個「k質數組」。例如(31,37)是一個「2質數組」，(83,89,97)是一個「3質數組」，而(53,61)則不是「2質數組」，因為53和61之間還有一個質數59。而每一個「k質數組」的重量就是該k個質數中最大的質數和最少的質數之差。例如(11,13,17,19,23)就是一個重量為23-11 = 12的「5質數組」。現在給出a,b符合條件1 < a < b < k 和d ，要找出在 [a,b] 內有多少個重量為d的「k質數組」。
當時想了一想，如果test case當中有 d = 0 ， k = 1，那不就是問我 a和b之間有多少個質數嗎？若然 a 和 b 均是很大的數，那麼要得到一個好的估計還不難（就是用Prime Number Theorem吧），但要無誤差地說出在某個特定的range內有多少個質數，唯一已知的方法就是逐個試。
最後因為a和b太大，我們認為TLE（Programming Contest術語，全寫為Time Limit Exceeded）的可能性非常大，所以我們没有做。比賽完畢後，相信百多隊中只有兩隊能夠完成這題，而其中一隊是相熟的中山大學隊。一問之下，才知道要用一個Radin-Miller Primality Test。
一般情況下，如果給的數n不太大的話，我們慣了用以下的以下的algorithm去驗它是否質數：
1)
If n is even but not 2, then it is NOT prime, done and leave this procedure.
2) for (i=3 ; i<=sqrt(n); i+=2) if (n mod i = 0) then n is NOT prime, done and leave this procedure.
3) n is a prime, terminate.
上面的algorithm的基礎就是基於一個定理：如果 n 是合成數，它最小質因數必然 <= sqrt(n)。稍為認識analysis of algorithm的人都應該知道這個 algorithm的run time是O(sqrt(n))。如果 n 是一個八位數，那麼用這個 algorithm 去驗証 n 是否質數，就需要試最少三千多次。若然只做一兩次還好，但若然有十萬個八位數要你試，最壞情況要試過億次。別以為現在的CPU越來越快，要這樣試，我辦公室內的電腦已經比一般家用電腦快，都要大約8.75秒。而這道比賽題目極有可能有test case需要我們試一千萬個數，所用的時間粗略估計會是8.75秒的20至100倍。而比賽的程式運行時間是有限制的，一般來說不會超過一分鐘。所以這個方法是不可以用來解決這道題目的。
Radin-Miller Primality Test的概念是這樣的。如果 n 是一個質數，那麼根據費馬小定理，對於所有 a < n，都有 an-1 = 1 (mod n)。若把 n-1 表成 2s d（d是奇數），我們可以得到
ad = 1 (mod n)
或
a2^r d = -1 for some 0 <= r <= s-1
Radin-Miller Primality Test就是使用以上定理的contrapositive。只要我們找出一個 a 使得以上兩條等式均不成立，那麼 n 就不可能是質數。當然，要找出一個這樣的 a 也不見得容易。但後來有人證明了對於少於
就是因為這個結果，對於每個 n 驗證是否質數的時間就變成了 5 lg n。若 n 是一個八位數字，那麼最多大約要做135次，比起上面那個"naive algorithm"的過3000次好太多了。
用了這個Radin-Miller Primality Test後怎樣完成餘下的部分就不算難，有興趣的讀者可以自己想想。
說回比賽。原來我其中一個組員是知道這個primality test的，但他當時覺得用了這個test後程式運行時間仍然太大，所以決定放棄。無言。
題外話2：數學資料庫在昨日下午已經換上全新的主頁設計。自己覺得這個設計蠻好的。以往的設計需要網友們scroll down才能見到每一個項目的更新，現在則不用了。而主頁那種顏色的配搭我覺得還真美的。在此要感謝MD的會員Vris花了很多時間去設計這個新主頁。
入正題。上回預告，今次講第二題。
越南Danang的ACM/ICPC Problem C。題目是這樣的：我們稱一組連續k個質數為一個「k質數組」。例如(31,37)是一個「2質數組」，(83,89,97)是一個「3質數組」，而(53,61)則不是「2質數組」，因為53和61之間還有一個質數59。而每一個「k質數組」的重量就是該k個質數中最大的質數和最少的質數之差。例如(11,13,17,19,23)就是一個重量為23-11 = 12的「5質數組」。現在給出a,b符合條件1 < a < b < k 和
當時想了一想，如果test case當中有 d = 0 ， k = 1，那不就是問我 a和b之間有多少個質數嗎？若然 a 和 b 均是很大的數，那麼要得到一個好的估計還不難（就是用Prime Number Theorem吧），但要無誤差地說出在某個特定的range內有多少個質數，唯一已知的方法就是逐個試。
最後因為a和b太大，我們認為TLE（Programming Contest術語，全寫為Time Limit Exceeded）的可能性非常大，所以我們没有做。比賽完畢後，相信百多隊中只有兩隊能夠完成這題，而其中一隊是相熟的中山大學隊。一問之下，才知道要用一個Radin-Miller Primality Test。
一般情況下，如果給的數n不太大的話，我們慣了用以下的以下的algorithm去驗它是否質數：
1)
If n is even but not 2, then it is NOT prime, done and leave this procedure.
2) for (i=3 ; i<=sqrt(n); i+=2) if (n mod i = 0) then n is NOT prime, done and leave this procedure.
3) n is a prime, terminate.
上面的algorithm的基礎就是基於一個定理：如果 n 是合成數，它最小質因數必然 <= sqrt(n)。稍為認識analysis of algorithm的人都應該知道這個 algorithm的run time是O(sqrt(n))。如果 n 是一個八位數，那麼用這個 algorithm 去驗証 n 是否質數，就需要試最少三千多次。若然只做一兩次還好，但若然有十萬個八位數要你試，最壞情況要試過億次。別以為現在的CPU越來越快，要這樣試，我辦公室內的電腦已經比一般家用電腦快，都要大約8.75秒。而這道比賽題目極有可能有test case需要我們試一千萬個數，所用的時間粗略估計會是8.75秒的20至100倍。而比賽的程式運行時間是有限制的，一般來說不會超過一分鐘。所以這個方法是不可以用來解決這道題目的。
Radin-Miller Primality Test的概念是這樣的。如果 n 是一個質數，那麼根據費馬小定理，對於所有 a < n，都有 an-1 = 1 (mod n)。若把 n-1 表成 2s d（d是奇數），我們可以得到
或
Radin-Miller Primality Test就是使用以上定理的contrapositive。只要我們找出一個 a 使得以上兩條等式均不成立，那麼 n 就不可能是質數。當然，要找出一個這樣的 a 也不見得容易。但後來有人證明了對於少於
就是因為這個結果，對於每個 n 驗證是否質數的時間就變成了 5 lg n。若 n 是一個八位數字，那麼最多大約要做135次，比起上面那個"naive algorithm"的過3000次好太多了。
用了這個Radin-Miller Primality Test後怎樣完成餘下的部分就不算難，有興趣的讀者可以自己想想。
說回比賽。原來我其中一個組員是知道這個primality test的，但他當時覺得用了這個test後程式運行時間仍然太大，所以決定放棄。無言。
2007年12月22日 星期六
變成一倍？
幾天前到了銀行處理帳戶的事宜時，客戶服務員把握機會向我推介該銀行管理的基金。雖然我沒有興趣購買，但等候處理文件時沒其他東西好做，於是我細心聆聽了他的推銷。期間他指出該基金利潤豐厚，前景可觀，假如在 2004 年購入，本金在 2007 年已變為原來的一倍。當時我有點心不在焉，可是當我聽到這一句時，便立即條件反射，問了他一句：「本金變為一倍不就是原地踏步嗎？」結果一如所料，原來他把「一倍」的概念弄錯，實際上他的意思是「本金在 2007 年增加了一倍」才對。
本來「增加 n 倍」和「變成 n 倍」這兩個概念的分別很明顯，但當 n = 1 時，人們卻將之混淆。這樣的例子在生活裏比比皆是。為甚麼 n = 1 這麼特別呢？愚見認為有兩個可能的原因：
這樣的錯誤不涉及高深的數學理論，但偏偏很少人會主動公開提及和更正。為甚麼？
〔註〕更高的倍數（如一百倍）未必有相應的英語單字，但人們一般也會把它們寫成形如「100-fold」的片語。可是「1-fold」或「2-fold」這種用法卻不常見。
本來「增加 n 倍」和「變成 n 倍」這兩個概念的分別很明顯，但當 n = 1 時，人們卻將之混淆。這樣的例子在生活裏比比皆是。為甚麼 n = 1 這麼特別呢？愚見認為有兩個可能的原因：
- 「變成一倍」等於沒變
與「變成兩倍」或「變成三倍」不同，「變成一倍」實際上指沒有變化，與「變成」的意思相違。因此，很多人會覺得這句話沒意思。於是他們在心裏「自動校正」(autocorrect)，將「變成一倍」自動看成有轉變意義的「增加一倍」，並慢慢習非成是。 - 中文的用法問題
這個問題在英語裏甚少發生。也許這是因為常用的倍數詞語（變成兩倍、變成三倍等），在英語裏各有自己的動詞（double、triple 等），因此「它增加兩倍」或「它增加三倍」等意思都會被「It triples.」或「It quadruples.」等寫法取代。以我有限的英語水平，我不認識有「變成一倍」的常用英語字彙。可是在中文裏，在數詞後加上後綴「倍」便輕易表達倍數的意思，使「變成一倍」這種對一般人沒甚意思的片語亦不難存在〔註〕。最後人們好像上一點指出的「自動校正」般把它錯看為「增加一倍」。因此這可能是中文才有的語病。
這樣的錯誤不涉及高深的數學理論，但偏偏很少人會主動公開提及和更正。為甚麼？
〔註〕更高的倍數（如一百倍）未必有相應的英語單字，但人們一般也會把它們寫成形如「100-fold」的片語。可是「1-fold」或「2-fold」這種用法卻不常見。
2007年12月17日 星期一
MD Academic Seminar Dec 2007
自去年開始，MD每次開會後都幾乎有academic seminar，邀請MD會員或其他朋友就不同的數學課題作講座。以後每次academic seminar都會在這裏賣廣告啦！
日期：2007 年 12 月 23 日（星期日）
時間：下午 2 時 30 分至 3 時 45 分
地點：香港大學莊月明文娛中心 101 室
講者：羅家豪（香港大學數學系博士研究生）
講題：《規則主宰遊戲》
簡介：
在日常生活中，我們經常會碰到各式各樣的「遊戲」：有朋友之間的消遣娛樂，有不同層次的體育競技，有各行各業的技藝比拼，有政治場上的選舉逐鹿。每個「遊戲」都有自己的一套遊戲規則，遊戲的結果是根據規則而得出的，因此遊戲規則可謂主宰著整個遊戲的結果。正因為遊戲規則如斯重要，我們都希望遊戲有一套公平和合理的規則。
在講座中，我們會探討一下不同的「遊戲規則」例子，包括音樂頒獎禮、足球比賽和議會選舉等。我們嘗試以數學方法把規則的「公平合理性」量化。最後我們會發現， 在某些情況下，「公平合理」的遊戲規則是不存在的。
Date: 23 December 2007 (Sunday)
Time: 2:30 pm - 3:45 pm
Venue: Room 101, Chong Yuet Ming Amenities Centre, The University of Hong Kong
Speaker: Law Ka Ho (PhD student, Department of Mathematics, The University of Hong Kong)
Title: "The Rule of the Game Rules"
Abstract:
In daily life, we come across different types of "games" -- entertainment among friends, sports tournaments at various levels, contests of various professions as well as elections in politics. Each "game" has its own set of rules, based on which the result is obtained. Hence the result of the game is "ruled by the rules". Given such importance, we always want to have a set of fair and reasonable rules for a game.
In this talk, we will look at various examples of "rules of the game", from musical prize presentations, soccer games to parliamentary elections. We try to quantify mathematically "how fair and reasonable" a set of rules is. Eventually, we shall see that under some situations, a set of rules which is "fair and reasonable" simply does not exist.
日期：2007 年 12 月 23 日（星期日）
時間：下午 2 時 30 分至 3 時 45 分
地點：香港大學莊月明文娛中心 101 室
講者：羅家豪（香港大學數學系博士研究生）
講題：《規則主宰遊戲》
簡介：
在日常生活中，我們經常會碰到各式各樣的「遊戲」：有朋友之間的消遣娛樂，有不同層次的體育競技，有各行各業的技藝比拼，有政治場上的選舉逐鹿。每個「遊戲」都有自己的一套遊戲規則，遊戲的結果是根據規則而得出的，因此遊戲規則可謂主宰著整個遊戲的結果。正因為遊戲規則如斯重要，我們都希望遊戲有一套公平和合理的規則。
在講座中，我們會探討一下不同的「遊戲規則」例子，包括音樂頒獎禮、足球比賽和議會選舉等。我們嘗試以數學方法把規則的「公平合理性」量化。最後我們會發現， 在某些情況下，「公平合理」的遊戲規則是不存在的。
Date: 23 December 2007 (Sunday)
Time: 2:30 pm - 3:45 pm
Venue: Room 101, Chong Yuet Ming Amenities Centre, The University of Hong Kong
Speaker: Law Ka Ho (PhD student, Department of Mathematics, The University of Hong Kong)
Title: "The Rule of the Game Rules"
Abstract:
In daily life, we come across different types of "games" -- entertainment among friends, sports tournaments at various levels, contests of various professions as well as elections in politics. Each "game" has its own set of rules, based on which the result is obtained. Hence the result of the game is "ruled by the rules". Given such importance, we always want to have a set of fair and reasonable rules for a game.
In this talk, we will look at various examples of "rules of the game", from musical prize presentations, soccer games to parliamentary elections. We try to quantify mathematically "how fair and reasonable" a set of rules is. Eventually, we shall see that under some situations, a set of rules which is "fair and reasonable" simply does not exist.
2007年12月11日 星期二
不是醫院法則，也不應是 l' Hôpital rule
先說一點其他事。作為一個數學網誌，除了要經常更新，也應該推介一些好的數學文章。大約兩個月前Kahoo在MD Blog有一篇關於偏序集的文章；今天看Quod Erat Demonstrandum時，也見到一篇文章，提及全序和複序，寫得很好，就在這裏貼一下好了。
我想大部分在香港或英國讀高考Pure Mathematics或Further Mathematics的人，都還記得有一條「醫院法則」。身邊不少同學甚至老師，一見到 l' Hôpital rule（若然有一天你考高考時因為忘記了寫 'o'上面的小符號而被扣一分……），經過體內複雜的神經系統的條件反射，就會讀成「臘‧荷士必圖 胡」。但認真望一望，中間其實是沒有 's' 這個字母的。根據維基百科的資料，這個數學家是將自己的名字串成 「l' Hospital」的，但法文卻是將's'拿掉，而在 'o' 上面加一個小向上箭號。而他的名字的讀音，是沒有 's'的（讀瀏覽Merriam-Master Online聽讀音；只能在Internet Explorer內發聲）。
昨日有在美國攻讀數學博士的朋友回港，連同Dr. Kin Li的幾個人就在科大的cafe閒談。席間Dr. Li談起原來 l' Hôpital rule根本就不是 l' Hôpital的發現。一般的說法是指 l' Hôpital 當時每年給另一位數學家 John Bernoulli 一些錢，Bernoulli就教 l' Hôpital微積分和替 l' Hôpital 解一些關於微積分的問題。這些問題當中，其中一條就是現在的 l' Hôpital rule。 1696年，l' Hôpital 將他學習微積分的筆記緝錄成書，當中包括了這個法則。當時 l' Hôpital 並未有將自己的名字加上去。但後來John Bernoulli 卻指 l' Hôpital 抄襲。而當時 l' Hôpital 已經死掉，出版社將這本書推出，並指 l' Hôpital 就是作者。就這樣，John Bernoulli發現的法則，卻以 l' Hôpital 去命名了。
原以為這種張冠李戴的事非常罕見。但今天Dr. Li給我們發了一封電郵，裏面說原來泰勒公式（Taylor's series）也不是Brook Taylor的發現。而被視為Diophantine Equation內一個重要結果的Pell's Equation，其實發現者也不是叫Pell。想知道甚麼是Pell's Equation和Pell's Equation「版權」誰屬，可參考Dr. Li等人主編的數學雜誌 Mathematical Excalibur Volume 6 No. 3和Volume 7 No. 1。
我想大部分在香港或英國讀高考Pure Mathematics或Further Mathematics的人，都還記得有一條「醫院法則」。身邊不少同學甚至老師，一見到 l' Hôpital rule（若然有一天你考高考時因為忘記了寫 'o'上面的小符號而被扣一分……），經過體內複雜的神經系統的條件反射，就會讀成「臘‧荷士必圖 胡」。但認真望一望，中間其實是沒有 's' 這個字母的。根據維基百科的資料，這個數學家是將自己的名字串成 「l' Hospital」的，但法文卻是將's'拿掉，而在 'o' 上面加一個小向上箭號。而他的名字的讀音，是沒有 's'的（讀瀏覽Merriam-Master Online聽讀音；只能在Internet Explorer內發聲）。
昨日有在美國攻讀數學博士的朋友回港，連同Dr. Kin Li的幾個人就在科大的cafe閒談。席間Dr. Li談起原來 l' Hôpital rule根本就不是 l' Hôpital的發現。一般的說法是指 l' Hôpital 當時每年給另一位數學家 John Bernoulli 一些錢，Bernoulli就教 l' Hôpital微積分和替 l' Hôpital 解一些關於微積分的問題。這些問題當中，其中一條就是現在的 l' Hôpital rule。 1696年，l' Hôpital 將他學習微積分的筆記緝錄成書，當中包括了這個法則。當時 l' Hôpital 並未有將自己的名字加上去。但後來John Bernoulli 卻指 l' Hôpital 抄襲。而當時 l' Hôpital 已經死掉，出版社將這本書推出，並指 l' Hôpital 就是作者。就這樣，John Bernoulli發現的法則，卻以 l' Hôpital 去命名了。
原以為這種張冠李戴的事非常罕見。但今天Dr. Li給我們發了一封電郵，裏面說原來泰勒公式（Taylor's series）也不是Brook Taylor的發現。而被視為Diophantine Equation內一個重要結果的Pell's Equation，其實發現者也不是叫Pell。想知道甚麼是Pell's Equation和Pell's Equation「版權」誰屬，可參考Dr. Li等人主編的數學雜誌 Mathematical Excalibur Volume 6 No. 3和Volume 7 No. 1。
2007年12月8日 星期六
出席數學會議
編按：本文作者現於德國攻讀博士學位
剛於 11 月中去了一個組合數學的會議（全名為 Kolloquium ueber Kombinatorik）。雖然我只是剛「開學」，談不上有甚麼研究可以發表，但因我的 supervisor 是主辦者之一，所以便去了「捧場」。
這是我第一次出席學術會議，而我這個「大鄉里」亦在報名時擺了一個烏龍 -- 在填報資料時，我在「地址」一欄很自然地填了我的住址。後來才發現原來場刊是會將參加者的地址刊登出來，故我們應填上所屬大學或研究所的地址！由於「填錯」了地址，我的個人資料在一眾參加者當中就顯得格格不入（英文可以說成「unprofessional」）。
這次會議在 Magdeburg 舉行，是柏林以西的一個小鎮。由於這次只是去「sit 會」，故也沒有抱著很大的期望。出席會議前亦曾經想過不知能聽懂多少 -- 說的不只是數學的內容，還有言語的問題。我在報名時看到會議的官方網頁，甚至是宣傳海報也全部是德文。雖然我已經學了數年德語，但我的程度還是只足以應付日常生活上的簡單溝通。後來拿到會議的場刊後，看到很多 abstract 也是以英語寫成的，才放心下來。雖然有一次還是碰到了一個「以英語寫 abstract，以德語講解」的 seminar，但當他開始了不久，看到了我這個「黑頭人」坐在那裡，便識趣地自動「轉台」。（話說回來，曾經有很多人問我在德國讀書是不是一定要懂德文，我現在可以肯定的告訴你，對於研究生來說，答案是不。）
既然是一個數學會議，就應該和大家分享一點點和數學有關的東西吧。（很抱歉在這裡只能很大概的談一談。）在我聽得懂而又比較有趣的 seminar 之中，有一個是關於求 small Ramsey numbers 的。眾所周知，求 Ramsey numbers 是一個非常困難的問題，縱然是一些很小的 Ramsey numbers 亦然（詳見數學資料庫筆記 http://db.math.ust.hk/notes_download/elementary/combinatorics/dc_D7.pdf）。這位學者嘗試以一個新的角度去解決這問題。他的方法大概是在為一個圖（graph）的邊（edge）填上紅藍兩色前，先揀選一些特別的邊來填上紫色（因他觀察到這些邊對結果影響不大）。這樣他便將需要考慮的可能性大大減少。
後記
雖然學術會議主要是提供一個學術交流的機會，但它同時亦帶來一個旅遊的藉口。故此，要是某學術會議是在一個著名的城市裡舉辦的話，那它的費用便會被調得特別高呢！
出席學術會議亦可能成為一些不負責任的教授用來「逃課」的藉口。我便聽說過曾經有一位教授在某學期裡三分之一的時間都去了「開會」，而他所授的課就不斷地要別人來接替！
剛於 11 月中去了一個組合數學的會議（全名為 Kolloquium ueber Kombinatorik）。雖然我只是剛「開學」，談不上有甚麼研究可以發表，但因我的 supervisor 是主辦者之一，所以便去了「捧場」。
這是我第一次出席學術會議，而我這個「大鄉里」亦在報名時擺了一個烏龍 -- 在填報資料時，我在「地址」一欄很自然地填了我的住址。後來才發現原來場刊是會將參加者的地址刊登出來，故我們應填上所屬大學或研究所的地址！由於「填錯」了地址，我的個人資料在一眾參加者當中就顯得格格不入（英文可以說成「unprofessional」）。
這次會議在 Magdeburg 舉行，是柏林以西的一個小鎮。由於這次只是去「sit 會」，故也沒有抱著很大的期望。出席會議前亦曾經想過不知能聽懂多少 -- 說的不只是數學的內容，還有言語的問題。我在報名時看到會議的官方網頁，甚至是宣傳海報也全部是德文。雖然我已經學了數年德語，但我的程度還是只足以應付日常生活上的簡單溝通。後來拿到會議的場刊後，看到很多 abstract 也是以英語寫成的，才放心下來。雖然有一次還是碰到了一個「以英語寫 abstract，以德語講解」的 seminar，但當他開始了不久，看到了我這個「黑頭人」坐在那裡，便識趣地自動「轉台」。（話說回來，曾經有很多人問我在德國讀書是不是一定要懂德文，我現在可以肯定的告訴你，對於研究生來說，答案是不。）
既然是一個數學會議，就應該和大家分享一點點和數學有關的東西吧。（很抱歉在這裡只能很大概的談一談。）在我聽得懂而又比較有趣的 seminar 之中，有一個是關於求 small Ramsey numbers 的。眾所周知，求 Ramsey numbers 是一個非常困難的問題，縱然是一些很小的 Ramsey numbers 亦然（詳見數學資料庫筆記 http://db.math.ust.hk/notes_download/elementary/combinatorics/dc_D7.pdf）。這位學者嘗試以一個新的角度去解決這問題。他的方法大概是在為一個圖（graph）的邊（edge）填上紅藍兩色前，先揀選一些特別的邊來填上紫色（因他觀察到這些邊對結果影響不大）。這樣他便將需要考慮的可能性大大減少。
後記
雖然學術會議主要是提供一個學術交流的機會，但它同時亦帶來一個旅遊的藉口。故此，要是某學術會議是在一個著名的城市裡舉辦的話，那它的費用便會被調得特別高呢！
出席學術會議亦可能成為一些不負責任的教授用來「逃課」的藉口。我便聽說過曾經有一位教授在某學期裡三分之一的時間都去了「開會」，而他所授的課就不斷地要別人來接替！
2007年12月7日 星期五
對數（logarithm）練習題
某位老師在課堂上跟學生討論以下一道關於對數（logarithm）的練習題：
設 log 2 = a、log 3 = b、log 7 = c，把以下各項以 a、b 和 c 表示。
(a) log 8
(b) log √2
(c) log 70
(d) log 105
小明：不是要以「a、b 和 c」表示嗎？只用了 a，沒有用 b 和 c 也可以嗎？
老師：可以的，不必 a、b、c 全部使用啊。
小明：但題目要求我們用 a、b 和 c 表示，多了個「3」也可以嗎？
老師：可以，因為 3a 可以看成 a + a + a 嘛。
老師：好，再看看 (b) 和 (c)。這兩題都不難，小芬，你出來做給大家看看吧。
小芬：（在白板上寫道……）
log √2 = log 21/2 = 1/2 log 2 = a/2
log 70 = log (7x10) = log 7 + log 10 = c+1
老師：對了，做得很好……
小明：不是只能以 a、b 和 c 表示嗎？答案中多了些「/2」和「+1」啊！
老師：可以，正如之前 3a 可以看成 a + a + a，這裡 a/2 和 c+1 可以看成……
小明：可以看成甚麼？
老師：……嗯……對 a、b 和 c 乘上或加上一些常數是可以的。
小明：甚麼是常數？
老師：常數英文叫 constant，就是沒 a、b 和 c 的實數吧……
小明：但為甚麼可以乘上或加上常數？
老師：凡是題目說「以 a、b 和 c 表示」都是可以的……
老師：好，小明，不如你出來試試 (d) 吧。
小明：（在白板上寫道……）
log 105 = log (3x5x7) = log 3 + log 5 + log 7 = b + log 5 + c
老師：不對呢，這個 log 5 應該變成 log (10/2) = log 10 - log 2 = 1 - a 才對。
小明：為甚麼不對？你剛才不是說可以不必 a、b、c 全部使用，也可以加上常數嗎？
老師：是啊……
小明：這裡 log 5 不就是個常數嗎？
老師：不可以這樣寫的，log 5 必須變成 1 - a 才成。
小明：+log 5 和 +1 都是常數，為何後者可以用前者卻不能？
老師：嗯……這個……你考試時答 log 5 是不會給分的。
小明：那到底錯了些甚麼？
老師：總之就不可以這樣答……這樣答沒分的……
當然，「以 a、b 和 c 表示」這一類的題目的意義一般都不太清晰，我們只能靠「common sense」來推斷「立法原意」。事實上，並不是所有這類題目的答案都是 a、b、c 的 rational function 的，例如：如果題目是「以 a 表示兩條直角邊均為 a 的等腰直角三角形的周界」的話，答案便是 (2 + √2) a 了。說到底，如果在考試中出現這樣題目的話，考生最終也得「推敲 marking scheme」呢。
設 log 2 = a、log 3 = b、log 7 = c，把以下各項以 a、b 和 c 表示。
(a) log 8
(b) log √2
(c) log 70
(d) log 105
老師：先看看 (a)，這個很簡單。因為 8 = 23，所以 log 8 = log 23 = 3 log 2 = 3a。
小明：不是要以「a、b 和 c」表示嗎？只用了 a，沒有用 b 和 c 也可以嗎？
老師：可以的，不必 a、b、c 全部使用啊。
小明：但題目要求我們用 a、b 和 c 表示，多了個「3」也可以嗎？
老師：可以，因為 3a 可以看成 a + a + a 嘛。
老師：好，再看看 (b) 和 (c)。這兩題都不難，小芬，你出來做給大家看看吧。
小芬：（在白板上寫道……）
log √2 = log 21/2 = 1/2 log 2 = a/2
log 70 = log (7x10) = log 7 + log 10 = c+1
老師：對了，做得很好……
小明：不是只能以 a、b 和 c 表示嗎？答案中多了些「/2」和「+1」啊！
老師：可以，正如之前 3a 可以看成 a + a + a，這裡 a/2 和 c+1 可以看成……
小明：可以看成甚麼？
老師：……嗯……對 a、b 和 c 乘上或加上一些常數是可以的。
小明：甚麼是常數？
老師：常數英文叫 constant，就是沒 a、b 和 c 的實數吧……
小明：但為甚麼可以乘上或加上常數？
老師：凡是題目說「以 a、b 和 c 表示」都是可以的……
老師：好，小明，不如你出來試試 (d) 吧。
小明：（在白板上寫道……）
log 105 = log (3x5x7) = log 3 + log 5 + log 7 = b + log 5 + c
老師：不對呢，這個 log 5 應該變成 log (10/2) = log 10 - log 2 = 1 - a 才對。
小明：為甚麼不對？你剛才不是說可以不必 a、b、c 全部使用，也可以加上常數嗎？
老師：是啊……
小明：這裡 log 5 不就是個常數嗎？
老師：不可以這樣寫的，log 5 必須變成 1 - a 才成。
小明：+log 5 和 +1 都是常數，為何後者可以用前者卻不能？
老師：嗯……這個……你考試時答 log 5 是不會給分的。
小明：那到底錯了些甚麼？
老師：總之就不可以這樣答……這樣答沒分的……
其實「以 a、b 和 c 表示」在本題中隱含了「寫成 a、b、c 的 rational function」的意思，不然的話學生大可以答 log 8 = log 8，不喜歡的可答 log 8 = a - a + log 8。由於 log 2、log 3 和 log 7 是 「linearly independent over Q」的，因此答案具唯一性。當然，這不容易給學生解釋呢！
當然，「以 a、b 和 c 表示」這一類的題目的意義一般都不太清晰，我們只能靠「common sense」來推斷「立法原意」。事實上，並不是所有這類題目的答案都是 a、b、c 的 rational function 的，例如：如果題目是「以 a 表示兩條直角邊均為 a 的等腰直角三角形的周界」的話，答案便是 (2 + √2) a 了。說到底，如果在考試中出現這樣題目的話，考生最終也得「推敲 marking scheme」呢。
2007年12月1日 星期六
培正數學邀請賽：最新消息
培正數學邀請賽的學校報名期將於 12 月 8 日（星期六）下午 5 時截止，有意參賽的同學請向就讀學校的數學老師查詢。
獲學校提名參賽的同學應提供正確的個人資料予老師報名，否則可能不獲參賽資格。老師輸入報名學生的資料時請特別注意以下事項：
獲學校提名參賽的同學應提供正確的個人資料予老師報名，否則可能不獲參賽資格。老師輸入報名學生的資料時請特別注意以下事項：
- 報名參加的組別必須與就讀年級相符。
- 必須提供正確的電郵地址。不同的參賽學生必須填寫不同的電郵地址。
- 必須填寫中文姓名，或選擇「沒有中文名」一項。
- 英文的「姓」和「名」不要倒轉，而且必須和身份證上的名字相同。
- 大會稍後會透過電郵要求參賽同學核實個人資料，屆時必須小心核對。
2007年11月27日 星期二
輸掉比勝出有利？
世界盃外圍賽
2010 年世界盃外圍賽便抽籤了。足球強國大多於歐洲和南美洲，而南美洲的外圍賽是最簡單的主客制雙循環賽事（即任何兩隊都會以主場和作客比賽各一場），不用抽籤分組，因此抽籤的焦點都落在歐洲 53 隊的分組情況。歐洲區將有 13 隊出線 2010 年世界盃決賽周。這 13 隊的產生辦法如下：
- 53 隊分為 9 組，其中 8 組 6 隊， 1 組 5 隊。每組都進行主客制雙循環賽事，各組首名出線決賽周；
- 9 組次名當中，成績較好的 8 隊會配成 4 對以主客制對賽 2 次，每對裏的勝出者出線決賽周。（最差的次名隊伍將自動出局。）
最差次名？
對數字敏感的讀者可能會發現上述賽制有個小問題：怎樣決定「最差次名」？如果各組隊數相同，我們還可以直接比較它們的分數。可是現在其中一組少了一隊呢，怎辦？放心，國際足協不會讓賽制留下這麼大的缺口。規則裏規定，排列各組次名時，擁有 6 隊的組別只計算與小組次名與小組首名、第 3 名、第 4 名和第 5 名的對賽分數，與第 6 名對賽所得的分數則忽略不計。因此，每隊小組次名都只計算 8 場比賽，問題似乎解決了。（當然，同分時另有決定準則，但這與本文主題太遠，在此略過。）
令人尷尬的賽果
實情真的如此嗎？非也。這個解決方法暗藏一個漏洞。這漏洞不易出現，但出現時可非常尷尬。原來它可能衍生某隊輸掉球賽比勝出更有利的情況！以下的就是這樣的尷尬情況：
假設某組有 6 隊 A、B、C、D、E 和 F。他們共需比賽 10 輪，現假設首 9 輪的成績和積分榜如下（勝出 3 分，賽和 1 分，輸掉則 0 分）：
|
|
第 10 輪比賽是 A 對 E、B 對 F 和 C 對 D。暫時 B 對 E 兩戰兩敗，但 B 對 F 卻一戰一勝，另有一戰在第 10 輪。從以下的分析，我們會發現 B 隊輸掉最後的比賽會比賽和或勝出有利！
賽果分析
首先，我們不難發現無論第 10 輪賽果如何，首名必為 A 隊，次名必為 B 隊。而第 6 名則取決於 A 對 F 及 B 對 E 的結果，C 對 D 的賽果已無傷大雅。本來組內名次已定，但誰是第 6 名卻成為計算 B 隊的「次名成績」的關鍵。
現列舉各種可能的情況如下：
- 情況一：E 隊擊敗 A 隊。
此時第 6 名是 F 隊。因為計算次名時，與第 6 名對賽的成績不算在內，所以無論 B 隊贏、和、輸，B 對 F 的賽果都不予計算，其「次名成績」皆為 4 勝 1 和 3 負，得 13 分。 - 情況二：A 隊擊敗 E 隊。
此時如果 B 隊擊敗或賽和 F 隊，第 6 名則為 F 隊。與情況一相似，B 隊贏、和、輸皆得 13 分（4 勝 1 和 3 負）。但如果 B 隊敗給 F 隊，情況便很不同了。此時 E 隊才是第 6 名，因此 B 和 E 之間的對賽將忽略不計。由上表可知，B 兩敗於 E，而對 F 則一勝一敗。B 隊敗給 F 隊後，B 對 E 的兩場敗績將不予計算，但卻保留了 B 對 F 的一勝一負成績。因此這反而令 B 隊的「次名成績」提升至 5 勝 1 和 2 負，得 16 分。 - 情況三：A 隊與 E 隊賽和。
如果 B 隊擊敗 F 隊，這便與情況一相同，B 隊的「次名成績」皆為 4 勝 1 和 3 負，得 13 分；如果 B 隊輸給 F 隊，則 E 和 F 同得 9 分，需要以其他方法（如對賽成績、得失球差等）排名。若 F 隊的同分排名條件優於 E 隊，情況便與情況二相同，B 隊的「次名成績」提升至 5 勝 1 和 2 負，得 16 分。否則，若 F 隊仍敬陪末席，這便與情況一相同，B 隊的「次名成績」皆為 4 勝 1 和 3 負，得 13 分。
結論：輸掉最有利！
綜合上述三個情況，我們可得知 B 隊敗給 F 隊永不會令其「次名成績」下降，反而在某些情況下（情況二和情況三的第二部分）有利！這寶貴的 3 分可能使 B 隊不用成為最差次名而出局呢！假如第 10 輪賽事前真的出現這樣的怪事，可不非常尷尬嗎？次名隊伍會應該故意輸掉球賽嗎？
2007年11月22日 星期四
數學資料庫 網站資源創作比賽
過去三星期大忙特忙，第一樣是因為ACM ICPC Regional Contest，第二樣就是數學資料庫的網站資源創作比賽。2004/05的徵文比賽，2005/06的徵文及漫畫比賽，到近兩屆的網站資源創作比賽，都是每年數學資料庫的重頭戲，目的就是希望學生自發去創作各樣數學的文章、遊戲、資源，提高你們對數學的興趣並擴闊在數學方面的視野，同時推廣課外學習數學。既是MD每年的重頭戲，你們又知道我們的成員都為比賽出過不少心力（我更處男下海，拋開以往Arts and Design從未高過70分兼平均分低於50分的心理包袱，親自設計poster！），你唔係唔參加呀？！
參賽資格：所有香港全日制中學生皆可參加（「數學資料庫」成員除外）。比賽分初中組和高中組，學生可選擇個人參賽或團體參賽。團體參賽每組最多六人。
作品要求：參賽者可創作任何能以網絡形式發放的作品，包括文章、網誌小品、書評、詩詞、故事、漫畫、短片、數學遊戲設計、遊戲程式等等，亦可在同一作品中融合不同形式的創作。
截止時間：2008年2月29日（星期五）下午五時
獎項：金、銀、銅獎和特別獎的獎品如下：
特別獎： 500 元書券 及 特別大獎一份
金獎： 300 元書券 及 精美禮品一份
銀獎： 200 元書券 及 精美禮品一份
銅獎： 100 元書券 及 精美禮品一份
若想知道其他詳情，請按此進入比賽網頁。
參賽資格：所有香港全日制中學生皆可參加（「數學資料庫」成員除外）。比賽分初中組和高中組，學生可選擇個人參賽或團體參賽。團體參賽每組最多六人。
作品要求：參賽者可創作任何能以網絡形式發放的作品，包括文章、網誌小品、書評、詩詞、故事、漫畫、短片、數學遊戲設計、遊戲程式等等，亦可在同一作品中融合不同形式的創作。
截止時間：2008年2月29日（星期五）下午五時
獎項：金、銀、銅獎和特別獎的獎品如下：
特別獎： 500 元書券 及 特別大獎一份
金獎： 300 元書券 及 精美禮品一份
銀獎： 200 元書券 及 精美禮品一份
銅獎： 100 元書券 及 精美禮品一份
若想知道其他詳情，請按此進入比賽網頁。
2007年11月21日 星期三
A mysterious induction
Problem
In a class there are 3n students. For a student x, let d(x) denote the number of friends of x in the class*. Suppose that
(1) the maximum value of d(x) is 4;
(2) if x is a friend of y, then d(x)+d(y)<7;
(3) no four students are friends of each other;
(4) no three students have three other common friends**.
Show that we can split the 3n students into 3 classes (say, A, B, C) of n students such that no friends are in the same class.
* If x is a friend of y, then y is a friend of x.
** This means there do not exist distinct a, b, c, x, y, z such that x, y, z are all friends of a, b, c.
Solution
(0) Assume the statement is false. Consider a counterexample with the smallest n.
By (1), assume a student v has friends w1, w2, w3 and w4. By (2), each of w1, w2, w3 and w4 has at most one friend other than v, and call them u1, u2, u3 and u4 (if exist). We shall divide all possibilities into four cases, and show that in each case we can split the students as desired.
Case 1: Some u (say, u1) does not exist
First ignore v, w1 and w2. By (0), the remaining 3(n-1) students can be split into 3 classes of n-1 students each. Then
Same proof as Case 1
Case 3: All u's exist and no u and w are equal, but some u's are equal (say u1=u2)
First ignore v, w1, w2, w3, w4 and u1. By (0), the remaining 3(n-2) students can be split into 3 classes of n-2 students each. Then
First ignore v, and temporarily regard w1 and w2 as one single student y1 (with friends u1 and u2), and w3 and w4 as one single student y2 (with friends u3 and u4). By (0), the resulting 3(n-1) students can be split into 3 classes of n-1 students each. Then
Reflections
Although not explicit, the above proof essentially makes use of the principle of mathematical induction, relying on smaller cases to prove a general case. This is one of the vast number of examples which show that mathematical induction can be a very powerful tool which can prove a huge variety of statements, other than the few typical examples in textbooks.
It is also worth to take note of the conditions given. It seems that the conditions (3) and (4) are never used in the proof. However, both of them are necessary conditions, as can be seen by the following examples:
In a class there are 3n students. For a student x, let d(x) denote the number of friends of x in the class*. Suppose that
(1) the maximum value of d(x) is 4;
(2) if x is a friend of y, then d(x)+d(y)<7;
(3) no four students are friends of each other;
(4) no three students have three other common friends**.
Show that we can split the 3n students into 3 classes (say, A, B, C) of n students such that no friends are in the same class.
* If x is a friend of y, then y is a friend of x.
** This means there do not exist distinct a, b, c, x, y, z such that x, y, z are all friends of a, b, c.
Solution
(0) Assume the statement is false. Consider a counterexample with the smallest n.
By (1), assume a student v has friends w1, w2, w3 and w4. By (2), each of w1, w2, w3 and w4 has at most one friend other than v, and call them u1, u2, u3 and u4 (if exist). We shall divide all possibilities into four cases, and show that in each case we can split the students as desired.
Case 1: Some u (say, u1) does not exist
First ignore v, w1 and w2. By (0), the remaining 3(n-1) students can be split into 3 classes of n-1 students each. Then
- put v into a class (say, A) to which w3 and w4 do not belong;
- put w1 and w2 into classes B and C respectively.
Same proof as Case 1
Case 3: All u's exist and no u and w are equal, but some u's are equal (say u1=u2)
First ignore v, w1, w2, w3, w4 and u1. By (0), the remaining 3(n-2) students can be split into 3 classes of n-2 students each. Then
- put v and u1 into some class (say A) so that u1 (who has at most 2 friends other than w1 and w2) does not meet his friends;
- put w3 (who has at most 1 friend other than v) into some class other than A (say B) so that he does not meet his friends, and put w1 into the remaining class (C in this case);
- repeat the above process for w4 and w2.
First ignore v, and temporarily regard w1 and w2 as one single student y1 (with friends u1 and u2), and w3 and w4 as one single student y2 (with friends u3 and u4). By (0), the resulting 3(n-1) students can be split into 3 classes of n-1 students each. Then
- in case y1 and y2 are in different classes (say A and B respectively), put w1 and w2 into class A, w3 and w4 into class B, and v into the remaining class (C in this case);
- in case y1 and y2 are in the same class (say A), put w1, w2 and w3 into class A, w4 into a class other than A to which u4 does not belong (say B), and v into the remaining class (C in this case).
Reflections
Although not explicit, the above proof essentially makes use of the principle of mathematical induction, relying on smaller cases to prove a general case. This is one of the vast number of examples which show that mathematical induction can be a very powerful tool which can prove a huge variety of statements, other than the few typical examples in textbooks.
It is also worth to take note of the conditions given. It seems that the conditions (3) and (4) are never used in the proof. However, both of them are necessary conditions, as can be seen by the following examples:
- Suppose there are 6 students (i.e. n=2) a, b, c, d, e, f with a, b, c, d being friends of each other and e, f being friends of each other. This satisfies (1), (2), (4) but not (3), and the statement does not hold.
- Suppose there are 3 male students a, b, c and 3 female students x, y, z (i.e. n=2) such that two students are friends if and only if they are of opposite gender. This satisfies (1), (2), (3) but not (4), and the statement does not hold.
2007年11月18日 星期日
從ACM回來的數學題（一）
不經不覺，已經接近一個月未在此作出更新。這種情況在今年八月提出建立「數學資料庫手記」時其實已經預料得到（事後孔明？）。自己認為，如果有一個人一年365天都是清清閒閒的話，他所寫的網誌大概也不會好看。而「數學資料庫手記」這麼精彩（難題：請在日常生活中找出比我這句更為硬銷的廣告），撰寫該網誌的成員年中有些時間比較忙也屬意料中事。
可幸的是，手記成立接近兩個月，充分發揮了"joint blog"的威力，大家你棒接我棒，令手記更新不斷。透過造訪紀錄看到，兩個月內手記已經得到一些老師和學生的推介。當然，我們的目標是令到更多更多的老師和學生認識「數學資料庫」和「數學資料庫手記」，充分利用兩個網站內的數學資源，好好的認識課程以外數學有趣和嚴謹的一面。
那麼我在過去一個月忙些甚麼呢？其中有七天，我到了南韓首爾和越南Danang參加ACM/ICPC，全寫為Association of Computing Machinery的International Collegiate Programming Contest，簡單點說就是以大學為單位的電腦編程競賽。每年的題目雖然都以Computer Science的題目為主，但不時亦會加插一些數學題。今天先挑在首爾見到的一條簡單「數學題」說說。
題目是這樣的：有一個 2 x n 的tag，有很多方法用 1 x 2、 2 x 1 和 2 x 2 的小塊去把它密舖。這些 2 x n 的tag可透過閱讀條碼機閱讀，從而確認身份。可是，用者可能將這個tag旋轉了180o。因此閱讀條碼機認為一個2 x n 的tag和這個tag旋轉了180o後的2 x n tag是一樣的。舉個例子，以下兩個tags是被認為一樣的：
而程式的工作就是輸入n後輸出不同的tags。
解題的方向分幾步，第一步就是先不考慮旋轉，數有多少個tags。考慮2 x n的tag右上角的正方形，它必然會被覆蓋，而覆蓋它的可能是 1 x 2 、 2 x 1 或者 2 x 2的小塊。若它是被 1 x 2的小塊覆蓋，那麼右下角的正方形也一定是被 1 x 2的小塊覆蓋，那麼餘下的就是一個 2 x (n-2)的tag。同理若右上角的正方形被 2 x 2的小塊覆蓋，餘下的也是一個 2 x (n-2)的tag。若右上角的正方形是被 2 x 1的小塊覆蓋，餘下的則是一個 2 x (n-1)的tag。因此，若定義Ck為（不考慮旋轉時）2 x k的tag不同的覆蓋方法數目，則有遞推關係
Ck = Ck-1 + 2Ck-2
知道C1 = 1和C2 = 3後，我們就可以用電腦以O(n)時間找出Cn。當然，這個遞推關係你甚至可以找到C的closed form，方法可參考「數學資料庫」筆記 - 「數列與遞歸關係」第13至15頁（這次感覺不那麼「硬」了吧）。
第二步則是找出經過180o旋轉後沒有改變的2 x n tags的數目。我們定義Dn為符合這個條件的tags的數目。當k是奇數時，可以証明它中間的兩個正方形一定是被一個2 x 1的小塊覆蓋著。因要符合條件，這些tags的左邊 2 x (k-1)/2的sub-tag覆蓋方法會決定了右邊2 x (k-1)/2的sub-tag的覆蓋方法。因此，
Dk = C(k-1)/2
當k是偶數時，有點麻煩。考慮中間的4個正方形，因要符合旋轉後不變的條件，它的密舖方法有兩種可能。第一就是被兩個 1 x 2 的小塊覆蓋或被一個 2 x 2 的小塊覆蓋。第二就是沒有小塊橫跨左邊的 2 x k/2 和右邊的 2 x k/2 subtags。這樣考慮下，得
Dk = 2C(k/2)-1+Ck/2
當用電腦儲存Ck後，Dn可在O(n)時間內求得。
對於任意的n用O(n)時間得到Cn和Dn後，想一想就知道答案是Dn + (Cn - Dn)/2 = (Cn + Dn)/2。
下一次說說兩條在越南Danang見到的題目，一條關於質數，另一條竟然和group theory扯上關係！
可幸的是，手記成立接近兩個月，充分發揮了"joint blog"的威力，大家你棒接我棒，令手記更新不斷。透過造訪紀錄看到，兩個月內手記已經得到一些老師和學生的推介。當然，我們的目標是令到更多更多的老師和學生認識「數學資料庫」和「數學資料庫手記」，充分利用兩個網站內的數學資源，好好的認識課程以外數學有趣和嚴謹的一面。
那麼我在過去一個月忙些甚麼呢？其中有七天，我到了南韓首爾和越南Danang參加ACM/ICPC，全寫為Association of Computing Machinery的International Collegiate Programming Contest，簡單點說就是以大學為單位的電腦編程競賽。每年的題目雖然都以Computer Science的題目為主，但不時亦會加插一些數學題。今天先挑在首爾見到的一條簡單「數學題」說說。
題目是這樣的：有一個 2 x n 的tag，有很多方法用 1 x 2、 2 x 1 和 2 x 2 的小塊去把它密舖。這些 2 x n 的tag可透過閱讀條碼機閱讀，從而確認身份。可是，用者可能將這個tag旋轉了180o。因此閱讀條碼機認為一個2 x n 的tag和這個tag旋轉了180o後的2 x n tag是一樣的。舉個例子，以下兩個tags是被認為一樣的：
而程式的工作就是輸入n後輸出不同的tags。
解題的方向分幾步，第一步就是先不考慮旋轉，數有多少個tags。考慮2 x n的tag右上角的正方形，它必然會被覆蓋，而覆蓋它的可能是 1 x 2 、 2 x 1 或者 2 x 2的小塊。若它是被 1 x 2的小塊覆蓋，那麼右下角的正方形也一定是被 1 x 2的小塊覆蓋，那麼餘下的就是一個 2 x (n-2)的tag。同理若右上角的正方形被 2 x 2的小塊覆蓋，餘下的也是一個 2 x (n-2)的tag。若右上角的正方形是被 2 x 1的小塊覆蓋，餘下的則是一個 2 x (n-1)的tag。因此，若定義Ck為（不考慮旋轉時）2 x k的tag不同的覆蓋方法數目，則有遞推關係
知道C1 = 1和C2 = 3後，我們就可以用電腦以O(n)時間找出Cn。當然，這個遞推關係你甚至可以找到C的closed form，方法可參考「數學資料庫」筆記 - 「數列與遞歸關係」第13至15頁（這次感覺不那麼「硬」了吧）。
第二步則是找出經過180o旋轉後沒有改變的2 x n tags的數目。我們定義Dn為符合這個條件的tags的數目。當k是奇數時，可以証明它中間的兩個正方形一定是被一個2 x 1的小塊覆蓋著。因要符合條件，這些tags的左邊 2 x (k-1)/2的sub-tag覆蓋方法會決定了右邊2 x (k-1)/2的sub-tag的覆蓋方法。因此，
當k是偶數時，有點麻煩。考慮中間的4個正方形，因要符合旋轉後不變的條件，它的密舖方法有兩種可能。第一就是被兩個 1 x 2 的小塊覆蓋或被一個 2 x 2 的小塊覆蓋。第二就是沒有小塊橫跨左邊的 2 x k/2 和右邊的 2 x k/2 subtags。這樣考慮下，得
當用電腦儲存Ck後，Dn可在O(n)時間內求得。
對於任意的n用O(n)時間得到Cn和Dn後，想一想就知道答案是Dn + (Cn - Dn)/2 = (Cn + Dn)/2。
下一次說說兩條在越南Danang見到的題目，一條關於質數，另一條竟然和group theory扯上關係！
2007年11月17日 星期六
誰因定理被證明發愁？
數學裏有很多令數學家苦思數十載仍毫無頭緒的猜想。其中部分猜想更涉及多個數學範疇的核心問題，一旦被證明正確或錯誤，必會推動各相關範疇的發展。黎曼猜想 (Riemann hypothesis) 便是一例。因此，大部分數學家都應該希望猜想早日被證明。當然，這總有例外。例如，有些數學家的研究工作就是衝著該猜想而來的，假如猜想被別人證明了，自己的研究可能因此失去意義。就好像當年 Andrew Wiles 證明費瑪大定理 (Fermat's Last Theorem) 和 Grigori Perelman 證明龐加萊猜想 (Poincaré Conjecture) 後，同在試圖攻克猜想的數學家也許在暗暗發愁。本來我以為只有他們才有可能因定理被證明而發愁，但最近我才發現還有另外一種這樣的數學家。
有些猜想太難證明或否定，但數學家一般相信它應該是對的。因此，他們會先假設猜想正確，再基於這假定推演理論，並期望最後有人能證明猜想來填補證明裏的空白。這樣做的好處是數學發展不會因猜想的懸案而裹足不前，但壞處是一旦猜想錯誤，奠基於猜想上的理論便毫無意義。因此，有些數學家會嘗試在不假設猜想成立的前提下，重新證明一些本來建基於猜想的理論。日前我和一位教授閒聊。她的研究正是希望繞過黎曼猜想，證明一大堆數論的命題。她說，假如猜想被證明正確，她的研究便會變得毫無意義。（這是因為此時我們不用假設猜想了。）因此，她說猜想得證對數學界來說是好事，但心裏卻不希望它這麼早便被攻克－－最早也要在她退休後。
有些猜想太難證明或否定，但數學家一般相信它應該是對的。因此，他們會先假設猜想正確，再基於這假定推演理論，並期望最後有人能證明猜想來填補證明裏的空白。這樣做的好處是數學發展不會因猜想的懸案而裹足不前，但壞處是一旦猜想錯誤，奠基於猜想上的理論便毫無意義。因此，有些數學家會嘗試在不假設猜想成立的前提下，重新證明一些本來建基於猜想的理論。日前我和一位教授閒聊。她的研究正是希望繞過黎曼猜想，證明一大堆數論的命題。她說，假如猜想被證明正確，她的研究便會變得毫無意義。（這是因為此時我們不用假設猜想了。）因此，她說猜想得證對數學界來說是好事，但心裏卻不希望它這麼早便被攻克－－最早也要在她退休後。
2007年11月16日 星期五
區議會選舉
本星期日（11 月 18 日）就是區議會選舉的日子，已登記的選民有沒有打算一盡公民責任，投下神聖的一票呢？
這次選舉，全港共分成 405 個選區，每區選出一名議員。選民投票時，只可選擇一名議員，得票最高的候選人當選，票數相同時則以抽籤決定。這種制度叫「單議席單票制」，好處是簡單易明，投票和點票的程序都非常直接。
然而，這個制度也有其缺點。最明顯的缺點是當候選人超過兩名時，可能出現票源分薄效應。舉例說，某選區有 60% 選民支持政黨 A，40% 支持政黨 B。如果兩個政黨各派一人出選，政黨 A 的候選人將會勝出。可是政黨 A 中有兩人同時堅持參選，結果瓜分了 60% 選票，每人得票 30%，於是得票 40% 的政黨 B 候選人便「漁人得利」。
另一個缺點是如果大部分選區都有約 60% 選民支持政黨 A，40% 選民支持政黨 B，那麼政黨 B 的候選人將全軍覆沒，使得支持政黨 B 的選民在議會內沒有代表聲音。
要解決這些缺點的話，可以改為使用其他選舉制度，例如：
當然，這些制度較為複雜，而且也有其他問題。事實上，要找出一個完美的選舉制度是不可能的。這可不是一個哲理評論，而是一個數學證明的結果：美國數學家 K. Arrow 證明了著名的「Arrow's Impossibility Theorem」，大意是說不存在一個選舉制度，可以滿足我們所有的「合理期望」！
這次選舉，全港共分成 405 個選區，每區選出一名議員。選民投票時，只可選擇一名議員，得票最高的候選人當選，票數相同時則以抽籤決定。這種制度叫「單議席單票制」，好處是簡單易明，投票和點票的程序都非常直接。
然而，這個制度也有其缺點。最明顯的缺點是當候選人超過兩名時，可能出現票源分薄效應。舉例說，某選區有 60% 選民支持政黨 A，40% 支持政黨 B。如果兩個政黨各派一人出選，政黨 A 的候選人將會勝出。可是政黨 A 中有兩人同時堅持參選，結果瓜分了 60% 選票，每人得票 30%，於是得票 40% 的政黨 B 候選人便「漁人得利」。
另一個缺點是如果大部分選區都有約 60% 選民支持政黨 A，40% 選民支持政黨 B，那麼政黨 B 的候選人將全軍覆沒，使得支持政黨 B 的選民在議會內沒有代表聲音。
要解決這些缺點的話，可以改為使用其他選舉制度，例如：
當然，這些制度較為複雜，而且也有其他問題。事實上，要找出一個完美的選舉制度是不可能的。這可不是一個哲理評論，而是一個數學證明的結果：美國數學家 K. Arrow 證明了著名的「Arrow's Impossibility Theorem」，大意是說不存在一個選舉制度，可以滿足我們所有的「合理期望」！
2007年11月11日 星期日
趣題一則
版本 1
曾先生是 X 國的商人，他以 2012 元買入了一件貨品，並標價 2017 元出售。李先生以 2017 元向曾先生買入這件貨品，並以一張 10000 元鈔票付款，曾先生找回 7983 元。後來，曾先生發現那張 10000 元鈔票是偽鈔。問事件中曾先生損失多少？
版本 2
曾先生是 X 國的商人，他以 2012 元買入了一件貨品，並標價 2017 元出售。李先生以 2017 元向曾先生買入這件貨品，並以一張 10000 元鈔票付款。曾先生沒有零錢，於是到北面的錢莊把 10000 元鈔票兌成零錢後找回 7983 元給李先生。後來，錢莊發現那張 10000 元鈔票是偽鈔，於是向曾先生索取 10000 元賠償。問事件中曾先生損失多少？
版本 3
曾先生是 X 國的商人，他以 2012 元買入了一件貨品，並標價 2017 元出售。李先生以 2017 元向曾先生買入這件貨品，並以一張 10000 元鈔票付款，曾先生找回 7983 元。後來，曾先生發現那張 10000 元鈔票是偽鈔，李先生亦發現貨品是贗品。問事件中李先生/曾先生各自得益/損失多少？
曾先生是 X 國的商人，他以 2012 元買入了一件貨品，並標價 2017 元出售。李先生以 2017 元向曾先生買入這件貨品，並以一張 10000 元鈔票付款，曾先生找回 7983 元。後來，曾先生發現那張 10000 元鈔票是偽鈔。問事件中曾先生損失多少？
版本 2
曾先生是 X 國的商人，他以 2012 元買入了一件貨品，並標價 2017 元出售。李先生以 2017 元向曾先生買入這件貨品，並以一張 10000 元鈔票付款。曾先生沒有零錢，於是到北面的錢莊把 10000 元鈔票兌成零錢後找回 7983 元給李先生。後來，錢莊發現那張 10000 元鈔票是偽鈔，於是向曾先生索取 10000 元賠償。問事件中曾先生損失多少？
版本 3
曾先生是 X 國的商人，他以 2012 元買入了一件貨品，並標價 2017 元出售。李先生以 2017 元向曾先生買入這件貨品，並以一張 10000 元鈔票付款，曾先生找回 7983 元。後來，曾先生發現那張 10000 元鈔票是偽鈔，李先生亦發現貨品是贗品。問事件中李先生/曾先生各自得益/損失多少？
2007年11月5日 星期一
香港大學公開講座
日期：2007 年 11 月 23 日（星期五）
時間：下午 5 時 30 分
地點：香港大學 T1 演講廳
講者：蕭文強教授
講題：歐拉之道 -- 從十八世紀到廿一世紀
Euler and His Path -- from the 18th Century to the 21st Century
有關其他詳情及報名方法，請瀏覽 http://www.hku.hk/science/euler/index.html。
時間：下午 5 時 30 分
地點：香港大學 T1 演講廳
講者：蕭文強教授
講題：歐拉之道 -- 從十八世紀到廿一世紀
Euler and His Path -- from the 18th Century to the 21st Century
有關其他詳情及報名方法，請瀏覽 http://www.hku.hk/science/euler/index.html。
2007年11月2日 星期五
培正數學邀請賽：最新消息
第七屆培正數學邀請賽將於 2008 年 1 月 26 日（星期六）及 2008 年 3 月 8 日（星期六）舉行。現已接受學校報名，詳情請瀏覽比賽網頁 http://www.puichingcentre.edu.hk/pcimc/。
2007年10月29日 星期一
概率與「一擲千金」
相信大家都聽過「一擲千金」遊戲。最近，我在某討論區發現有關這遊戲的一則討論： 「到了最後，外間已開了二十四個箱，都不是三百萬。三百萬不是在參與者的箱就是在外間餘下唯一的箱，機會是一半一半嗎？當然不是，在參與者的箱的概率仍是二十六分之一，在外間的箱則是二十六分之二十五。」
大家同意這說法嗎？在讀下去之前不妨停下來先想一想。
我們先看看另一個電視遊戲節目。在遊戲中，參賽者需在三個寶箱中選一個。已知其中兩個寶箱是空的，選中另一個則可贏得名貴房車。參賽者選了一個寶箱後，主持人在餘下兩個寶箱中 打開一個空的寶箱（主持人知道房車的位置，而餘下兩個寶箱中最少一個是空的）。這時還剩下兩個寶箱，分別是參賽者選了的一個和餘下主持人沒有打開的一個。主持人給參賽者一次改變主意的機會，讓他改選餘下沒有打開的寶箱，那麼參賽者應否改變主意？
很多人都認為，餘下兩個寶箱中獎的機會都是二分之一。當然，懂得數學的人都知道參賽者應該改選餘下沒有打開的寶箱，因為那個寶箱中獎的機會其實是三分之二而不是二分之一。
這 對非數學人來說是很難接受的，他們一定會說「明明兩者機會均等，為何概率不是二分之一？」之類的說話。通常我會用以下方法來說服他們：在一副 52 張的紙牌中讓「參賽者」先選一張（選中黑桃 A 便中獎），然後我在餘下 51 張牌中打開 50 張不是黑桃 A 的牌（我會先看過確保不是黑桃 A 才打開），這時只剩下參賽者選的一張牌和我沒有打開的一張牌，然後我給他們機會改選後者，這樣的話一般人大概都會明白改選後者是較為明智的（事實上，後者 中獎的機會是 51/52），儘管他們可能仍是一頭霧水。
現在回到「一擲千金」的遊戲。26 個寶箱打開了 24 個後，三百萬的寶箱還沒有打開。那麼參賽者一開始選定的寶箱是三百萬寶箱的機會，是 1/26 嗎？表面上看，這跟之前所說的沒有兩樣，都是在 n 個選擇中先選一個，然後「打開」了 n-2 個，最後餘下參賽者原先選了的個和沒有被打開的一個。（以上三個情況分別對應於 n = 3, 52, 26。）然而，只要稍為分析一下，便知道「一擲千金」中的情況其實是不同的。假設餘下的兩個寶箱分別是一元和三百萬，則如果參賽者的寶箱是三百萬的概率真的是 1/26 的話，那麼同理參賽者的寶箱是一元的概率也應該是 1/26，則餘下的 12/13 機會去了哪裡？事實上，參賽者的寶箱是三百萬和一元的概率都是 1/2。
為甚麼「一擲千金」和之前的房車／紙牌遊戲不同呢？關鍵是那 n-2 個「不是房車／黑桃 A／三百萬」的東西是如何打開的。在房車／紙牌的例子中，是由主持人在知情的情況下打開的，但在「一擲千金」中，參賽者是在不知道寶箱內容的情況下打開的。事實上，在前兩者中，每次都可以打開 n-2 個「不是大獎」東西，但在「一擲千金」中，開了 24 個寶箱後仍未開出三百萬的機會只有 1/13 呢！
2007年10月24日 星期三
「自然對數」的符號
昨天在辦公室工作時，一位同學問我怎樣展開「IN (1 + x)」。我不加思索便告訴他「x + x2/2 + C」。怎料他說這不可能，我百思不得其解。後來他再說清楚後，我才發現他要的是「ln (1 + x)」（(1 + x) 的自然對數）的泰勒級數 (Taylor series)。可是他把自然對數的符號「ln」讀成「in」（音標為 /'in/），使我以為他想求 (1 + x) 的不定積分 (indefinite integral)。原來他一直以來都誤會了自然對數的符號的第一個字母是「i」。
這不是我第一次遇到的事。還記得唸中六時很多同學也這樣出錯，我只好不斷糾正他們，說這符號應讀成「natural log」（英文）。怎料在大學時這樣的錯誤仍在身邊偶然出現。假如我沒有推測錯誤，這個錯處是由平日的書本或計算機而來的。在數學書上，通常變數都會以斜體字母表示，而大部分常用的函數的符號都以正楷表示，如「sin x」、「cos x」、「exp x」等。這樣的慣例在香港學生慣用的科學計算機上（如 Casio fx-3600、fx-3650、fx-3900、fx-3950、Sharp EL5020 等）亦通用。可是自然對數的符號「ln」裏的「l」與大寫「I」太相似，甚至在部分字型裏更無法分辨。更壞的是「ln」的字母順序與「natural logarithm」的字首順序「nl」不同，才導致這樣的笑話。
其實我也不太明白為甚麼自然對數要寫成「ln」。根據史料記載，這個符號是一位 University of Berkeley 的美國教授 Irving Stringham (1847 - 1909) 在 1893 年出版的著作Uniplanar Algebra 首次使用（詳見這裏）。這本著作是用英語寫成的，為何他不把這符號按英語全寫的字首順序寫成呢？也許，當時德語才是數學界的共同語言，於是他便按德語的「logarithmus naturalis」作縮寫了。可惜網上有關 Stringham 的介紹太少，很難從他的寫作習慣推敲其原因。有人知道嗎？
這不是我第一次遇到的事。還記得唸中六時很多同學也這樣出錯，我只好不斷糾正他們，說這符號應讀成「natural log」（英文）。怎料在大學時這樣的錯誤仍在身邊偶然出現。假如我沒有推測錯誤，這個錯處是由平日的書本或計算機而來的。在數學書上，通常變數都會以斜體字母表示，而大部分常用的函數的符號都以正楷表示，如「sin x」、「cos x」、「exp x」等。這樣的慣例在香港學生慣用的科學計算機上（如 Casio fx-3600、fx-3650、fx-3900、fx-3950、Sharp EL5020 等）亦通用。可是自然對數的符號「ln」裏的「l」與大寫「I」太相似，甚至在部分字型裏更無法分辨。更壞的是「ln」的字母順序與「natural logarithm」的字首順序「nl」不同，才導致這樣的笑話。
其實我也不太明白為甚麼自然對數要寫成「ln」。根據史料記載，這個符號是一位 University of Berkeley 的美國教授 Irving Stringham (1847 - 1909) 在 1893 年出版的著作Uniplanar Algebra 首次使用（詳見這裏）。這本著作是用英語寫成的，為何他不把這符號按英語全寫的字首順序寫成呢？也許，當時德語才是數學界的共同語言，於是他便按德語的「logarithmus naturalis」作縮寫了。可惜網上有關 Stringham 的介紹太少，很難從他的寫作習慣推敲其原因。有人知道嗎？
2007年10月18日 星期四
圓周角是圓心角的兩倍的逆定理：解答
本文是《圓周角是圓心角的兩倍……的逆定理？》一文的續集。
「圓周角是圓心角的兩倍」這定理是可逆的，以下是其中一個逆定理的版本：
設 O 為某圓的圓心，B、C 為圓上的兩點。若 ∠BOC = 2∠BAC，則 A 也位於此圓的圓周上。（後記：此版本有誤，見文章的留言部分。）
證明這逆定理很簡單，只需用到原定理和「同弓形的圓周角（angles in the same segment）」定理即可，讀者不妨試試。
以上的版本是先固定圓心角，然後指出凡是圓心角的一半的皆是圓周角。我們可否先固定圓周角呢？考慮以下版本：
設 A、B、C 為某圓上的三點。若 ∠BOC = 2∠BAC，則 O 是這個圓的圓心。
很可惜，以上命題是錯的（只需考慮滿足 ∠BOC = 2∠BAC 的點 O 的軌跡）。要一個先固定圓周角的逆定理版本的話，就得加入一個條件：
設 A、B、C 為某圓上的三點。若 O 位於 BC 的垂直平分線上，且 ∠BOC = 2∠BAC，則 O 是這個圓的圓心。（後記：此版本有誤，見文章的留言部分。）
「圓周角是圓心角的兩倍」這定理是可逆的，以下是其中一個逆定理的版本：
設 O 為某圓的圓心，B、C 為圓上的兩點。若 ∠BOC = 2∠BAC，則 A 也位於此圓的圓周上。（後記：此版本有誤，見文章的留言部分。）
證明這逆定理很簡單，只需用到原定理和「同弓形的圓周角（angles in the same segment）」定理即可，讀者不妨試試。
以上的版本是先固定圓心角，然後指出凡是圓心角的一半的皆是圓周角。我們可否先固定圓周角呢？考慮以下版本：
設 A、B、C 為某圓上的三點。若 ∠BOC = 2∠BAC，則 O 是這個圓的圓心。
很可惜，以上命題是錯的（只需考慮滿足 ∠BOC = 2∠BAC 的點 O 的軌跡）。要一個先固定圓周角的逆定理版本的話，就得加入一個條件：
設 A、B、C 為某圓上的三點。若 O 位於 BC 的垂直平分線上，且 ∠BOC = 2∠BAC，則 O 是這個圓的圓心。（後記：此版本有誤，見文章的留言部分。）
2007年10月17日 星期三
偏序集（Partially ordered sets）
現時，香港政府的架構以「三司十二局」為骨幹，每個決策局均設一名局長和一名常任秘書長，之下再設副秘書長和助理秘書長多名，再之下還設有更多職級。基本上，這些「高級」的職位有著緊密的從屬關係：局長是常任秘書長的直屬上司、常任秘書長是副秘書長的直屬上司、副秘書長是助理秘書長的直屬上司。這就好像是數學上的全序集（totally ordered sets）-- 集合裏任何兩個元素都可以比較大小。
今天，政府公佈擴闊政治委任制的建議，在局長下增設副局長和政治助理，兩者與常任秘書長之間沒有從屬關係（詳見 http://www.news.gov.hk/tc/category/administration/071017/html/071017tc01006.htm）。這就「破壞」了之前提及的全序集，因為常任秘書長和副局長兩者的職級不能比較高低。數學上，這是一個偏序集（partially ordered set）-- 集合中有些元素可以比較大小，但亦有可能有些不能比較（incomparable -- 注意讀音）的元素。
偏序集的「大小關係」（通常以「≥」表示）需滿足以下三個條件：
有沒有些不是全序集的偏序集呢？也有很多，例如，若 S 是有兩個或以上的元素的集合，P(S) 為 S 的冪集（power set），即 S 的所有子集（subsets）的集合，並對 P(S) 中的元素 X、Y 定義 Y ≥ X 當且僅當 X 是 Y 的子集，那麼 P(S) 便是偏序集，然而它是不全序集。（例如：若 S = {1,2}，那麼 P(S) = {Φ, {1}. {2}. {1,2}}，其中 {1, 2} ≥ Φ、{1,2} ≥ {1}、{1,2} ≥ {2}、{1} ≥ Φ、{2} ≥ Φ，但 {1} 和 {2} 不能比較大小。）
值得注意的一點是全序集和偏序集包括本身和比較大小的關係「≥」。改變「≥」的定義後所得的會被視為另一個全序集或偏序集。在以上例子中，若對 P(S) 中的元素 X、Y 改為定義 Y ≥ X 當且僅當 Y 的元素之和不小於 X 的元素之和，則 P(S) 會變成一個全序集呢！
今天，政府公佈擴闊政治委任制的建議，在局長下增設副局長和政治助理，兩者與常任秘書長之間沒有從屬關係（詳見 http://www.news.gov.hk/tc/category/administration/071017/html/071017tc01006.htm）。這就「破壞」了之前提及的全序集，因為常任秘書長和副局長兩者的職級不能比較高低。數學上，這是一個偏序集（partially ordered set）-- 集合中有些元素可以比較大小，但亦有可能有些不能比較（incomparable -- 注意讀音）的元素。
偏序集的「大小關係」（通常以「≥」表示）需滿足以下三個條件：
(1) 對偏序集中的任意元素 x，皆有 x ≥ x。全序集則需同時滿足「對偏序集中的任意元素 x 和 y，皆有 x ≥ y 或 y ≥ x」，即「任何兩個元素都可以比較大小」。全序集的例子很多，如實數集、所有英文字的集合（以字母順序比較大小）等。
(2) 若 x ≥ y 且 y ≥ x，則 x = y。
(3) 若 x ≥ y 且 y ≥ z，則 x ≥ z。
有沒有些不是全序集的偏序集呢？也有很多，例如，若 S 是有兩個或以上的元素的集合，P(S) 為 S 的冪集（power set），即 S 的所有子集（subsets）的集合，並對 P(S) 中的元素 X、Y 定義 Y ≥ X 當且僅當 X 是 Y 的子集，那麼 P(S) 便是偏序集，然而它是不全序集。（例如：若 S = {1,2}，那麼 P(S) = {Φ, {1}. {2}. {1,2}}，其中 {1, 2} ≥ Φ、{1,2} ≥ {1}、{1,2} ≥ {2}、{1} ≥ Φ、{2} ≥ Φ，但 {1} 和 {2} 不能比較大小。）
值得注意的一點是全序集和偏序集包括本身和比較大小的關係「≥」。改變「≥」的定義後所得的會被視為另一個全序集或偏序集。在以上例子中，若對 P(S) 中的元素 X、Y 改為定義 Y ≥ X 當且僅當 Y 的元素之和不小於 X 的元素之和，則 P(S) 會變成一個全序集呢！
2007年10月15日 星期一
外圍賽的出線問題－－為何沒有附加賽？
經過一年多的比賽後，歐洲國家盃的外圍賽戰況接近尾聲，體育雜誌和報章都開始討論各組機會最大的出線組合。與過去三屆歐洲國家盃外圍賽和三屆世界盃足球賽歐洲區外圍賽不同，今屆沒有附加賽，七組首次名共 14 隊出線由外圍賽出線決賽周（再另加主辦國瑞士及奧地利，共 16 國參賽）。但我卻認為不設附加賽是一種退步。
小型比賽不需要外圍賽，但歐洲國家盃卻是大型比賽。除兩個主辦國外，歐洲足協共有 50 個成員，如果全部都參加決賽周，比賽將會過多，並不切實際。因此我們需要以某些方式決定決賽周的參賽隊伍，這就是外圍賽。為保持決賽周的可觀性，合理的期望是從外圍賽出線的隊伍都是強隊。比較若干隊之間的強弱程度，最公平的方法當然是任何兩隊皆對賽，否則我們很難比較沒有對賽過的隊伍。這就是最常見的聯賽制度，如英超、德甲、西甲等都憑這種制度決出每屆的冠軍〔註一〕。可是如果歐洲足協要求所有成員參與一個大聯賽，即使是單循環的聯賽也要 25 輪比賽（雙循環則需 50 輪），賽事太多，根本沒可能在一年多的時間實行。當然，我們亦可以抽籤形式決定出線隊伍，簡單、方便、快捷。但這卻無視隊伍的強弱，減低了決賽周的重要性。
既然兩個極端都不行，我們唯有折衷，以分組比賽形式選出各組的強隊。由於設有根據往績而定的種子制度，分組後往績較好的隊伍通常都分散各組，不容易因同組而不能同時出線。分組作賽大幅減少比賽數量，又可使強隊從比賽中以其實力出線，一舉兩得。儘管如此，分組仍有其缺點。以今屆歐洲國家盃外圍賽為例，除主辦國瑞士和奧地利外的 50 個成員共分為 7 組（1 組 8 隊和 6 組 7 隊），每組首次名出線決賽周。換言之，因為蘇格蘭、法國和意大利同在 B 組，所以她們三隊必有最少一隊在外圍賽止步。可是純以外圍賽的表現計算，出局的隊伍可能僅比出線的隊伍略遜，但比其他小組次名（如 C 組的土耳其或挪威〔註二〕）表現更佳。我們有沒有辦法增加分組作賽的彈性呢？答案就是附加賽。
以往三屆歐洲國家盃外圍賽都有附加賽。以 2000 年那屆為例〔註三〕，當年除主辦國荷蘭和比利時外，共 49 個成員需爭奪 14 個決賽周席位。外圍賽則分為 9 組（4 組 6 隊和 5 組 5 隊），各組首名及最佳小組次名〔註四〕直接出線，餘下 8 組次名則配為 4 對進行兩場附加賽，勝者出線。在附加賽制度下，每組出線的隊伍數量並不固定，可為 1 至 2 隊。即使某隊因成績僅稍遜於小組首名，仍可靠擊敗另一組小組次名出線。反之，較弱的小組次名卻可能因此緣盡決賽周。由此可見，附加賽制度為分組賽的限制微調，提高了出線組合的彈性，但又不會大幅增加賽事數量。我們可從以下的數字略見一斑：2000 年那屆的外圍賽共需 228 場比賽，出線組合共 27097031250 個（約 271 億），但今屆外圍賽共需 350 場比賽，出線組合卻只有 2401451388 個（約 24 億）。
為何不可以當年的模式設立外圍賽？這令人難以明白。
註一：聯賽制度牽涉計分，但如何計分才公平的問題離本文主旨太遠，另文再談。
註二：本文寫於 2007 年 10 月 15 日，外圍賽尚未完結，故 C 組次名純粹以當時的成績猜測。
註三：我不選擇以 2004 年該屆的外圍賽為例，原因是該屆的外圍賽共決出 15 隊出線隊伍（主辦國只有德國），出線隊伍多了，組合自然大增。因此這樣的比較不能顯示附加賽的重要性。
註四：如果在不同大小的組別裏決定最佳次名又可帶出另一個數學問題，另文再談。
小型比賽不需要外圍賽，但歐洲國家盃卻是大型比賽。除兩個主辦國外，歐洲足協共有 50 個成員，如果全部都參加決賽周，比賽將會過多，並不切實際。因此我們需要以某些方式決定決賽周的參賽隊伍，這就是外圍賽。為保持決賽周的可觀性，合理的期望是從外圍賽出線的隊伍都是強隊。比較若干隊之間的強弱程度，最公平的方法當然是任何兩隊皆對賽，否則我們很難比較沒有對賽過的隊伍。這就是最常見的聯賽制度，如英超、德甲、西甲等都憑這種制度決出每屆的冠軍〔註一〕。可是如果歐洲足協要求所有成員參與一個大聯賽，即使是單循環的聯賽也要 25 輪比賽（雙循環則需 50 輪），賽事太多，根本沒可能在一年多的時間實行。當然，我們亦可以抽籤形式決定出線隊伍，簡單、方便、快捷。但這卻無視隊伍的強弱，減低了決賽周的重要性。
既然兩個極端都不行，我們唯有折衷，以分組比賽形式選出各組的強隊。由於設有根據往績而定的種子制度，分組後往績較好的隊伍通常都分散各組，不容易因同組而不能同時出線。分組作賽大幅減少比賽數量，又可使強隊從比賽中以其實力出線，一舉兩得。儘管如此，分組仍有其缺點。以今屆歐洲國家盃外圍賽為例，除主辦國瑞士和奧地利外的 50 個成員共分為 7 組（1 組 8 隊和 6 組 7 隊），每組首次名出線決賽周。換言之，因為蘇格蘭、法國和意大利同在 B 組，所以她們三隊必有最少一隊在外圍賽止步。可是純以外圍賽的表現計算，出局的隊伍可能僅比出線的隊伍略遜，但比其他小組次名（如 C 組的土耳其或挪威〔註二〕）表現更佳。我們有沒有辦法增加分組作賽的彈性呢？答案就是附加賽。
以往三屆歐洲國家盃外圍賽都有附加賽。以 2000 年那屆為例〔註三〕，當年除主辦國荷蘭和比利時外，共 49 個成員需爭奪 14 個決賽周席位。外圍賽則分為 9 組（4 組 6 隊和 5 組 5 隊），各組首名及最佳小組次名〔註四〕直接出線，餘下 8 組次名則配為 4 對進行兩場附加賽，勝者出線。在附加賽制度下，每組出線的隊伍數量並不固定，可為 1 至 2 隊。即使某隊因成績僅稍遜於小組首名，仍可靠擊敗另一組小組次名出線。反之，較弱的小組次名卻可能因此緣盡決賽周。由此可見，附加賽制度為分組賽的限制微調，提高了出線組合的彈性，但又不會大幅增加賽事數量。我們可從以下的數字略見一斑：2000 年那屆的外圍賽共需 228 場比賽，出線組合共 27097031250 個（約 271 億），但今屆外圍賽共需 350 場比賽，出線組合卻只有 2401451388 個（約 24 億）。
為何不可以當年的模式設立外圍賽？這令人難以明白。
註一：聯賽制度牽涉計分，但如何計分才公平的問題離本文主旨太遠，另文再談。
註二：本文寫於 2007 年 10 月 15 日，外圍賽尚未完結，故 C 組次名純粹以當時的成績猜測。
註三：我不選擇以 2004 年該屆的外圍賽為例，原因是該屆的外圍賽共決出 15 隊出線隊伍（主辦國只有德國），出線隊伍多了，組合自然大增。因此這樣的比較不能顯示附加賽的重要性。
註四：如果在不同大小的組別裏決定最佳次名又可帶出另一個數學問題，另文再談。
2007年10月12日 星期五
圓周角是圓心角的兩倍……的逆定理？
大家知道，幾何裏很多定理的逆定理都是成立的，以下是一些簡單的例子：
畢氏定理：若 ∠BAC = 90o，則 AB2 + AC2 = BC2。
畢氏定理的逆定理：若 AB2 + AC2 = BC2，則 ∠BAC = 90o。
半圓角定理：若 BC 是一個圓的直徑，A 是圓周上的一點，則 ∠BAC = 90o。
半圓角定理的逆定理：若 A、B、C 是一個圓周上的三點且 ∠BAC = 90o，則 BC 是圓的直徑。
那麼以下定理又如何？
圓心角是圓周角的兩倍：若 A、B、C 是一個圓周上的三點且 O 是圓心，則 ∠BOC = 2∠BAC。
以上定理的逆定理是甚麼？它是否成立？大家先想想，答案下回揭曉。
畢氏定理：若 ∠BAC = 90o，則 AB2 + AC2 = BC2。
畢氏定理的逆定理：若 AB2 + AC2 = BC2，則 ∠BAC = 90o。
半圓角定理：若 BC 是一個圓的直徑，A 是圓周上的一點，則 ∠BAC = 90o。
半圓角定理的逆定理：若 A、B、C 是一個圓周上的三點且 ∠BAC = 90o，則 BC 是圓的直徑。
那麼以下定理又如何？
圓心角是圓周角的兩倍：若 A、B、C 是一個圓周上的三點且 O 是圓心，則 ∠BOC = 2∠BAC。
以上定理的逆定理是甚麼？它是否成立？大家先想想，答案下回揭曉。
2007年10月11日 星期四
把魔法放進那百寶袋
有一位朋友，從五月開始準備博士學位的實數分柝資格考試，九月底應考了。從試場一出來，劈面就說:「四道問題我只差不多完成一道。我想我不能及格了。」
老實說，這個實數分析的考試，對很多人來講，相當難。但四個多月的準備時間實在是很充裕了。那份試卷我看過，對比往年，不算難。四道做不完一題，是遜了一點。我的朋友為何會考得這樣差?
想了一想，是他的溫習方式出了問題。著名數學家陶哲軒說過，學習數學，有如把不同的魔法道具放進自己的百寶袋裏，往後能隨時隨地、隨心所欲的拿出來運用。我很同意。我朋友他把考試範圍的那幾課都差不多翻爛了;定理背得爛熟，那個定理在那一頁都說得出;這許多的舊試卷他不是全看過了都看了九成。然而，這有個屁用!考試還不是過不了?
他就是沒有把魔法道具放進百寶袋裏!他看懂了書內的定理，卻沒掌握到那些定理的妙用。他做舊試卷，看看問題，想一會想不通，或看答案，或問我。看明白了答案，就當自己明了, 卻沒吸收到答案中的精髓:解題的技巧。寶劍雖在，但他沒學懂怎樣發揮其威力。看著新的問題，他就一籌莫展了。
多做練習是掌握運用定理與技巧的不二法門。自己一手一腳把答案做出來，印象最深刻。有題目不懂，看答案不打緊，看明白後過一段時間，不妨拿那問題再做，你或會發覺，還是有些地方未攪明白。當你能隨時隨地把那個問題想通一遍，恭喜你，你已經把一些魔法放進了自己的百寶袋了。
老實說，這個實數分析的考試，對很多人來講，相當難。但四個多月的準備時間實在是很充裕了。那份試卷我看過，對比往年，不算難。四道做不完一題，是遜了一點。我的朋友為何會考得這樣差?
想了一想，是他的溫習方式出了問題。著名數學家陶哲軒說過，學習數學，有如把不同的魔法道具放進自己的百寶袋裏，往後能隨時隨地、隨心所欲的拿出來運用。我很同意。我朋友他把考試範圍的那幾課都差不多翻爛了;定理背得爛熟，那個定理在那一頁都說得出;這許多的舊試卷他不是全看過了都看了九成。然而，這有個屁用!考試還不是過不了?
他就是沒有把魔法道具放進百寶袋裏!他看懂了書內的定理，卻沒掌握到那些定理的妙用。他做舊試卷，看看問題，想一會想不通，或看答案，或問我。看明白了答案，就當自己明了, 卻沒吸收到答案中的精髓:解題的技巧。寶劍雖在，但他沒學懂怎樣發揮其威力。看著新的問題，他就一籌莫展了。
多做練習是掌握運用定理與技巧的不二法門。自己一手一腳把答案做出來，印象最深刻。有題目不懂，看答案不打緊，看明白後過一段時間，不妨拿那問題再做，你或會發覺，還是有些地方未攪明白。當你能隨時隨地把那個問題想通一遍，恭喜你，你已經把一些魔法放進了自己的百寶袋了。
2-Dimensional Mathematical Induction
在我讀中學的年代，有一種證明方法叫「數學歸納法」（用「在我讀中學附加數的年代」而不是「現時的中學附加數」這一個phrase，是因為在課程不斷cut、cut、cut下，我怕連M.I.都cut了，那麼用「現時的中學附加數」在未來就變得不適用了……）。個人覺得這是一種美麗的方法。首先，它的最基本只涉及自然數。Kronecker說過：「上帝創造了自然數，其餘的一切才是人做的工作」，可以輔證一個proposition涉及自然數是最自然最美麗的事情。而最基本的由 n = k 去到 n = k+1 ，體驗了數學是由低做起，慢慢build up上去的系統的嚴謹。
最近製造一份教中四學生「證明方法」的筆記，忽發奇想，不如在筆記中說一些特別的數學歸納法形式。最自然的就是我當年讀的附加數textbook中（註1），有一種題目類似：Prove that 3n+13 * 7n+2 is divisible by 8 for all odd n.而接下來的，當然就是二維數學歸納法了。所謂二維數學歸納法，就是想證明P(m,n)對於所有正整數m,n都是正確的話，先證明P(1,n)對所有n均正確，然後假設P(k,n)正確再證明P(k+1,n)正確（註2）。
問題是，翻看純數的past paper，所有涉及二維數學歸納法的題目都涉及其他技巧，不太適合中四學生。於是便想想自己構造一條題目出來吧。苦思良久，竟然巧合地發現我最近在科大做TA的一個course功課的某道題目，竟然可以用來作二維數學歸納法的例子！
題目是這樣的：有一個 m X n 的棋盤，其中 m 和 n 均是奇數。假設左上角的格是白色的，而棋盤的格子是黑白相隔。證明當從棋盤中移走任意一個白色方格，餘下的棋盤可以用 1 x 2的長方形密鋪。
我發給學生的題解，可以看看這裏的第一頁。這是證明方法的另一種，叫構造法，在此就不多述了。而早兩日這樣無意間發現可以有另一種使用二維數學歸納法的證明，實在太開心了。
若讀者當中有中學生，可以嘗試一下寫下用二維數學歸納法的證明，享受一下另一種數學歸納法的美麗。
註1：我讀附加數是2001年的事，但我當時看的是一本1990年左右出版的附加數書（原因上面已經說了）。而讀純數時，老師派了一份"Past Paper結集"的筆記。我可以從筆記中看到九十年代、八十年代、甚至七十年代的past paper questions。到了後來，偶然自己在中學教奧林匹克數學，或從其他朋友聽見現時附加數沒有了甚麼甚麼甚麼（很多的甚麼），我可以說我見證著香港數學課程不斷刪減的事實。
註2：有許許多多其他的形式，這裏說一個便算了。
最近製造一份教中四學生「證明方法」的筆記，忽發奇想，不如在筆記中說一些特別的數學歸納法形式。最自然的就是我當年讀的附加數textbook中（註1），有一種題目類似：Prove that 3n+13 * 7n+2 is divisible by 8 for all odd n.而接下來的，當然就是二維數學歸納法了。所謂二維數學歸納法，就是想證明P(m,n)對於所有正整數m,n都是正確的話，先證明P(1,n)對所有n均正確，然後假設P(k,n)正確再證明P(k+1,n)正確（註2）。
問題是，翻看純數的past paper，所有涉及二維數學歸納法的題目都涉及其他技巧，不太適合中四學生。於是便想想自己構造一條題目出來吧。苦思良久，竟然巧合地發現我最近在科大做TA的一個course功課的某道題目，竟然可以用來作二維數學歸納法的例子！
題目是這樣的：有一個 m X n 的棋盤，其中 m 和 n 均是奇數。假設左上角的格是白色的，而棋盤的格子是黑白相隔。證明當從棋盤中移走任意一個白色方格，餘下的棋盤可以用 1 x 2的長方形密鋪。
我發給學生的題解，可以看看這裏的第一頁。這是證明方法的另一種，叫構造法，在此就不多述了。而早兩日這樣無意間發現可以有另一種使用二維數學歸納法的證明，實在太開心了。
若讀者當中有中學生，可以嘗試一下寫下用二維數學歸納法的證明，享受一下另一種數學歸納法的美麗。
註1：我讀附加數是2001年的事，但我當時看的是一本1990年左右出版的附加數書（原因上面已經說了）。而讀純數時，老師派了一份"Past Paper結集"的筆記。我可以從筆記中看到九十年代、八十年代、甚至七十年代的past paper questions。到了後來，偶然自己在中學教奧林匹克數學，或從其他朋友聽見現時附加數沒有了甚麼甚麼甚麼（很多的甚麼），我可以說我見證著香港數學課程不斷刪減的事實。
註2：有許許多多其他的形式，這裏說一個便算了。
2007年10月6日 星期六
笑話一則
小明：媽媽，老師今天派了上星期的數學測驗卷……
媽媽：為何這次測驗的表現這樣差？
小明：沒法子，其實題目我是懂的，但我很不小心，很多道題都乘漏了個 1。
媽媽：為甚麼會這樣？
小明：唉，沒辦法，我已經帶了兩部計算機，怎料同時壞了，所以只好用筆算，自然容易算錯了。
媽媽：兩部計算機同時壞了？情況怎樣？
小明：我也不知道。我想計 1 的平方根，輸入 1 後按開方，卻沒有反應，兩部計算機都是這樣子。
媽媽：那怎麼辦？有同學懂得修理嗎？
小明：我給小強嘗試替我修理，他試著按 1/x 鍵，也是沒有反應。
媽媽：之後呢？
小明：他按了重設鍵 AC，然後再按開方鍵，仍是沒有反應；再試按 1/x 鍵，就出現 error 了。
媽媽：那就是沒法修理了？
小明：是啊，你還是給我錢買兩部新的吧。
媽媽：為何這次測驗的表現這樣差？
小明：沒法子，其實題目我是懂的，但我很不小心，很多道題都乘漏了個 1。
媽媽：為甚麼會這樣？
小明：唉，沒辦法，我已經帶了兩部計算機，怎料同時壞了，所以只好用筆算，自然容易算錯了。
媽媽：兩部計算機同時壞了？情況怎樣？
小明：我也不知道。我想計 1 的平方根，輸入 1 後按開方，卻沒有反應，兩部計算機都是這樣子。
媽媽：那怎麼辦？有同學懂得修理嗎？
小明：我給小強嘗試替我修理，他試著按 1/x 鍵，也是沒有反應。
媽媽：之後呢？
小明：他按了重設鍵 AC，然後再按開方鍵，仍是沒有反應；再試按 1/x 鍵，就出現 error 了。
媽媽：那就是沒法修理了？
小明：是啊，你還是給我錢買兩部新的吧。
2007年9月30日 星期日
培正數學邀請賽：經典重溫（二）
第一屆（個人賽中三組第 19 題、中四組第 20 題）
董先生參加某國家的總統選舉，得票率（準確至小數點後一個位）為 66.6%。問董先生最少得到多少票？
本題是另一道看下去不難，卻很有深度的題目。表面上它只是一道百分率和近似值的問題，而要找到「66.6%」的例子亦很容易：666/1000 和 333/500 就是最簡單的情況。可是如何找出董先生的得票的最小值呢？
如果大家對數字有一定的敏感度的話，應該會發現 66.6% 和三分之二很接近，但 2/3 四捨五入至小數點後一位的話卻是 66.7%，跟題目不符。因此，董先生的得票應該「比三分之二少一點點」。這基本上也是大會題解背後的思路，大家不妨試試。
這道題是罕有沒有參賽者答對的題目之一。當然，從比賽的角度看這並非好事。然而題目事後卻引起了廣泛討論，有數學老師更想出了一些另類的解法，當中甚至跟表面看來毫不相干的 Pick's formula 扯上關係。這實在是數學其中一個最可愛的地方。
董先生參加某國家的總統選舉，得票率（準確至小數點後一個位）為 66.6%。問董先生最少得到多少票？
本題是另一道看下去不難，卻很有深度的題目。表面上它只是一道百分率和近似值的問題，而要找到「66.6%」的例子亦很容易：666/1000 和 333/500 就是最簡單的情況。可是如何找出董先生的得票的最小值呢？
如果大家對數字有一定的敏感度的話，應該會發現 66.6% 和三分之二很接近，但 2/3 四捨五入至小數點後一位的話卻是 66.7%，跟題目不符。因此，董先生的得票應該「比三分之二少一點點」。這基本上也是大會題解背後的思路，大家不妨試試。
這道題是罕有沒有參賽者答對的題目之一。當然，從比賽的角度看這並非好事。然而題目事後卻引起了廣泛討論，有數學老師更想出了一些另類的解法，當中甚至跟表面看來毫不相干的 Pick's formula 扯上關係。這實在是數學其中一個最可愛的地方。
2007年9月22日 星期六
2007年9月18日 星期二
培正數學邀請賽：經典重溫（一）
培正數學邀請賽已經舉辦六屆，六年來出現過不少有趣的題目，「培正數學邀請賽：經典重溫」系列會為大家重溫一下這些題目。
第一屆（個人賽中一組第 14 題、中二組第 9 題）
求最小的質數 p，使得 2002 - p 和 2002 + p 均為質數。
本題看下去不難，一個很自然的想法是代入 p = 2、3、5、7、……，看看有甚麼發現。可是即使很有耐性地試到 100 以上，似乎怎樣也找不到 p 使得 2002 - p 和 2002 + p 均為質數。若再細心觀察一下，不難發現（也不難證明）除 p = 3 外，任何的質數 p 皆會使得 2002 - p 或 2002 + p 的其中一個是 3 的倍數。當年的一名中一組參賽者，就以此在答題紙上長篇大論，指出題目有誤，因為他可以證明這樣的 p 根本不存在。當然，題目其實是沒有錯的（大家是否已經想到答案呢？），但那位中一的參賽者能寫出這樣的「證明」也殊不簡單，而他最後亦成為得獎者之一呢！
第一屆（個人賽中一組第 14 題、中二組第 9 題）
求最小的質數 p，使得 2002 - p 和 2002 + p 均為質數。
本題看下去不難，一個很自然的想法是代入 p = 2、3、5、7、……，看看有甚麼發現。可是即使很有耐性地試到 100 以上，似乎怎樣也找不到 p 使得 2002 - p 和 2002 + p 均為質數。若再細心觀察一下，不難發現（也不難證明）除 p = 3 外，任何的質數 p 皆會使得 2002 - p 或 2002 + p 的其中一個是 3 的倍數。當年的一名中一組參賽者，就以此在答題紙上長篇大論，指出題目有誤，因為他可以證明這樣的 p 根本不存在。當然，題目其實是沒有錯的（大家是否已經想到答案呢？），但那位中一的參賽者能寫出這樣的「證明」也殊不簡單，而他最後亦成為得獎者之一呢！
2007年9月14日 星期五
Card Trick Solution
開課後，很多莫明其妙的事情接腫而來，弄至一星期後才能更新這裏。
利用這個小特點，就可以將原本的二選一變成「一一對應」了。
說一說上次那個"trick"的解答吧。正所謂「無氈無扇，神仙難變」，「使者」和「神秘通天眼」不會有任何接觸，能夠令「神秘通天眼」猜到底牌的，當然就是「使者」放在桌上的四張牌。
一副紙牌有52隻。有玩過「鋤大D」或「橋牌」都應該知道不難為這52隻牌定一個次序（例如先比較數字，A > K > Q > J > 10 > 9 > ... > 2；同數字的就比較花，桃花 > 紅心 > 葵扇 > 磚）。
撇除在桌上的4隻牌後，餘下48隻。用這4隻牌做一個排列（permutation），可以有24個可能性，然後我們可以根據下表，知道「底牌」只有兩個可能（下圖左列的 4 代表4隻牌當中最大的牌； 1 代表4隻牌當中最小的牌）：
| 4隻牌的排序 | 代表「底牌」是餘下48張中的第n張牌。 |
|---|---|
| 1234 | 1,2 |
| 1243 | 3,4 |
| 1324 | 5,6 |
| 1342 | 7,8 |
| 1423 | 9,10 |
| 1432 | 11,12 |
| 2134 | 13,14 |
| 2143 | 15,16 |
| 2314 | 17,18 |
| 2341 | 19,20 |
| 2413 | 21,22 |
| 2431 | 23,24 |
| 3124 | 25,26 |
| 3142 | 27,28 |
| 3214 | 29,30 |
| 3241 | 31,32 |
| 3412 | 33,34 |
| 3421 | 35,36 |
| 4123 | 37,38 |
| 4132 | 39,40 |
| 4213 | 41,42 |
| 4231 | 43,44 |
| 4312 | 45,46 |
| 4321 | 47,48 |
就是這樣，「神秘通天眼」就可以根據「使者」在桌上的擺陣，在兩次內猜出「底牌」了。
用數學的語言，我們利用了 |P4| = 24和餘下48隻牌的兩個數字，構成了一個 1-to-2 map。
後來，鄭教授的高足們更用了紙牌一個小特點，令他們有很大機會一次就能命中。這個小特點就是，52隻牌當中有不少牌打直擺和倒轉擺的花款是不同的。舉個例子吧（磚7）：
 |  |
2007年9月7日 星期五
A Wonderful Card Trick
科大的理學院院長鄭紹遠教授不時教授學生玩一些紙牌遊戲，英文名就叫Card Trick。自己未能親身學習，不過倒認識了不少科大的同學，都有玩這些Card Trick。這些同學曾經將鄭教授教的一個Card Trick改良，變成了一個在科大傳頌一時的「魔術」。
「魔術師」有兩個人，我們叫他們做「使者」和「神秘通天眼」好了。一開始「神秘通天眼」會走到老遠去，而「觀眾」在Poker Cards的五十二隻牌中隨機抽五隻出來。然後觀眾可以從這五隻中任意抽取一隻藏起。「使者」把餘下四隻牌放在桌子上，然後便走掉。「神秘通天眼」這時回來，望一望那四隻牌，便跟「觀眾」說：「我猜兩次就可以知道你的牌了。」
期間「使者」和「神秘通天眼」是不可以有任何接觸的（不能對話，也不能夠望到對方）究竟兩個「魔術師」是怎樣做到的呢？
「魔術師」有兩個人，我們叫他們做「使者」和「神秘通天眼」好了。一開始「神秘通天眼」會走到老遠去，而「觀眾」在Poker Cards的五十二隻牌中隨機抽五隻出來。然後觀眾可以從這五隻中任意抽取一隻藏起。「使者」把餘下四隻牌放在桌子上，然後便走掉。「神秘通天眼」這時回來，望一望那四隻牌，便跟「觀眾」說：「我猜兩次就可以知道你的牌了。」
期間「使者」和「神秘通天眼」是不可以有任何接觸的（不能對話，也不能夠望到對方）究竟兩個「魔術師」是怎樣做到的呢？
2007年9月3日 星期一
Pythagoras' Theorem---Logic in F2 Math
在初中階段，要證明邊長分別是3、4和5 的三角形是一個直角三角形，我們可以這樣說：「由於32 +42 = 52，所以根據畢氏定理的逆定理，它一個直角三角形。」
那麼，怎樣證明邊長分別是2、3和4 的三角形 XYZ 不是一個直角三角形呢？以下是一般教科書的說法：「由於22 +32 不等於 42，所以XYZ不是一個直角三角形。」
大家留意，當中省略了根據什麼。是否也是根據畢氏定理的逆定理？
非也！是根據畢氏定理 ！
我們可用反證法作出證明：「假設XYZ一個直角三角形，則22 +32 = 42 (畢氏定理)。矛盾。」
一般來說，根據一個常用的邏輯論證方法：contrapositivity, 「若ABC一個直角三角形，則a2 +b2 =c2 」與「若a2 +b2 不等於c2 ，則ABC不是一個直角三角形」這兩句statement是等價的。
(contrapositivity是指「若p則q 」與 「若~q則~p」 是等價的，例如「若下雨我便帶傘，但我沒帶傘，所以沒有下雨。)。
那麼，怎樣證明邊長分別是2、3和4 的三角形 XYZ 不是一個直角三角形呢？以下是一般教科書的說法：「由於22 +32 不等於 42，所以XYZ不是一個直角三角形。」
大家留意，當中省略了根據什麼。是否也是根據畢氏定理的逆定理？
非也！是根據畢氏定理 ！
我們可用反證法作出證明：「假設XYZ一個直角三角形，則22 +32 = 42 (畢氏定理)。矛盾。」
一般來說，根據一個常用的邏輯論證方法：contrapositivity, 「若ABC一個直角三角形，則a2 +b2 =c2 」與「若a2 +b2 不等於c2 ，則ABC不是一個直角三角形」這兩句statement是等價的。
(contrapositivity是指「若p則q 」與 「若~q則~p」 是等價的，例如「若下雨我便帶傘，但我沒帶傘，所以沒有下雨。)。
2007年8月31日 星期五
可數性（countability）
大家知道，如果一個集的元素可以和正整數集 N 的元素一一對應的話，那麼這個集稱為可數的（countable）。例如：整數集 Z 是可數的，因為它可以和 N 作一一對應：
1←→0、2←→1、3←→ -1、4←→2、5←→ -2、6←→3、7←→ -3、……
換句話說，如果一個集的所有元素可以「順序列出來」，則它是可數的：
0、1、-1、2、-2、3、-3、……
以下是兩個「證明」，大家看看有甚麼問題：
(1) 0 和 1 之間的所有實數（不包括 0 和 1）是可數的
證明：我們只需把 0 和 1 之間的所有實數「順序列出來」即可：
0.1, 0.2, 0.3, ..., 0.9, 0.01, 0.02, ..., 0.99, 0.001, 0.002, ..., 0.999, 0.0001, ...
(2) 所有以整數為系數的多項式是不可數的
證明：假設所有以整數為系數的多項式是可數的，則存在一一對應
1 ←→ a10 + a11x + a12x2 + a13x3 + ...
2 ←→ a20 + a21x + a22x2 + a23x3 + ...
3 ←→ a30 + a31x + a32x2 + a33x3 + ...
4 ←→ a40 + a41x + a42x2 + a43x3 + ...
......
考慮 f(x) = (a10+1) + (a21+1)x + (a32+1)x2 + (a43+1)x3 + ...，則顯然 f(x) 不等於以上任何一個多項式，這跟一一對應的意義矛盾，因此所有以整數為系數的多項式是不可數的。
One Line Solution?
最近在科大圖書館找一些關於Combinatorial Algorithms的書時，無意中見到兩本同系列的書，書名非常吸引。作者是A.M. Yaglom和I.M. Yaglom（兩兄弟？父子？），書名是"Challenging Mathematical Problems With Elementary Solutions"，有Volume 1和Volume 2。書內的Preface說，這本書是翻譯自俄羅斯一本著名的problem book，名叫"Non-Elementary Problems in an Elementary Exposition"。
這個時候，當然又是給大家想想書中問題的時間了。
如果大家有玩過國際象棋的話，一定知道有一種棋叫"bishops"，它只可以打斜行，但行多少格都可以。試證明在國際象棋的 8 x 8 棋盤內放下 k 隻 bishop（k可以是0；不放任何bishops在這裏被視為一種方法）而這些bishops互不攻擊的方法的數目是一個平方數。
English Version: A bishop can moves diagonally only in the chessboard; but the number of boxes it move is not restricted. Prove that on the 8 x 8 chessboard, the number of different arrangements of k bishops (k can be 0; not placing any bishop is also considered as a arrangement here) such that no bishop controls a square on which another lies.
這個時候，當然又是給大家想想書中問題的時間了。
如果大家有玩過國際象棋的話，一定知道有一種棋叫"bishops"，它只可以打斜行，但行多少格都可以。試證明在國際象棋的 8 x 8 棋盤內放下 k 隻 bishop（k可以是0；不放任何bishops在這裏被視為一種方法）而這些bishops互不攻擊的方法的數目是一個平方數。
English Version: A bishop can moves diagonally only in the chessboard; but the number of boxes it move is not restricted. Prove that on the 8 x 8 chessboard, the number of different arrangements of k bishops (k can be 0; not placing any bishop is also considered as a arrangement here) such that no bishop controls a square on which another lies.
2007年8月29日 星期三
Mission Impossible?
哈，今日又聽到一條看似"mission impossible"的問題。我想這題用英文會好理解一點：
There is a submarine which is located at some integer point on the real axis at the 0th second. It moves with uniform velocity k units / sec, where k is an integer (possibly negative). As the submarine is deep under the water, you cannot see it. Every second you are allowed to fire a missile at some integer point. Find a way to fire the missiles so that you are guaranteed to fire at the submarine.
There is a submarine which is located at some integer point on the real axis at the 0th second. It moves with uniform velocity k units / sec, where k is an integer (possibly negative). As the submarine is deep under the water, you cannot see it. Every second you are allowed to fire a missile at some integer point. Find a way to fire the missiles so that you are guaranteed to fire at the submarine.
2007年8月25日 星期六
帽子問題
最近玩了兩題「帽子問題」，跟大家分享一下：
- 有 10 個人排了一條隊，每人頭上都有一頂黑色或者白色帽子。每個人只可以看到排自己前面的人所穿帽子的顏色，而且他們均不能看到自己帽子的顏色。
現在有一個公証人，他會向每個人問一條問題：「你自己的帽子是甚麼顏色？」他會順序由排最後的人問到排最前的人。每個人只可以回答：「黑色」或「白色」，而每個人回答時，其他人都是可以聽到他的答案的。
這 10 個人可以事先商量怎樣回答，以確保答對的次數最多。問：他們可以確保答對多少次？怎樣可以達到？ - 監獄裏有 n 個囚犯。有一日，皇上要跟這 n 個囚犯玩一個遊戲。皇上會選出 n 種顏色。獄長會在每一個囚犯頭上戴上一頂帽子，每頂帽子的顏色是這 n 種顏色之一。帽子的顏色並無其他限制，所以可能每個囚犯的帽子顏色都相同，亦有可能每個囚犯的帽子顏色均不同的。
每個囚犯都可以看到其他囚犯的帽子，唯獨是不可以看到自己的帽子。現在，囚犯們要同一時間向獄長交一張紙，上面寫上他們猜測自己帽子的顏色。當然，這樣子就是說囚犯們不會看到其他囚犯的猜測了。
皇上說如果有任何一個囚犯答對了，就釋放所有囚犯；否則，全部囚犯都要處死。這些囚犯可以事先商量怎樣回答，以確保他們一定能夠被釋放？問：他們怎樣達到目的？
2007年8月23日 星期四
第七屆培正數學邀請賽
Let me Break The Ice
各位MD的朋友好！
「數學資料庫手記」誕生之前，有人問：「MD 已經有Forum ，討論可在Forum 進行。為何要開一個Blog? 」
我認為這個網誌不但為MD 提供多一條康莊大道與各界人士接觸，讓各位認識我們多一些；亦為MD members 提供一個 (相比Forum) 較 informal 的吹水平台，閒時發下奴騷。多謝阿Dick (Website Management Vice) 為MD 出主意，開了這個網誌。
這個網誌會有些什麼？由於MD members 各有千秋，且題材太廣，我也預計不到。可以透露：Gigi (Academic Vice) 提議，一些海外MD members 可把在外地修讀數學的經歷加入其中。此外、MD members 亦會在這裡談及於日常生活中涉及數學的趣事。詳情大家拭目以待吧！
雖然只有MD members 可以編輯這個網誌, 但我們歡迎各位留言。我希望所有與MD 有緣的人能見證「數學資料庫手記」的誕生, 更希望能在這個Blog、Forum 、MD Seminar 或其他有關數學的場合和大家見面！
「數學資料庫手記」誕生之前，有人問：「MD 已經有Forum ，討論可在Forum 進行。為何要開一個Blog? 」
我認為這個網誌不但為MD 提供多一條康莊大道與各界人士接觸，讓各位認識我們多一些；亦為MD members 提供一個 (相比Forum) 較 informal 的吹水平台，閒時發下奴騷。多謝阿Dick (Website Management Vice) 為MD 出主意，開了這個網誌。
這個網誌會有些什麼？由於MD members 各有千秋，且題材太廣，我也預計不到。可以透露：Gigi (Academic Vice) 提議，一些海外MD members 可把在外地修讀數學的經歷加入其中。此外、MD members 亦會在這裡談及於日常生活中涉及數學的趣事。詳情大家拭目以待吧！
雖然只有MD members 可以編輯這個網誌, 但我們歡迎各位留言。我希望所有與MD 有緣的人能見證「數學資料庫手記」的誕生, 更希望能在這個Blog、Forum 、MD Seminar 或其他有關數學的場合和大家見面！
訂閱：
文章 (Atom)