做一回事後諸葛亮 |
送交者: 零加一中 2011年09月26日21:43:56 於 [靈機一動] 發送悄悄話 |
我很小就從某科普讀物得知,讓大猩猩在鋼琴上蹦11億年,也會演奏出一首貝多芬的第五交響樂。當然,你無法預測11億年中哪個時刻,大猩猩會有此壯舉。以後上了大學對此事有了較清楚的概念。首先,計算需要一些簡化的假定,比如猩猩蹦跳的頻率,還需假定蹦跳是勻速的,所以要對大師的第五交響樂作些假定,什麼餘音繞梁之類,想都不要想。最重要的是,這是統計意義上的,不是說一定會出現。應用通常採取的95%置信區間(Confidence Level),就是說成千上萬隻的大猩猩在鋼琴上亂蹦,經過11億年,95%的猩猩會在無法預知的時間,至少演奏過一次第五交響樂。然而,直至拿到博士學位,對這經過簡化的計算過程,還是一點概念都沒有。 有一次,一位大學同學(同系同年級,開車不到10分鐘!)問我一個問題,是她女兒的回家作業。在0-99這100個數中,多少不含數字1。她當然做出來了,但總覺得有更好的方法。而且當數字變大,她的死算方法馬上就不能用了。這是我的專業,自然是小菜一碟。一般的方法是“Inclusion-Exclusion”原理,或譯成“容斥原理”。設有N個元素,符合條件a的有N(a)個,符合條件b的有N(b)個,符合條件(a,b)的有N(a,b)個,問不符合條件a,b,c,... 的元素有多少。答案是 N(0) - {N(a) + N(b) + ...} + {N(a,b) + N(a,c) + ...} - {N(a,b,c) + ...} + N(0)是不加限制的選擇數。其意義是先減去我們不要的符合條件的選擇。因為減的太多,所以補上。第二次又補的太多,然後再減,直至正好。 現考慮我同學的問題,不妨假定是0-9,999。有4個條件abcd,各代表某一位有數字1。 N(0) = 10,000 N(a) = N(b) = N(c) = N(d) = 1,000 N(a,b) = N(a,c) = ... = 100 (共6項) N(a,b,c) = N(a,b,d) = ... = 10 (共4項) N(a,b,c,d) = 1 所以最終答案是 10,000 - 4,000 + 600 - 40 + 1 = 6,561 就是說先從一萬種減去至少含一個1的數,正好含一個1,2,3,4個1的數分別被扣、減了1,2,3,4次。現在把至少含兩個1的加回去,正好含2,3,4個1的被加了1,3,6次。再減去至少含三個1的,正好含3,4個1的被減了1,4次。三次操作一起考慮,正好含1,2,3個1的恰好被減了各一次。含四個1的被減了4-6+4=2次,加上N(a,b,c,d) = 1,也是只減一次。 答案用電郵送出後,我覺得這些數字之間是有聯繫的。用C (m,n)代表m中取n的組合數,最後答案可以寫成 C (4,0)104 - C (4,1)103 + C (4,2)102 - C (4,3)10 + C (4,4) = 6,561 將上式與二項式展開(a + b)4相比較,我們發現a = 10, b = -1, 答案6,561就是9的四次方,這才是真正的答案。我原來的方法比死算當然要好多了,而且有通用性。儘管對大數也很不便,但至少可寫程序用電腦輕鬆求解。很顯然,對這個問題來說,那把通用性極大的牛刀確實是重了些。但在考試中,尋找“雞刀”所用的時間很可能比用牛刀殺雞的時間還要長。大多數情況下,你開始並不知道這到底是“雞”還是“牛”。拿這把戰無不勝的牛刀,畢竟保證了任務總是能完成的。 看到這個94,我終於明白這個9和4分別是怎麼來的。每一位數不能含1,所以可以放其餘9個數字中任何一個,共9种放法。一共4位數,就是94。我用容斥原理來解,用上海說,似乎是“港督”了(即傻瓜)。然而,這雞刀儘管人人都懂,但要在很短時間內馬上找到,就要有相當的功力了。黑體輻射現象,人們研究了好幾十年,也就找到了長波極限Rayleigh-Jeans公式和短波極限Wien公式,還有博士生的博士論文是用數值方法把這兩個公式擬合起來,最後當普朗克(Planck)發現了黑體輻射公式 I = a / (eb/T - 1),這些前輩們真是可以吐血了。然而,沒人會說前輩們的工作是“港督”。正是他們的工作給了普朗克啟發,從而一舉成功。在現在這個問題,前輩和晚輩都是我自己,港督或聰明人也就無所謂了。事實上,這個最後答案還可以用更簡單的方法加以理解。我們問0-9,999中有幾個數不含9,這和不含1當然是一樣的。這就是說9進制的四位數共有多少值。10進制的四位數有104,2進制的四位數有24,9進制的四位數當然是94了。 現在回到大猩猩演奏貝多芬的問題。我們不妨研究蹦了11億年不出現第五交響樂的幾率,就是N(N為天文數字)位數不含某特定數串的組合數有多少。運用容斥原理,先把總數減去出現至少一次第五交響樂的組合數,再加上出現至少兩次的,直至這N位數再也裝不下第五交響樂了。那個吃飽沒事幹的數學家大概證明了,大猩猩蹦了11億年後,95%的大猩猩至少“演奏”了一次第五交響樂。現在假定我們有個10位數,空缺用0填上(Leading 0),而“第五交響樂”只有三個“音符”123,大猩猩蹦了10次後,0.7985%的大猩猩會演奏出至少一次123。多大的N可保證95%的大猩猩演奏123,我想是沒有“雞刀”的,有興趣的讀者可藉助電腦進行計算。 |
|
|
|
實用資訊 | |
|
|
一周點擊熱帖 | 更多>> |
|
|
一周回復熱帖 |
|
|
歷史上的今天:回復熱帖 |
2009: | 尺規作圖題 | |
2009: | 從“亞他拿修”來看“基督的人性”的定 | |
2008: | 人在行走時所用的能量來源 | |
2006: | 引起法律糾紛的字條. | |