在 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年11月25日 星期日
2007年6月27日 星期三
最新的 TOP500
最新的 TOP500 列表又發表了。BlueGene/L 仍然穩居第一名,而且還有兩部新的 BlueGene 電腦進入了前十名。現在前八名的電腦都是位於美國的電腦。另外,前三名的電腦都超過了 100 TFLOPS。
前十名中另一部新電腦是 Dell 的 cluster,位於第八名。第十名的電腦也是一部新電腦,是 SGI 的 Altix 系統。
現在日本最快的電腦是一部 NEC 建置的 Sun Fire X4600 cluster,使用 Opteron 處理器和 Clearspeed 加速器,位於第十四名。
前十名中另一部新電腦是 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 有很密切的關係。也就是說,如果你打中怪物的準度不夠,就應該打少次一點,期待運氣好每次都命中。但是如果準度夠,就可以選擇打多次一點,比較「保險」。
假設球棒的速度正好是小刀的一半,那麼,看起來似乎沒什麼差別,因為小刀刺中六下所需要的時間,和球棒打三下是一樣的。不過,這是假設每一下都能打中。如果有一個固定機率會沒打中的話,情形似乎就不同了。
如果十秒的時間,剛好可以用小刀刺十下,或是用球棒打五下。那麼,直覺來看,似乎用小刀「比較安全」,因為就算偶而沒刺到,也有比較多次機會可以補救。但真的是這樣嗎?
為了簡單起見,先假設,打中的機率和打不中的機率是一樣的(各為 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日 星期二
2007年1月29日 星期一
Supreme Commander beta 測試結束日期
Gas Powered Games 表示,目前暫時決定 Supreme Commander 的 beta 測試將在二月五日結束。目前的 beta 測試將以 GPGNet 的測試為主,同時也引進新的統計系統,將會記錄所有 ranked game 中的詳細資訊,包括各種單位被生產的次數等。
2007年1月19日 星期五
訂閱:
文章 (Atom)