一个不简单的概率问题
我们办公室里放了四盒扑克,以前是在休息时玩一种扑克游戏用的。这种玩法需要 8 个人进行,同时用 4 副牌。玩完后我们洗乱放进了 4 个牌盒里。现在流行打桥牌,桥牌只用一副 52 张就够了,所以我决定清一副出来。清牌的时候,偷懒不想把 4 个牌盒里的牌全倒出来,然后我脑子里就出现了这么一个问题。
假设牌是完全洗乱,均匀随机分布在 4 个牌盒里的,而且每个盒子里都是均等的 54 张。那么需要打开几个牌盒,才能有很大几率(>90%)的保证从中得到一整副牌呢?
当时一个帮忙清牌的牌友说,大概打开 2 盒就够了。我的直觉告诉我,2 盒应该不够,3 盒应该勉强吧。但实际情况是,我们从 3 盒牌里只找到了独立的 53 张。第 54 张牌是从第 4 个盒子里找到的。
当时觉得这个概率问题很有趣,应该也不复杂。便在纸上划了一下。推导了如下公式:
假设有 n 盒洗乱的牌,当我打开其中的 m 盒,从中凑齐一副完整的概率应该是
(1- ( (n-m)/n )^n ) ^ 54
把 m=2 n=4 代入算了一下,概率只有 3%
m=3 n=4 的时候,概率有 81%
今天( 5 月 1 日)重新想了一下,这个问题并不简单。原因下面 zf 的留言里也写了。我的数学不是那么的好,推导公式恐怕比较麻烦。好在我们有 C 语言这个工具,我用 C 写了个程序求解:
#include "stdio.h" #define CARD 54 #define N 4 #define M 3 static int assemble_table[N+1]; static double probability_table[CARD*N][CARD*N]; void init_probability_table() { int i,j; for (i=0;i0) { for (i=n;i =0) { return probability_table[total-1][part-1]; } if (part==N && total==N) { return 1; } p+=draw_ncard(total,part,N); for (i=N-1;i>=0;i--) { double t=draw_ncard(total,part,i); if (t!=0) { t*=probability(total-N,part-i); p+=t; } } probability_table[total-1][part-1]=p; return p; } double calc() { int total=N*CARD; int part=(N-M)*CARD; double p=probability(total,part); return 1-p; } int main() { init_assemble_table(); init_probability_table(); printf("%lf\n",calc()); return 0; }
程序写的很粗糙,不过能计算出答案就够了。代入 N=4 M=2 计算了一下,结果是 0.019088 N=4, M=3 时概率是 0.820296
跟前面那个错误公式得到的答案差不太多,我觉得原因是牌的张数(54) 远大于牌的分组的缘故。
引申一个可以被口算的题:有四张牌,两张大王两张小王,摸两张牌,摸到一对的可能性有多大?我问了好几个人,居然第一反应是 50% (._.!) 当然大家想过 1 分钟后,就可以得到正确的答案了。
Comments
原概率等价于(1-P(从N盒扑克发出去54*(N-M)张牌,其中有N张相同的牌的概率))。
后式概率的通项公式应该能用54个的超几何分布的子式的和表达。即P(其中有4张红心A)+P(其中有4张方片A)*(1-P(其中有4张红心A))+………………
Posted by: XlperTxT | (17) February 8, 2021 02:26 PM
准确结果为
2220569736629156151741670901129196206150503104512/
2707034400465566460140580464472215649960207011165
Posted by: Anonymous | (16) June 28, 2011 11:46 PM
应该是1/6吧?
Posted by: 妞妞 | (15) July 18, 2008 02:10 PM
好像一些分布式文件系统会有类似的算法 :)
前几天我和同事也计划过一个N台机器稳定存储M个文件的构架,用来保证换掉几台机器也不会丢失文件。
Posted by: arden | (14) November 13, 2007 08:25 AM
太值得学习了,概率问题应用于生活中。
最后那个小问题应该是(P22+P22)/P24 = (2+2)/12 = 1/3
最近正好在复习概率,因为要考试了。
Posted by: benjaminsrj | (13) June 17, 2007 02:34 AM
c42 4×3/2 ,再除以2把。6/2
Posted by: dangel | (12) June 9, 2006 01:44 PM
1/3是对的.
Posted by: ywchen2000 | (11) May 26, 2006 06:01 PM
F(n, m) = <br>
n^54 * C(54*(m-1), 54*(n-1))<br>
----------------------------<br>
C(54*m, 54*n)<br>
不知道算对了没?
Posted by: kaikai | (10) May 19, 2006 08:35 PM
是个有趣的问题,我也写了简单的程序算这个的概率:
<pre>
#include"stdio.h"
#include"stdlib.h"
#define CARD 54
#define N 4
#define M 3
#define L 1 // N-M
#define T 100000
#define RAND01 (rand()/(1.0+RAND_MAX))
int main()
{
int i, j, k;
int tagCards[ N*CARD ];
float failed = 0;
for(i=0; i<T; i++){
for(j=0; j<N*CARD; j++) tagCards[j] = 0;
for(j=0; j<L*CARD; j++){ // draw cards:
int ic = N*CARD * RAND01;
while( tagCards[ic] ) ic = N*CARD * RAND01;
tagCards[ic] = 1; // may check cards here for effeciency
}
for(j=0; j<CARD; j++){ // check cards:
int sum = 0;
for(k=0; k<N; k++) sum += tagCards[j*N+k];
if( sum == N ){
failed ++;
break;
}
}
}
printf("succeeding probability = %f\n", 1-failed/T );
return 0;
}
</pre>
这是个超几何分布问题,我觉得其理论公式不大会像chinainvent给的这么简单的。
Posted by: phoolimin | (9) May 12, 2006 05:10 PM
本人算了一下,当(n-m)*54/n为一整数时,概率应为:
(1-((n-m)/n)^n)^((n-m)*54/n)
Posted by: chinainvent | (8) May 11, 2006 12:39 PM
概率是:2/3对哇.
Posted by: lao_mage | (7) May 10, 2006 12:05 PM
呵呵 我也学学云兄的
C 验证附加题[PS:显示问题,尖括号都改成了全角]:
<pre class="mtc_block">
//用随机数来验证几率问题
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
static int cards[]={1,1,2,2};
void rand2Cards(int *c1, int *c2)
{
*c1 = rand()%4;
do
{
*c2 = rand()%4;
}while(*c2 == *c1);//No same
}
int main()
{
int testtimes = 100000;
int successtimes = 0;
int c1,c2;
int i = 0;
srand((unsigned)time(NULL)); //init seed
while(i < testtimes)
{
rand2Cards(&c1,&c2);
if(cards[c1] == cards[c2])
++successtimes;
++i;
}
printf("odds:%.4f",successtimes*1.0/testtimes);
return 0;
}
</pre>
Posted by: Ninstein | (6) May 5, 2006 12:11 PM
“引申一个可以被口算的题:有四张牌,两张大王两张小王,摸两张牌,摸到一对的可能性有多大?”
是1/3吗?
首先随意抽一张,不管花色几率为1
然后问题变成了在余下的3张里抽出那张与已经抽出的那张相同的牌 几率1/3
数学不好 不知道对不
Posted by: Ninstein | (5) May 5, 2006 11:22 AM
我看过你的书啊。忘了名字叫什么了,反正挺喜欢的。
Posted by: 厉害阿 | (4) May 2, 2006 08:03 PM
的确,这个公式不对。正确的公式应该很复杂。
Posted by: Cloud
| (3)
May 1, 2006 07:58 PM
这个公式好象不大对,数出来的是另一个问题的答案:给n个盒子,然后随机往里丢牌,最后m个盒子含有一套完整牌的概率。和原题的区别是这样的结果n个盒子里的牌数量不一定是一样的。
换句话说,原问题中每张牌的分布不是独立的,因为有每个盒子最后牌数一样的约束,所以不是同一个概率^54。
Posted by: zf | (2) May 1, 2006 03:38 AM
在生活中灵活运用知识,很不错
Posted by: Atry | (1) May 1, 2006 02:11 AM