我們常常要將一群 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隊「種子隊」，每隊「種子隊」在分組賽中不會同組，也是「不是所有可能組合出現的概率也相等」的一個例子。
沒有留言:
張貼留言