2008年9月28日 星期日

32x32棋盤的覆蓋問題

剛剛在網上見到這樣一個問題，覺得蠻有趣的，在這裏分享一下：

有一個 32 x 32 的棋盤。你要預先剪好5塊拼圖，使得當我拿走棋盤任意一個正方形後，你可以用這5塊拼圖覆蓋「餘下的棋盤」。

當然，老規矩，5塊拼圖覆蓋時不可重覆，亦不可有任何部分在「餘下的棋盤」外啦。


原本想說多些對這問題的感想，但不想影響到大家的解題方向，所以不講了。就這樣。
張貼者： 於 6 則留言:
標籤： , , ,

2008年9月23日 星期二

奇怪的經典數學比賽題目－－無窮項的處理

　　經常參加數學比賽的學生應該遇過以下的兩道題目：

1. 若 x=1+0.1+0.01+0.001+\cdots=\displaystyle{\sum_{k=0}^\infty10^{-k}}，求 x 的值。

2. 若 y=\sqrt{6+\sqrt{6+\sqrt{6+\sqrt{6+\cdots}}}}，求 y 的值。

　　這兩題皆牽涉無窮項的處理。在大學的分析課裏，我們知道處理運算符 (operator) 必須逐一按優先次序處理。例如當我們算 2 + 3 + 4 時，我們應由左至右算出答案 2 + 3 + 4 = 5 + 4 = 9。因為我們的算式只應涉及有限次運算，因此我們不能求無窮項的和。那麼第一題的寫法成立嗎？

　　其實我們可把所謂「無窮項的和」只是有限項的和的極限 (limit)。由此可知，第一題可嚴謹地寫成

「設 \color{blue}a_n = \displaystyle{\sum_{k=0}^{n-1}10^{-k}}（即首 n 項的和），求 \color{blue}\displaystyle{\lim_{n\to\infty}a_n} 的值。」

　　我們不難證明上述的極限（即「無窮項的和」）是 \dfrac{10}{9}。

　　解決了第一題，到第二題。我們能否嚴謹地將題目裏的表達式寫出來呢？在此之前，先看看求 y 的運算過程。它的最後一步是取（非負）平方根，前一步是加 6，再前一步是取（非負）平方根，再之前的是加 6，並以此規律不斷往前推，推至「無窮項」。根據這種寫法，很多數學書都提供以下的解法：

　　「因為這裏應用了無窮個「加 6 後取平方根」的步驟，所以將 y 加 6 後取平方根仍是 y。即 \color{blue}%5Csqrt%7B6+y%7D=%5Csqrt%7B6+%5Csqrt%7B6+%5Csqrt%7B6+%5Csqrt%7B6+%5Ccdots%7D%7D%7D%7D=y。從第一項和第三項的等式可知 \color{blue}6+y=y^2。因平方根號指非負的平方根，故解二次方程後只取正根，可得 y = 3。」

　　這種解法有意思嗎？不。從前文的推論，我們可知求 y 的「運算過程」根本不完整。我們只知它不斷運算「加 6 後取平方根」，但卻不知道它的第一步是由甚麼「加 6 後取平方根」。這和第一題的無窮項之和不同。第一題的和有第一項 1，接著是加上第二項 0.1，然後是第三項 0.01，如此類推。因此，我們才可以將它理解為有限項之和的極限。可是第二題裏的怪物卻無從由第一步算起。換言之，這個表達式根本不成立，又怎會有數值？
張貼者： 於 1 則留言:
標籤： , , , , ,

2008年9月19日 星期五

流行榜最多得幾個獎？

某電台年終的樂壇頒獎禮，會頒發十首歌曲獎。聽聞有規定，每個歌手不可拿兩首或以上的歌曲獎。而江湖傳聞，若兩人合唱的歌曲，每人只算1/2個獎；三人合唱的歌曲，每人只算1/3個獎；如此類推。

於是我腦裏閃過一個問題：每個歌手最多可以拿多少個獎？數學上，可以將問題這樣表達：

求 的supremum。


甚麼是supremum呢？簡單來說就是"smallest upper bound"。舉個例子，若一個集合裏面的元素是3/2, 7/4, 15/8, 31/16, ... 等可表達成的數。這個集合可以有很多不同的upper bound，例如3、4、1,000,000,000等。而2當然也是其中一個upper bound。

而我們可以證明所有比2小的數都不是這個集合的upper bound。設，而。那麼必然存在一個正整數N，使得。這樣的話，所以a不是該集合的upper bound。因此2是該集合的"smallest upper bound"，亦即該集合的supremum。

以上的例子亦說明了supremum一個特點：雖然它是該集合的upper bound，但該集合裏沒有元素是等於2的！

說回頒獎禮的問題。從S的定義來看，2明顯地是S的一個upper bound。但它是supremum嗎？在數學資料庫的論壇，我和其他網友有一些關於這題的討論。歡迎大家發表意見！
張貼者： 於 2 則留言:
標籤：

2008年9月13日 星期六

「法定門檻」與「安全門檻」

大家知道，香港立法會選舉的地區直選採用比例代表制。以九龍東選區為例，該區有 4 個議席，參選名單每取得四分之一（25%）的選票便可保證獲得一席。這個 25% 一般稱為法定門檻。

可是六天前的選舉過後，香港大學民意研究計劃所提供的快速報票資訊中，卻出現了另一個詞語，名為安全門檻。得票超過安全門檻後，名單上排名第一的候選人便會得到一個「剔號」，意味候選人肯定當選。在九龍東選區，安全門檻是總票數的五分之一（20%）。

為甚麼會有兩個不同的數字？原來即使選舉法例規定要 25% 選票才能保證獲得一席，但事實上（或者說「數學上」）得票超過 20% 亦可保證獲得一個議席，因為不可能有五張名單得票超過 20% 的。同樣道理，得票 43.75% 便可保證贏得兩席，得票 66.67% 便可保證贏得三席，如此類推（試作出證明！）。

正因為這個原因，部分地區採用比例代表制分配 n 個議席時，法定門檻會定為總票數的 (n+1) 分之一而非香港採用的 n 分之一。香港法定門檻 n 分之一一般稱為黑爾數額（Hare quota），而「(n+1) 分之一」的門檻則稱為特羅普數額（Droop Quota）。不難發現，採用黑爾數額是不利於以一張名單奪取多個議席的，從而鼓勵政黨分拆名單，令每張名單各自以低於黑爾數額的餘額取得一席。以今年的選舉結果為例，只有港島區、新界東和新界西各有一張名單取得兩席，其他名單都只取得一席。

這樣的制度實在偏離了比例代表制的原意：議席數目與得票數目成正比。以新界東選區為例，劉江華名單以 102434 票取得兩席，而劉慧卿名單則以 33205 票取得一席。兩者所得的議席比例為 2:1，但得票比例卻是 3.1:1。而且當參選名單越多時，更極端的情況越可能發生。當然，沒有一個制度是完美的，這樣的偏差難免會出現，不過使用配以黑爾數額的最大餘額法是否最為適合，實在值得各方深入探討。
張貼者： 於 沒有留言:
標籤： , , ,

2008年9月8日 星期一

多議席全票制？

　　第四屆立法會選舉落幕。劉慧卿在點票現場接受傳媒訪問，指出選舉制度應該改革，例如由比例代表制改為多議席全票制 (block voting)（即各候選人皆獨立參選，而每位選民的票數與議席數量相等。例如，今屆新界東有七席，每位新界東選民可投最多七票）。如果選舉採用這種制度，結果有甚麼特點？下文將作簡單的討論。

　　假設某選區有七席，其中一個政治派別派出七人或以下出戰。如果某選民是該派別的絕對支持者，明顯地會將他的票全投給該派別的代表。其他支持者亦通常把票投給當中幾人，再配搭其他候選人。由此可知，我們可以預期政治派別的候選人得票應與其支持者數量相若。

　　另一方面，因為大多數選民皆會以上述的套餐形式投票，同一派別的候選人票數很接近。對政治派別來說，這是一場「全部或沒有」 (all-or-none) 的遊戲。為甚麼呢？考慮兩個政治派別 A 和 B。假設 A 和 B 皆派出七人出戰擁有七席的選區。若 A 有 20000 名支持者，上述的推論指出 A 的候選人各應約得 20000 票（如 18000 至 21000 之間）。假如 B 的支持者超過 20000（如 30000），他們的七位候選人得票很可能都比 A 的七人高，令 A 全軍盡墨。但如果 B 的支持者不夠多（如 15000），A 的候選人便可完全壓倒 B 的七人。不難發現僅當兩者支持者數量極接近時，才可能平分秋色。換言之，這接近一種「全部或沒有」的選舉制度，尤其當政治派別只有兩個時更為明顯。多議席全票制對支持率高的政治派別有利，而稍次的則可能完全落敗。由此可知，當政治派別太少時，多議席全票制無法有效按支持者比例分配議席。

　　今年初的人大代表選舉正是選用多議席全票制的，詳情可參見本手記的兩篇文章《港區人大代表選舉》和《人大選舉結果》。只要細看《人大選舉結果》一文所列的選舉結果（尤其是第 40 和 41 位的得票），便知多議席全票制的「全部或沒有」所言非虛。

張貼者： 於 沒有留言:
標籤： , , , , ,

2008年9月7日 星期日

順流、逆流

這裏不是說小鳳姐的經典名曲，而是講一個在奧數中不時遇到的概念。

事緣今天寫奧數筆記，其中一個例子是這樣的：

小船在沒有水流時航行的速度是24 km/h。水流由A城流往B城，而兩城相距70 km。現小船由A城航行到B城，然後駛回A城，共需6小時。問水流的速度是多少？


而原本寫的解答的其中幾句是：

設由A城流往B城的水流速度為x km/h。這樣的話，由A城駛往B城時，順流時小船的速度為 (24+x) km/h。而逆流時小船的速度為 (24-x) km/h。

但，腦筋急轉彎：順流時小船的速度真的是 (24+x) km/h嗎？

因為最近比較忙，所以不打算作出一些詳細物理的arguments。但可以舉一個例子。若在水流為 x km/h 的河裏放一隻小紙船，小紙船的速度應該大約是 x km/h。若在同一條河放一隻大漁船，水流的影響就不會很大，所以大漁船在不開摩打的情況下速度應該比 x km/h 為低。

為了補救，我作出了以下修改：

設由A城流往B城的水流速度為x km/h。這樣的話，由A城駛往B城時，因為順流，小船的速度會比在沒有水流時航行時為高。一般來說，我們會取順流時小船的速度為 (24+x) km/h。而逆流時小船的速度會減慢，而我們會取逆流時小船的速度為 (24-x) km/h。
張貼者： 於 沒有留言:
標籤：

2008年9月6日 星期六

投票選冠軍的概率問題－－錯處在哪？（下）

注意：請先看畢本文的第一部分，並想過當中的概率問題才看這篇文章。
　　正如第一部分的提示所說，我們先考慮只有 3 人投票的情況。假設兩位參賽者為 P 和 Q，三位觀眾 A、B 和 C 皆隨機投票。現計算各情況下 A 可參加抽獎的概率：
A 的選擇B 的選擇C 的選擇冠軍A 可否參加抽獎？
PPPP可以
PPQP可以
PQPP可以
PQQQ不可以
QPPP不可以
QPQQ可以
QQPQ可以
QQQQ可以
由上表可知，A 可獲抽獎的概率是 \frac{6}{8}=\frac{3}{4}，而不是第一部分提及的 \frac{1}{2}。原因很簡單：當 A 投了票，他所選的對象便已獲一票，故當其他人隨機投票時，A 所選的對象便較有優勢，只需在餘下的票取得剛好一半便勝出。那麼第一部分提及的「因為所有人都隨機投票，所以兩名參賽者得冠軍的概率相等，皆為 \frac{1}{2}」錯了甚麼？其實它沒錯，只不過在這裏不適用。這是因為經過 A 的投票後，兩位參賽者 P 和 Q 已經不對稱了。這一點在票數較少的情況下才明顯。
　　接著我們考慮 A 被抽中的概率：

A 的選擇B 的選擇C 的選擇冠軍此情況
的概率		此情況下
A 被抽中的概率		A 被抽中
的概率
PPPP\frac{1}{4}\frac{1}{3}\frac{1}{4}\times\frac{1}{3}=\frac{1}{12}
PPQP\frac{1}{4}\frac{1}{2}\frac{1}{4}\times\frac{1}{2}=\frac{1}{8}
PQPP\frac{1}{4}\frac{1}{2}\frac{1}{4}\times\frac{1}{2}=\frac{1}{8}
PQQQ000
QPPP000
QPQQ\frac{1}{4}\frac{1}{2}\frac{1}{4}\times\frac{1}{2}=\frac{1}{8}
QQPQ\frac{1}{4}\frac{1}{2}\frac{1}{4}\times\frac{1}{2}=\frac{1}{8}
QQQQ\frac{1}{4}\frac{1}{3}\frac{1}{4}\times\frac{1}{3}=\frac{1}{12}





總計\frac{1}{3}


　　你看，A 被抽中的概率是 \frac{1}{3}，與我們預期的相同。至於第一部分提到的情況，各位自行算一算吧，情況很相似。
張貼者： 於 沒有留言:
標籤： ,

2008年9月5日 星期五

Friends of MathDB

「數學資料庫之友」Friends of MD (FoMD) 現已成立！
現誠邀各界人仕（包括大學、中學及小學的老師和學生）免費加入，
登記資料後即可享有 FoMD 會員之權利，
包括參加所有由數學資料庫舉辦的活動，
及定期收到網站的資訊及期刊，
更有機會贏取豐富獎品！
要立即登記，請按....
Friends of MD

Here comes our newly formed allied group Friends of MD (FoMD) !
We sincerely invite all of you (including teachers and students from tertiary, secondary and primary schools) to join us.
Upon free registration, you will enjoy the privilege of FoMD members,
including the right of joining activities held by MD and
receiving our updates and newsletters regularly,
plus the chance to win fabulous prizes!
To join now, click ......
Friends of MD
張貼者： 於 沒有留言:
訂閱： 文章 (Atom)