2008年3月6日 星期四

猜包揼

[這是網友singmay向數學資料庫手記提供的文章。]

我們常常要將一群 2n 個人分成兩個 n 人小組,一個常用的方法是「猜包揼」。用簡單的組合知識可以知道每次「猜包揼」成功分組的概率為 C(2n,n) / 2^(2n) ,例如要將12人隨機分成兩組進行排球比賽,用「猜包揼」的方法每次成功的概率是 231/1024 ,另外一個講法是所需要的次數的期望值為 1024 / 231 = 4.4329 。當n很大的時候,成功的概率會越來越少。一個有趣的事實是所需次數的期望值隨著 n 趨向無限而趨向於 sqrt(n * pi) [1]。人太多的時候這可以很花時間,所以這時很多人會用「數1、2」的方法代替,但大家也知道「數1、2」不是一個很隨機的方法,因為通常大家所在的位置並不是完全隨機的,有沒有辨法保持分組方法的隨機性 [2] 而增加分組方法的效率呢?


其中一個方法是在 2n 個人中預先選定一人離開,跟著用「猜包揼」將剩下的2n-1人分成 n 人及 n-1 人兩組,然後將預先選定的那個人分配入有 n-1 人那一組;由對稱性不難知道這個方法沒有損失隨機性,而每次成功分組的概率則會大大增加,例如當 n=6 時,新的方法的成功概率為 231/512 。細心的讀者會發現這個概率是原先的兩倍,而所需要的次數的期望值則是原來的一半。這並不是巧合。事實上無論 n 是多少,新的方法每次的成功概率皆為原來的兩倍,這可以從恆等式 C(2n-1,n-1) + C(2n-1,n) = C(2n,n) 直接看出來 [3] ,有興趣的朋友不防自己證明作為練習。

在實際應用的時候,由於解釋這個方法要花一點時間,本人慣用的做法是自己不出手顯示「包」或「揼」,當其他人分開為 n 人及 n-1 人兩組後自己便加入有 n-1 人的那一組。如果當中有一些是數學人,他們很快會明白本人的意圖,也理解這個方法也是完全隨機的;但如果當中大部份也不是數學人,他們便會說一句「你做乜嘢唔出呀?玩嘢咩!」與其嘗試解釋這個方法為何可行,不如從頭再猜一次,結果反而浪費了時間。

註:
[1] 這點可以用Stirling’s formula證明。Stirling’s formula是 n! 的近似公式,有興趣的朋友可以在這裡找到一篇很好的介紹:
http://episte.math.ntu.edu.tw/articles/mm/mm_17_2_05/index.html


[2] 這裡隨機的嚴格定義是所有可能組合出現的概率也相等。

[3] 另外一個有趣的解釋是預先被選的那人出「包」或「揼」已沒有所謂,所以成功機會剛好是兩倍。



數學資料庫所作的補充:第一次有網友向我們提供文章作刊登,本會成員都很高興。希望這個先例可以令更多網友提供關於數學的文章作刊登,令手記成為大家交流數學的一個平台吧!

[以下是 marco_dick 的補充。]

關於上文註[2]所講的「所有可能組合出現的概率也相等」,部分讀者可能不明白,所以在此舉一個不是所有可能組合出現概率相等的例子。

設有 2n 個人,若我們先抽出兩人 A 和 B,然後讓餘下的 2n-2 人以 singmay 在文章第一段所講的方法分成兩個 n-1 人的組別,再隨機讓 A 和 B 每個人加入其中一組,那麼每次可成功分組的機會率會由 C(2n,n) / 2^(2n) 增加至 C(2n-2,n-1) / 2^(2n-2) 。

但是,這種分組方法是會令 A 和 B不可能在同一組;換句話說,所有 A 和 B 同組的組合出現的概率是 0,而A 和 B不同組的組合出現的概率則不是 0,所以這個分組方法違背了「所有可能組合出現的概率也相等」這個原則。

不過這種分組方法在現實中是有用的。例如,當 A 和 B 是仇家時……又例如,10個人分兩組打籃球,但當中只有2個人適合打中鋒(Center),那就必需將他們分開在不同的組。

另外,在每四年一屆的足球世界杯,大會每設出8隊「種子隊」,每隊「種子隊」在分組賽中不會同組,也是「不是所有可能組合出現的概率也相等」的一個例子。

沒有留言: