2007年11月25日 星期日

Mahalanobis 的問題

在 Wikipedia 上介紹數學天才 Ramanujan 的文章中,提到一個有趣的問題:

假設你在一條街道上,有 n 間房子,路牌號碼是 1 ~ n。其中有一間房子(號碼 x),它的左邊所有房子的路牌號碼總和,和它右邊的房子的路牌號碼總和相同。如果 n 在 50 至 500 之間,那麼 n 和 x 各是多少?

文章中提到 Ramanujan 很快就利用連分數解出了這個問題,讓他的室友 Mahalanobis 非常驚訝。

當然,Ramanujan 是數學天才。不過這個問題讓我覺得很有意思:它看起來算是相當簡單,我想可能小學生也能聽懂。不過這個問題倒底要怎麼解呢?

考慮 x 左邊的房子,即號碼 1 ~ x-1 的房子,其路牌號碼總和就是 x(x-1)/2。它右邊的房子,路牌號碼總和是 n(n+1)/2 - x(x+1)/2。這兩個數字要一樣,所以:

x(x-1)/2 = n(n+1)/2 - x(x+1)/2

-> x^2 = n(n+1)/2

所以,問題變成,要找出一個平方數(即 x^2),它同時也是一個三角數(即 n(n+1)/2)。

這個問題其實就蠻古老的,例如有名的阿基米德分牛問題,也有類似的要求。解法的關鍵是,一個正整數 m 若是三角數,則 8m+1 會是一個平方數,反之亦然。所以,因為 x^2 是一個三角數,所以 8x^2 + 1 會是一個平方數,設它為 y^2,這樣會得到一個 Pell's equation:

y^2 - 8x^2 = 1

解 Pell's equation 的確是會用到連分數,這個例子中會需要用到 sqrt(8) 的連分數。不過這個式子倒是有個很明顯的解,就是 y = 3, x = 1。

要求出更多的解,除了用連分數之外,也可以用下面的方法:

y^2 - 8x^2 = (y + sqrt(8) x) (y - sqrt(8) x) = 1

因此

(y + sqrt(8) x)^n (y - sqrt(8) x)^n = 1

n 是任意正整數。也就是說,假設已經有一組解(例如 y = 3, x = 1),就可以很容易計算出更多的解。比如說:

(3 + sqrt(8))^2 = 17 + 6 sqrt(8)

所以 y = 17, x = 6 也是一組解。

現在有了 x,就需要算出 n,因為題目要求 n 是 50 ~ 500 之間。算出 n 就容易多了:因為

n(n+1)/2 = x^2

-> n^2 + n = 2x^2

所以要算出 n,只需要把 x 乘上 sqrt(2),再取整數部份即可(因為 n^2 < 2x^2 且 (n+1)^2 > 2x^2)。所以,x = 6 的時候 n = 8。很容易驗證這個答案是正確的(1 + 2 + ... + 5 = 15,7 + 8 = 15)。另外也可以注意到因為 y^2 = 8x^2 + 1,所以

y^2 - 1 = 8x^2

-> (y + 1) (y - 1) / 4 = 2x^2

-> (y + 1) / 2 * (y - 1) / 2 = 2x^2

所以如果 n = (y - 1) / 2 則 n (n + 1) = 2x^2,也就是要求得的 n。

要計算出 50 ~ 500 之間的 n,需要再找更大的 x:

(3 + sqrt(8))^3 = 99 + 35 sqrt(8) -> x = 35, n = 49

(3 + sqrt(8))^4 = 577 + 204 sqrt(8) -> x = 204, n = 288

這就是原問題的解了。

2007年6月27日 星期三

最新的 TOP500

最新的 TOP500 列表又發表了。BlueGene/L 仍然穩居第一名,而且還有兩部新的 BlueGene 電腦進入了前十名。現在前八名的電腦都是位於美國的電腦。另外,前三名的電腦都超過了 100 TFLOPS。
前十名中另一部新電腦是 Dell 的 cluster,位於第八名。第十名的電腦也是一部新電腦,是 SGI 的 Altix 系統。
現在日本最快的電腦是一部 NEC 建置的 Sun Fire X4600 cluster,使用 Opteron 處理器和 Clearspeed 加速器,位於第十四名。

2007年5月9日 星期三

哪種方法好?

有一隻大怪物出現在你面前,十秒內就可以把你幹掉。所以,你得在十秒內把它解決。你可以用小刀刺它:速度比較快,但是效果也比較差,要刺中六下才能解決它。或是,你可以用球棒,速度比較慢,但是效果比較好,只要打中三下就夠了。哪種方法比較好?

假設球棒的速度正好是小刀的一半,那麼,看起來似乎沒什麼差別,因為小刀刺中六下所需要的時間,和球棒打三下是一樣的。不過,這是假設每一下都能打中。如果有一個固定機率會沒打中的話,情形似乎就不同了。

如果十秒的時間,剛好可以用小刀刺十下,或是用球棒打五下。那麼,直覺來看,似乎用小刀「比較安全」,因為就算偶而沒刺到,也有比較多次機會可以補救。但真的是這樣嗎?

為了簡單起見,先假設,打中的機率和打不中的機率是一樣的(各為 50%)。這麼一來,這個問題就變成:丟五次硬幣,至少出現三次正面,和丟十次硬幣,至少出現六次正面,比較哪種方法的機率高。

丟五次硬幣中出現至少三次正面的機率是 (1 + 5 + C(5, 2))/2^5 = 16/32 = 50%。丟十次硬幣中出現至少六次正面的機率是 (1 + 10 + C(10, 2) + C(10, 3) + C(10, 4))/2^10 = 386/1024 ~= 38%。所以,如果打中的機率只有 50% 時,用小刀反而不好,看起來「直覺」好像是錯的。

不過,如果打中的提率提高了,會有什麼影響?設打中的機率是 p,則五次打中至少三次的機率是:

p^5 + 5p^4(1-p) + C(5,2)p^3(1-p)^2

如果 p = 0.9 則機率是 99.144%。

十次中打中至少六次的機率是:

p^10 + 10p^9(1-p) + C(10,2)p^8(1-p)^2 + C(10,3)p^7(1-p)^3 + C(10,4)p^6(1-p)^4

如果 p = 0.9 則機率是 99.836%。

也就是說,如果打中的機率提高到 90%,則使用小刀反而是比較好的方法。直覺畢竟是對的 (?)。

當然,認真來說,哪種方法比較好,和 p 有很密切的關係。也就是說,如果你打中怪物的準度不夠,就應該打少次一點,期待運氣好每次都命中。但是如果準度夠,就可以選擇打多次一點,比較「保險」。

2007年2月6日 星期二

Supreme Commander demo 版即將推出

GameSpot 的這個報導說,Supreme Commander 的 demo 版將在星期二早上 9:30 am (PST) 推出(台灣時間星期三 1:30 am)。Demo 版會包括 Cybran Nation 的早期單人任務,以及一個對戰地圖 Finn's Revenge,可以選擇和三種不同難度的電腦對手對戰。

另外,BETA 測試的結束時間訂為二月十二日。

2007年1月29日 星期一

Supreme Commander beta 測試結束日期

Gas Powered Games 表示,目前暫時決定 Supreme Commander 的 beta 測試將在二月五日結束。目前的 beta 測試將以 GPGNet 的測試為主,同時也引進新的統計系統,將會記錄所有 ranked game 中的詳細資訊,包括各種單位被生產的次數等。

2007年1月19日 星期五

Supreme Commander(最高指揮官)進廠壓片

THQ 表示,Supreme Commander(最高指揮官)已經進廠壓片。 Supreme Commander 是由 Gas Powered Games 發展的即時戰略遊戲,由 Chris Taylor 設計(Chris Taylor 也是 Total Annihilation 的設計者)。預定推出日期為二月二十日。

不過目前 Supreme Commander 的 beta 測試仍繼續進行中,可能是要繼續測試和多人遊戲相關的部份。

2007年1月18日 星期四