为了集齐108将,你得吃多少袋干脆面?

  数学

看到这个文章标题,估计 80 后们都会眼前一亮,脑海里闪过各种回忆吧。几乎每个人都有过满怀欣喜地拆开干脆面,却发现里面附送的水浒英雄卡自己早就有了的悲剧经历;不少人更是“买椟还珠”,买来干脆面不吃,仅仅是为了求得一张未曾收集到的卡片。最后,绝大多数人都未能集齐所有卡片,留下了永久的遗憾。现在再想起这些故事时,或许大家会好奇地问:究竟得买多少袋干脆面,才能集齐 108 将呢?

为了让问题变得更简单,让我们假设干脆面里每一种卡片出现的概率都是均等的。不过,即使在这样的假设下,集齐 108 卡片需要的干脆面数量也远远大于 108。这是因为,虽然刚开始收集时很容易,几乎每次都会看到不一样的卡片,但是越到后来重复的概率也就越高。当你收集到了其中 104 张卡片,只差 4 张卡片时,新买的干脆面里附送的恰好是这 4 张卡片中的一张的概率仅 4/108 = 1/27,也就是说平均还得买 27 袋干脆面才能搞到一张新的卡片。如果就差最后一张卡的话就更艰难了,平均要再买 108 袋干脆面,才能把最后这张收入囊中呢。

类似地,假设你已经收集了 n 张卡片,还有 108 – n 张没有的卡片。那么,下次拆开干脆面,拿到一张新卡片的概率就是 (108 – n)/108,为了拿到一张新卡片平均就需要 108/(108 – n) 袋干脆面。因此,集齐全部 108 张卡片需要的干脆面袋数就是

108/108 + 108/107 + 108/106 + … + 108/2 + 108/1
= 108(1 + 1/2 + 1/3 + … + 1/108)
≈ 568.5

也就是说,为了集齐 108 张卡片,平均需要买 500 多袋干脆面。我简单地调查了一下,发现这个数字似乎比大家想象的要小得多。看来,生产商不得不想办法让 108 张卡片出现的几率不那么均等呢。

这个问题有一个名字,叫做优惠券收集问题(Coupon collector’s problem)。在离散概率中,这是最为经典的问题之一,早在 1957 年《概率论及其应用》(An Introduction to Probability Theory and Its Applications)中就有过介绍。这个理论的应用很广。小编打听到, 果壳青年谱系 测试的题库里一共有 300 道题,因此平均需要回答 300(1 + 1/2 + 1/3 + … + 1/300) ≈ 1884.8 个问题才能答遍所有的问题。由于一次测试有 20 道题,因此平均需要做 94.24 次测试才能把每个问题都见一遍。不过,实际需要的测试次数应该比这个数小,因为系统似乎能避免同一套测试题里有重复的题目。

LEAVE A COMMENT

This site uses Akismet to reduce spam. Learn how your comment data is processed.