2007年12月27日 星期四

新手記網址

由今日起,大家除了可以使用 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 架?」

小權說:「我也是這樣跟老師說……」

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 < kd ,要找出在 [a,b] 內有多少個重量為d的「k質數組」。

當時想了一想,如果test case當中有 d = 0 , k = 1,那不就是問我 ab之間有多少個質數嗎?若然 a 和 b 均是很大的數,那麼要得到一個好的估計還不難(就是用Prime Number Theorem吧),但要無誤差地說出在某個特定的range內有多少個質數,唯一已知的方法就是逐個試。

最後因為ab太大,我們認為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 也不見得容易。但後來有人證明了對於少於
2,152,302,898,747 的 n ,只要試 a = 2, 3, 5, 7 或 11,若然對於這五個 a 的數值,都可以符合以上定理中兩組等式的其中一組,那麼 n 就是一個質數了。

就是因為這個結果,對於每個 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 這麼特別呢?愚見認為有兩個可能的原因:
  1. 「變成一倍」等於沒變
    與「變成兩倍」或「變成三倍」不同,「變成一倍」實際上指沒有變化,與「變成」的意思相違。因此,很多人會覺得這句話沒意思。於是他們在心裏「自動校正」(autocorrect),將「變成一倍」自動看成有轉變意義的「增加一倍」,並慢慢習非成是。
  2. 中文的用法問題
    這個問題在英語裏甚少發生。也許這是因為常用的倍數詞語(變成兩倍、變成三倍等),在英語裏各有自己的動詞(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月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。

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)填上紅藍兩色前,先揀選一些特別的邊來填上紫色(因他觀察到這些邊對結果影響不大)。這樣他便將需要考慮的可能性大大減少。


後記

雖然學術會議主要是提供一個學術交流的機會,但它同時亦帶來一個旅遊的藉口。故此,要是某學術會議是在一個著名的城市裡舉辦的話,那它的費用便會被調得特別高呢!

出席學術會議亦可能成為一些不負責任的教授用來「逃課」的藉口。我便聽說過曾經有一位教授在某學期裡三分之一的時間都去了「開會」,而他所授的課就不斷地要別人來接替!

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),這個很簡單。因為 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 時截止,有意參賽的同學請向就讀學校的數學老師查詢。

獲學校提名參賽的同學應提供正確的個人資料予老師報名,否則可能不獲參賽資格。老師輸入報名學生的資料時請特別注意以下事項:
  • 報名參加的組別必須與就讀年級相符。
  • 必須提供正確的電郵地址。不同的參賽學生必須填寫不同的電郵地址。
  • 必須填寫中文姓名,或選擇「沒有中文名」一項。
  • 英文的「姓」和「名」不要倒轉,而且必須和身份證上的名字相同。
  • 大會稍後會透過電郵要求參賽同學核實個人資料,屆時必須小心核對。
希望參加比賽而所屬學校沒有報名的同學,應留意大會公佈的個人報名安排。詳情請瀏覽比賽網頁