Quod Erat Demonstrandum

2008/07/04

Just answer an applied mathematics question

Filed under: Additional / Applied Mathematics,HKALE — johnmayhk @ 5:26 下午

Just answer an applied mathematics question from a F.6 student.

Book 4A Ex 2(a) No.19.

An urn consists of n tickets labelled 1, 2, 3, …, n. Tickets are drawn one by one without replacement. What is the probability that in these n draws, there is at least one for which the number on the ticket corresponds to the number of draw.

The following is a solution given by the student.

1. Denominator is n! because there are n tickets lining up for n size of queue.

2. For P(1), there are nC1 ways for the 1 ticket which is corresponding to no. of draw and the rest n-1 tickets are lining up for n-1 size of queue. So P(1)=nC1(n-1)!/n!.

3. Similarly, P(2)=nC2(n-2)!/n!, P(3)=…, P(n)=nCn/n!

4. P(1)+P(2)+…+P(n) is the answer

5. Hence the answer is [nC1(n-1)!+nC2(n-2)!+nC3(n-3)!+…+nCn]/n! = 1+1/2!+1/3!+…+1/n!

Obviously, the answer is not correct because it is greater than 1. So, what’s wrong?

從第 4 步 P(1)+P(2)+…+P(n) 看到同學心中的 P(k) 代表 exactly k 張票的票號配合抽票次序(記曰『配合的』)。運用加法 P(1)+P(2)+…+P(n),一定要確保 P(1), P(2) , …, P(n) 是兩兩互斥(mutually exclusive)。可是,同學在計算 P(k) 時出了問題。單看看同學計 P(1) 時,要算的是 exactly 1 張票是『配合的』。不錯,分母 n! 代表所有可能的排列。不錯,nC1 代表在 n 張票選一張做『配合』的票。然而,(n-1)! 只是代表餘下的 (n-1) 張票的排列數,並不能確保餘下的 (n-1) 張票都『不配合』(因為 P(1) 代表只有一張票是『配合』,其他 (n-1) 張是『不配合』),所以 (n-1)! 是多算了!當然最後得出大於 1 的答案。況且,如同學的算法:P(1) = nC1(n-1)!/n! 和 P(2) = nC2(n-2)!/n! 都不能保證是互斥事件,『加』法則已無效。

要處理這問題,都是慣常用的『容斥原理』。設 A_k 代表第 k 張票是『配合的』,則題目問的是 P(A_1\bigcup A_2 \bigcup \dots \bigcup A_n)。這和所謂『入信封問題』方法一樣,請參考:

http://johnng.inscyber.net/apm/pa_expand_union.doc

1 則迴響 »

  1. oic~thx
    看埋個入信封問題的document終於明白佢個(-1)^(n+1)係點走出來…

    迴響 由 Sit — 2008/07/04 @ 11:05 下午 | 回覆


RSS feed for comments on this post. TrackBack URI

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

在WordPress.com寫網誌.

%d 位部落客按了讚: