Quod Erat Demonstrandum


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)。這和所謂『入信封問題』方法一樣,請參考:



1 則迴響 »

  1. oic~thx

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

RSS feed for comments on this post. TrackBack URI



WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )


您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s


%d 位部落客按了讚: