Quod Erat Demonstrandum

2011/08/19

某數算題

Filed under: Additional / Applied Mathematics,HKALE,NSS,Teaching — johnmayhk @ 6:34 下午

給學生 98 道「暑期」(注 1)概率題目,這是第 77 題:

If three tickets are chosen at random without replacement from a set of 6n tickets numbered respectively 1, 2,…, 6n, what is the probability that the sum of the numbers on the numbers on the chosen tickets is 6n?

現在講解一下。

易知 possible coutcomes 的數目為 C_3^{6n}

設 3 個被選出的數字為 {x,y,z}。

那麼,favorable outcomes 的數目,就是滿足

\left \{ \begin{array}{ll} x+y+z=6n\\x < y < z\end{array}\right.

的正整數解 (x,y,z) 之數目(為何要有 x < y < z?)。

起碼有兩個方法數算上述正整數解的數目。

【方法一】

x 是 3 個被選出的數字中最小的數,

我們可以由 x=1 開始數起。

x=1 的前提下,有多少個 (x,y,z) 呢?

(1,2,6n-3), (1,3,6n-4), (1,4,6n-5)\dots

「最後一個」是甚麼?

y 值由 2 開始,每次上升 1,z 值由 6n-3 開始,每次下降 1。

y+z=6n-1,且 y < z,故「最後一個」是 (1,3n-1,3n)

x=1 的前提下,有

(1,2,6n-3), (1,3,6n-4), (1,4,6n-5)\dots (1,3n-1,3n)

(3n-1)-2+1 = 3n-2 個可能解。

x=2 的前提下,有

(2,3,6n-5), (2,4,6n-6), (2,5,6n-7)\dots (2,3n-2,3n)

(3n-2)-3+1 = 3n-4 個可能解。

x=3 的前提下,或許同學以為有 3n-6 個,小心!非也。

y+z=6n-3,且 y < z,「最後一個」不是 (3,3n-3,3n),而是 (3,3n-2,3n-1)

即在 x=3 的前提下,有

(3,4,6n-7), (3,5,6n-8), (3,6,6n-9)\dots (3,3n-2,3n-1)

(3n-2)-4+1 = 3n-5 個可能解。

x=4 的前提下,有

(4,5,6n-9), (4,6,6n-10), (4,7,6n-11)\dots (4,3n-3,3n-1)

(3n-3)-5+1 = 3n-7 個可能解。

類似地,考慮 x 值一直上升,到最後,

x=2n-1,只有

(2n-1,2n,2n+1)

這一個可能解。

以下表總結:

觀察到 no. of solution 是形如

3n-k

者,其中 k 不是 3 的倍數(試證明這個現象)。

可見,可能解的數目是

(3n-2)+(3n-4)+(3n-5)+(3n-7)+(3n-8)+\dots +1

= 1+2+4+5+7+8+\dots+(3n-4)+(3n-2)

= 1+2+3+4+5+\dots+(3n-2)-(3+6+9+\dots+(3n-3))

= \frac{(3n-2)(3n-1)}{2}-3\frac{n(n-1)}{2}

= 3n^2-3n+1

故題目要求的概率 = \frac{3n^2-3n+1}{C_3^{6n}}= \frac{3n^2-3n+1}{n(6n-1)(6n-2)}

【方法二】

感到【方法一】太麻煩嗎?我給的解是 \frac{C_2^{6n-1}-1-3(3n-2)}{3!} \div C_3^{6n}

讓我以 n=2 為例,即問滿足

\left \{ \begin{array}{ll} x+y+z=12\\x < y < z\end{array}\right.

的正整數解 (x,y,z) 之數目。

想像有 12 個球,見下

● ● ● ● ● ● ● ● ● ● ● ●

我們以 2 條「竹枝」把 12 個球分三份,比如

● ●│● ● ● ● ● ● ●│● ● ●

即代表了 (2,7,3) 這個解,又比如

● ● ●│● ● ●│● ● ● ● ● ●

即代表了 (3,3,6) 這個解,諸如此類。

那麼,共有多少個 (x,y,z),即共有多少個方法可以把 2 條「竹枝」放在 12 個球之間,較精確說,是放在球與球之間的 11 個位置。可見,共有 C_2^{11} 個方法。

但是,上述數算方法裡,存在 (x,y,z) 不合題意(x < y < z)的情況,正如上述兩個 (2,7,3), (3,3,6) 就是不合了。

現在除去不合的例子:

三個變量相同,即 (4,4,4)。

存在二個變量相同,包括

{1,1,10}
{2,2,8}
{3,3,6}
{5,5,2}

而 {1,1,10} 其實代表著 3 個情況,即

(x,y,z)=(1,1,10),(1,10,1),(10,1,1)

故,「二個變量相同」共有 4\times 3=12 情況。

所以,三個變量不相同的情況有

C_2^{11}-1-4\times 3

個。

但,比如對於三個變量分別為 {1,2,9},代表了

(1,2,9),(1,9,2),(2,1,9),(2,9,1),(9,1,2),(9,2,1)

3!=6 個情況,但只有 (1,2,9) 才合題意(x < y < z),即

三個變量不相同且(x < y < z)的情況有共有

\frac{C_2^{11}-1-4\times 3}{3!}=7

驗算一下

(1,2,9)
(1,3,8)
(1,4,7)
(1,5,6)
(2,3,7)
(2,4,6)
(3,4,5)

共 7 個。

一般地,當三個變量總和是 6n 時,共

C_2^{6n-1}-1-3(3n-2)

個。

注 1:修 core mathematics 的同學,這題純粹無聊的,應該不會在公開試出現,放心。但修應數的同學,這不過是教科書的習題,你應懂的。

1 則迴響 »

  1. 數算題除了要思路清晰還要很小心..
    特別在考試時的緊張氣氛下, 能答對這題的應數考生應該不多吧..
    至少我就是錯的其中一員…

    迴響 由 Lan — 2011/09/02 @ 5:12 下午 | 回覆


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 位部落客按了讚: