世界杯球星卡 - 辕门射虎 - 轩辕春秋文化论坛 20周年


	周瑜


	栎阳侯谏议大夫 ★

组别	翰林学士
级别	征西将军
好贴	10
功绩	943
帖子	4717
编号	1808
注册	2003-11-3
家族	瓦岗寨

#1

发表于 2010-8-13 03:41 资料主页文集短消息看全部作者

世界杯球星卡

几个月前，我买了一盒世界杯球星卡，也许是我运气不好，8张卡片中只认识一个纳尼，因此突然想到一个问题：

球星卡总共有640张，每一盒里包含随机组合的8张不同的球星卡，每张卡片出现的概率相等。求为了凑齐全部640张，需要购买卡片盒数的期望值。

[ 本帖最后由周瑜于 2010-9-8 11:10 编辑 ]

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	周瑜


	栎阳侯谏议大夫 ★

组别	翰林学士
级别	征西将军
好贴	10
功绩	943
帖子	4717
编号	1808
注册	2003-11-3
家族	瓦岗寨

#2

发表于 2010-8-13 21:03 资料主页文集短消息看全部作者

求的是期望值，也就是平均值，指的是运气不好也不坏的情况。

[广告] 《精忠报国岳飞传完整版》火热发布


	周瑜


	栎阳侯谏议大夫 ★

组别	翰林学士
级别	征西将军
好贴	10
功绩	943
帖子	4717
编号	1808
注册	2003-11-3
家族	瓦岗寨

#3

发表于 2010-8-18 00:00 资料主页文集短消息看全部作者

为什么没有人来做题呢？我在这里把题目简化一下吧。

假设每盒卡片只有1张，那么收集全部640张平均需要购买多少盒？这个问题能算出的话，稍稍改进一下也能答出一盒8张的问题了。

[ 本帖最后由周瑜于 2010-8-17 14:36 编辑 ]

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	周瑜


	栎阳侯谏议大夫 ★

组别	翰林学士
级别	征西将军
好贴	10
功绩	943
帖子	4717
编号	1808
注册	2003-11-3
家族	瓦岗寨

#4

发表于 2010-8-24 05:17 资料主页文集短消息看全部作者

公布答案

没有人来答题么，我这就公布答案了。

先考虑简化版的题目，每盒只有一张卡片。定义以前未收集到的卡片为新卡片，那么，显然买第一盒的时候能获得一张新卡片。

买第二盒时，有 1/640 的概率碰上与第一盒相同的卡片，有 639/640 的概率获得一张新卡片，换言之，收集一张卡片后，期望再买 640/639 盒就能收集到第二张卡片。
同理，收集两张卡片后，再买一张卡片 638/640 的概率获得一张新卡片，即收集到第三张卡片所期望购买的盒数为 640/638 。
......
收集 i 张卡片后，再收集第 i+1 张卡片所期望购买的盒数为 640/(640-i)
收集最后一张卡片所期望购买的盒数为 640/1

因此，简化版题目的答案是 ∑(i = 0 to 639) 640/(640-i) = 4505.2575282

再看原题：

设卡片总数为 N ，每盒有不同卡片 k 张，则本题中 N = 640，k = 8
令 p(x) 表示收集到 x 张不同卡片后，为了全部收齐还需要购买盒数的期望值。
易知 p(N)=0， p(0) 为所求答案，p(0) = p(k)+1 ，可由 p(N) 逆推 p(k)，进而求得 p(0)。

假设某时刻已收集 x 张卡片，那么再买下一盒之后可能收集多少张呢？
最坏的情况，下一盒的所有卡片都在以前 x 张中出现过，那么此时的收集数仍为 x 张。
最好的情况，下一盒的所有卡片都不在以前 x 张中出现，或买入下一盒将收集满全部卡片，那么此时的收集数为 min(N, x+k)
令 y = min(N, x+k)

下文中 C(n, m) 表示 n 中选 m 的组合数，其值为 n!/(m!(n-m)!)
由上，收集 x 张卡片后新买一盒可能增加的卡片数在 0 到 y-x 之间。设新增卡片数为 i ，则其概率为：
q(i) = C(x, k-i) * C(N-x, i) / C(N, k)
即在已收集的 x 张中选出 k-i 张，未收集的 N-x 张中选出 i 张。

然后，根据条件期望，可得出：
p(x) = ∑(i = 0 to y-x) q(i)*(1+p(x+i))

最后，代入N=640，k=8，解方程逐步求出 p(N-1) 到 p(k) 所有值，最终结果为 560.5076664

[ 本帖最后由周瑜于 2010-8-24 13:12 编辑 ]

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！