2007年11月27日 星期二

輸掉比勝出有利?

世界盃外圍賽

  2010 年世界盃外圍賽便抽籤了。足球強國大多於歐洲和南美洲,而南美洲的外圍賽是最簡單的主客制雙循環賽事(即任何兩隊都會以主場和作客比賽各一場),不用抽籤分組,因此抽籤的焦點都落在歐洲 53 隊的分組情況。歐洲區將有 13 隊出線 2010 年世界盃決賽周。這 13 隊的產生辦法如下:

  1. 53 隊分為 9 組,其中 8 組 6 隊, 1 組 5 隊。每組都進行主客制雙循環賽事,各組首名出線決賽周;
  2. 9 組次名當中,成績較好的 8 隊會配成 4 對以主客制對賽 2 次,每對裏的勝出者出線決賽周。(最差的次名隊伍將自動出局。)

最差次名?

  對數字敏感的讀者可能會發現上述賽制有個小問題:怎樣決定「最差次名」?如果各組隊數相同,我們還可以直接比較它們的分數。可是現在其中一組少了一隊呢,怎辦?放心,國際足協不會讓賽制留下這麼大的缺口。規則裏規定,排列各組次名時,擁有 6 隊的組別只計算與小組次名與小組首名、第 3 名、第 4 名和第 5 名的對賽分數,與第 6 名對賽所得的分數則忽略不計。因此,每隊小組次名都只計算 8 場比賽,問題似乎解決了。(當然,同分時另有決定準則,但這與本文主題太遠,在此略過。)


令人尷尬的賽果

  實情真的如此嗎?非也。這個解決方法暗藏一個漏洞。這漏洞不易出現,但出現時可非常尷尬。原來它可能衍生某隊輸掉球賽比勝出更有利的情況!以下的就是這樣的尷尬情況:

  假設某組有 6 隊 A、B、C、D、E 和 F。他們共需比賽 10 輪,現假設首 9 輪的成績和積分榜如下(勝出 3 分,賽和 1 分,輸掉則 0 分):


ABCDEF
A/ 1 : 0
1 : 0
1 : 0
? : ?
1 : 0
B 0 : 0
/1 : 01 : 00 : 1? : ?
C0 : 10 : 1/? : ?1 : 01 : 0
D0 : 10 : 11 : 0/0 : 01 : 0
E0 : 11 : 00 : 10 : 0/0 : 1
F0 : 10 : 10 : 10 : 11 : 0/





分數
A
8
1
0
25
B51316
C40512
D32411
E2258
F2076

  第 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 元書券 及 精美禮品一份

若想知道其他詳情,請按此進入比賽網頁。

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
  • 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.
Case 2: All u's exist, but some u and w are equal (say u1=w2)
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.
Case 4: All u's exist and are distinct, and no u and w are equal
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).
Hence in each case we get a desired splitting, in contrary to (0). This completes the proof.



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.
So why can a proof avoid making use of conditions that are necessary?

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扯上關係!

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」,大意是說不存在一個選舉制度,可以滿足我們所有的「合理期望」!

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 元鈔票是偽鈔,李先生亦發現貨品是贗品。問事件中李先生/曾先生各自得益/損失多少?

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

2007年11月2日 星期五

培正數學邀請賽:最新消息

第七屆培正數學邀請賽將於 2008 年 1 月 26 日(星期六)及 2008 年 3 月 8 日(星期六)舉行。現已接受學校報名,詳情請瀏覽比賽網頁 http://www.puichingcentre.edu.hk/pcimc/