小学堂：从生日悖论到“能获得赠票”的最佳位置

前段时间，微博上有位科普博主提出一个了百万年薪(应该是玩笑)面试题：电影院搞优惠活动，排队的人里面，首个和前面某人(不特定)的生日相同的那位，可以获赠票。就是说，前面n个人，生日都不同，第n+1人的生日和前面某个人重复，则第n+1个人拿到赠票。

现在，因为你充了VIP，所以获得一项特权:可以决定自己在队列里的位置。

问：你应该站在哪里，才能使自己中奖的概率最大。

因为这个问题解答起来比较繁琐，基本上不可能笔算完成，所以就不放到#小体操栏目里——直接讲解一下这个问题。

首先，或许大家听说过著名的“生日难题”或“生日悖论”。

试问：若n个人里，存在生日相同的两人的概率大于50%，则n最小是多少？

实际上，n的最小值远小于大多数人直觉上的那个数字，所以也被称为悖论——虽然毫无“悖论”之处。

n=23时，则n个人里，存在生日相同的两人的概率就大于50%。

因为后面会用到，先稍微解释一下计算方法。

首先忽略闰年，把1年365天的日期，看做是从1-365的数字编号。

我们不直接计算“n个人里有两人生日相同的概率”——记为P(n)，而是计算“n个人里所有人生日全不相同的概率”——则为1-P(n)。

显然，若n＞365，则根据抽屉原理，必然有两人生日一样。所以，下面仅考虑n＜365的情况。

房间n个人，要计算所有人的生日都不相同的概率。那么第一个人的生日是 365 选 365，第二个人是 365 选 364，第三个人 365 选 363 …… 第 n 个人的生日是 365 选 365-(n-1)。所以所有人生日都不相同的概率为

1-P(n)=1*(364/365)*(363/365)*……*[(365-n+1)/365]

剩下的就是数值计算技巧，或直接编程解决，可以发现P(23)＞0.5。上面这个算法还被用于生日攻击——一种密码学攻击方法。

这个问题看起来和我们的原始的排队位置问题有点关系，但又不同。

实际上，我们需要的是那个P(n)的表达式(把数字1挪到等式右边即可得到)。

现在，大家不妨思考一下，最佳的位置到底代表着什么。

显然，n越大，P就越接近1。也就是说，你站到n+1的位置时，虽然可以让P更大，但是，排在你前面的n个人里可能早已存在生日相同的两人。

所以，关键点不是具体P(n)的大小，而是 P(n)-P(n-1)!

上面的式子代表第n个位置，所占据的概率份额。

当然，关于P(n)-P(n-1)，手算就更加不要想了。有人编程计算，得到如下结果
小学堂：从生日悖论到“能获得赠票”的最佳位置

查表(delta p(n)那列)知，n=20时，第n个位置所占据的概率份额最大。这就是原问题的答案。

Recommend