Chinaunix

标题: 进来算到题 [打印本页]

作者: 石油工人干IT 时间: 2007-03-22 14:27
标题: 进来算到题
一年有365天，如果有366人，可以保证以概率100％找到一对生日相同的人。现在问题是，至少需要多少个人才能保证以50％的概率找到两个生日相同的人。

想了2个小时，还是不知道怎么算。

进来算哈。

作者: flw 时间: 2007-03-22 14:36
任意找 50 个人，就可以保证 99% 的机会有两个人生日相同。

作者: 石油工人干IT 时间: 2007-03-22 14:37

原帖由 flw 于 2007-3-22 14:36 发表
任意找 50 个人，就可以保证 99% 的机会有两个人生日相同。

怎么算出来的

我算不出来

作者: yuangong 时间: 2007-03-22 14:40
概率学

作者: 石油工人干IT 时间: 2007-03-22 14:43

原帖由 yuangong 于 2007-3-22 14:40 发表
概率学

学过概率

没听说过概率学

怎么算

作者: emacsnw 时间: 2007-03-22 14:47

原帖由 石油工人干IT 于 2007-3-21 22:27 发表
一年有365天，如果有366人，可以保证以概率100％找到一对生日相同的人。现在问题是，至少需要多少个人才能保证以50％的概率找到两个生日相同的人。

想了2个小时，还是不知道怎么算。

进来算哈。

问题等价与多少个人，生日各不相同的概率小于等于0.5.
365*364*...*(366-x) / 365^x <= 0.5
365!/((365-x)! * 365^x) <= 0.5
两边取对数：
f(x)=log_gamma(366) - log_gamma(366-x) - x * log(365) + log(2) <= 0
写个程序试一下，发现当x>=23时，f(x)第一次<=0

x=1, f=0.6931
x=2, f=0.6904
x=3, f=0.6849
x=4, f=0.6767
x=5, f=0.6656
x=6, f=0.6518
x=7, f=0.6353
x=8, f=0.6159
x=9, f=0.5937
x=10, f=0.5688
x=11, f=0.5410
x=12, f=0.5104
x=13, f=0.4770
x=14, f=0.4407
x=15, f=0.4016
x=16, f=0.3596
x=17, f=0.3148
x=18, f=0.2671
x=19, f=0.2165
x=20, f=0.1631
x=21, f=0.1067
x=22, f=0.0475
x=23, f=-0.0147
x=24, f=-0.0798
x=25, f=-0.1478
x=26, f=-0.2188
x=27, f=-0.2927
x=28, f=-0.3695
x=29, f=-0.4493
x=30, f=-0.5321

作者: 石油工人干IT 时间: 2007-03-22 14:50

原帖由 emacsnw 于 2007-3-22 14:47 发表

问题等价与多少个人，生日各不相同的概率小于等于0.5.
365*364*...*(366-x) / 365^x <= 0.5
365!/((365-x)! * 365^x) <= 0.5
两边取对数：
f(x)=log_gamma(366) - log_gamma(366-x) - x * log(365) ...

厉害
答案就是23。

我想了很久都不知道怎么算。

作者: emacsnw 时间: 2007-03-22 14:52
另外楼主的题要求的概率随着人数x结果大致这样：
x=1, prob=0.000000
x=2, prob=0.002740
x=3, prob=0.008204
x=4, prob=0.016356
x=5, prob=0.027136
x=6, prob=0.040462
x=7, prob=0.056236
x=8, prob=0.074335
x=9, prob=0.094624
x=10, prob=0.116948
x=11, prob=0.141141
x=12, prob=0.167025
x=13, prob=0.194410
x=14, prob=0.223103
x=15, prob=0.252901
x=16, prob=0.283604
x=17, prob=0.315008
x=18, prob=0.346911
x=19, prob=0.379119
x=20, prob=0.411438
x=21, prob=0.443688
x=22, prob=0.475695
x=23, prob=0.507297
x=24, prob=0.538344
x=25, prob=0.568700
x=26, prob=0.598241
x=27, prob=0.626859
x=28, prob=0.654461
x=29, prob=0.680969
x=30, prob=0.706316
x=31, prob=0.730455
x=32, prob=0.753348
x=33, prob=0.774972
x=34, prob=0.795317
x=35, prob=0.814383
x=36, prob=0.832182
x=37, prob=0.848734
x=38, prob=0.864068
x=39, prob=0.878220
x=40, prob=0.891232
x=41, prob=0.903152
x=42, prob=0.914030
x=43, prob=0.923923
x=44, prob=0.932885
x=45, prob=0.940976
x=46, prob=0.948253
x=47, prob=0.954774
x=48, prob=0.960598
x=49, prob=0.965780
x=50, prob=0.970374
x=51, prob=0.974432
x=52, prob=0.978005
x=53, prob=0.981138
x=54, prob=0.983877
x=55, prob=0.986262
x=56, prob=0.988332
x=57, prob=0.990122
x=58, prob=0.991665
x=59, prob=0.992989
x=60, prob=0.994123
x=61, prob=0.995089
x=62, prob=0.995910
x=63, prob=0.996604
x=64, prob=0.997190
x=65, prob=0.997683
x=66, prob=0.998096
x=67, prob=0.998440
x=68, prob=0.998726
x=69, prob=0.998964
x=70, prob=0.999160
x=71, prob=0.999321
x=72, prob=0.999453
x=73, prob=0.999561
x=74, prob=0.999649
x=75, prob=0.999720
x=76, prob=0.999777
x=77, prob=0.999824
x=78, prob=0.999861
x=79, prob=0.999891
x=80, prob=0.999914
x=81, prob=0.999933
x=82, prob=0.999948
x=83, prob=0.999960
x=84, prob=0.999969
x=85, prob=0.999976
x=86, prob=0.999982
x=87, prob=0.999986
x=88, prob=0.999989
x=89, prob=0.999992
x=90, prob=0.999994
x=91, prob=0.999995
x=92, prob=0.999997
x=93, prob=0.999997
x=94, prob=0.999998
x=95, prob=0.999999
x=96, prob=0.999999
x=97, prob=0.999999
x=98, prob=0.999999
x=99, prob=1.000000
x=100, prob=1.000000

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)