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隊「種子隊」,每隊「種子隊」在分組賽中不會同組,也是「不是所有可能組合出現的概率也相等」的一個例子。

1 則留言:

blog marketing 提到...

飞龙搬家公司,是一家专业性北京搬家公司,企业诚信,员工搬运专业,是北京搬家公司行业的后起新秀,公司长期为搬家免费纸箱。欢迎重询!
公兴上海搬场公司是经工商,税务,交通部注册的一家专业性的上海搬家公司,诚实信誉,工作细心,服务热情;为上海搬场,上海搬家的企业,如有需求,敬请垂询本搬场公司
海胜数码快印有限公司,致力于数码印刷,诚实信誉,实力雄厚,技术专业,设备先进,设计新颖,是北京数码印刷行业中新秀一支,愿做北京数码快印需求者的忠诚合作伙伴!
佳佳乐月嫂服务中心,精心提供月嫂服务,育儿嫂服务,育婴师服务,本中心月嫂,育儿嫂,育婴师,均通过健康体验,经过严格培训,持
证上岗.
华夏国际机票预定中心,全程代销各航机票
,特价机票,北京特价国际机票,留学生机票,打折机票,打折的价格,增值的服务
, 国际机票预订中心精心哈护你的远航!
星云科技,诚信于教育;研究出电子起电机,语音室,语言实验
,数字探究实验室,数字化实验室,探究实验室,系列探究实验配套设施,望广大院校前来考察!
北凝科技,废汽,余热回收,热力除氧改造,凝结水
治理专家,其推出的,定连排,烟囱余热回收器,乏汽回收,低位热力除氧器,凝结水回收器,冷凝水,
等系列产品.
北京防水堵漏公司、专业承接防水
防水堵漏地下室防水地下室堵漏北京防水北京防水堵漏北京防水公司北京防水网.防水堵漏专家! 工作心细,滴水不漏!
 北京爱福石材养护有限公司是专业从事石材翻新,石材结晶,石材护理,石材清洗,石材养护的企业,专业提供:石材翻新,石材结晶,石材清洗,石材护理,石材养护,石材无缝处理,石材防护,石材防滑,石材病症预防处理,石材修补,石材日常保养等业务.服务专线010-82922015