設萬維讀者為首頁 廣告服務 技術服務 聯繫我們 關於萬維
簡體 繁體 手機版
分類廣告
版主:
萬維讀者網 > 靈機一動 > 帖子
做一回事後諸葛亮
送交者: 零加一中 2011年09月26日21:43:56 於 [靈機一動] 發送悄悄話

                我很小就從某科普讀物得知,讓大猩猩在鋼琴上蹦11億年,也會演奏出一首貝多芬的第五交響樂。當然,你無法預測11億年中哪個時刻,大猩猩會有此壯舉。以後上了大學對此事有了較清楚的概念。首先,計算需要一些簡化的假定,比如猩猩蹦跳的頻率,還需假定蹦跳是勻速的,所以要對大師的第五交響樂作些假定,什麼餘音繞梁之類,想都不要想。最重要的是,這是統計意義上的,不是說一定會出現。應用通常採取的95%置信區間(Confidence Level),就是說成千上萬隻的大猩猩在鋼琴上亂蹦,經過11億年,95%的猩猩會在無法預知的時間,至少演奏過一次第五交響樂。然而,直至拿到博士學位,對這經過簡化的計算過程,還是一點概念都沒有。

                有一次,一位大學同學(同系同年級,開車不到10分鐘!)問我一個問題,是她女兒的回家作業。在0-99100個數中,多少不含數字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的數,正好含一個12341的數分別被扣、減了1234次。現在把至少含兩個1的加回去,正好含2341的被加了136次。再減去至少含三個1的,正好含341的被減了14次。三次操作一起考慮,正好含1231的恰好被減了各一次。含四個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,我終於明白這個94分別是怎麼來的。每一位數不能含1,所以可以放其餘9個數字中任何一個,共9种放法。一共4位數,就是94。我用容斥原理來解,用上海說,似乎是“港督”了(即傻瓜)。然而,這雞刀儘管人人都懂,但要在很短時間內馬上找到,就要有相當的功力了。黑體輻射現象,人們研究了好幾十年,也就找到了長波極限Rayleigh-Jeans公式和短波極限Wien公式,還有博士生的博士論文是用數值方法把這兩個公式擬合起來,最後當普朗克(Planck)發現了黑體輻射公式 I = a /  (eb/T - 1),這些前輩們真是可以吐血了。然而,沒人會說前輩們的工作是“港督”。正是他們的工作給了普朗克啟發,從而一舉成功。在現在這個問題,前輩和晚輩都是我自己,港督或聰明人也就無所謂了。事實上,這個最後答案還可以用更簡單的方法加以理解。我們問0-9,999中有幾個數不含9,這和不含1當然是一樣的。這就是說9進制的四位數共有多少值。10進制的四位數有1042進制的四位數有249進制的四位數當然是94了。

                現在回到大猩猩演奏貝多芬的問題。我們不妨研究蹦了11億年不出現第五交響樂的幾率,就是NN為天文數字)位數不含某特定數串的組合數有多少。運用容斥原理,先把總數減去出現至少一次第五交響樂的組合數,再加上出現至少兩次的,直至這N位數再也裝不下第五交響樂了。那個吃飽沒事幹的數學家大概證明了,大猩猩蹦了11億年後,95%的大猩猩至少“演奏”了一次第五交響樂。現在假定我們有個10位數,空缺用0填上(Leading 0),而“第五交響樂”只有三個“音符”123,大猩猩蹦了10次後,0.7985%的大猩猩會演奏出至少一次123。多大的N可保證95%的大猩猩演奏123,我想是沒有“雞刀”的,有興趣的讀者可藉助電腦進行計算。

0%(0)
0%(0)
標 題 (必選項):
內 容 (選填項):
實用資訊
回國機票$360起 | 商務艙省$200 | 全球最佳航空公司出爐:海航獲五星
海外華人福利!在線看陳建斌《三叉戟》熱血歸回 豪情築夢 高清免費看 無地區限制
一周點擊熱帖 更多>>
一周回復熱帖
歷史上的今天:回復熱帖
2009: 尺規作圖題
2009: 從“亞他拿修”來看“基督的人性”的定
2008: 人在行走時所用的能量來源
2006: 引起法律糾紛的字條.