« 关于 openGL 的 4444 贴图 | 返回首页 | 3d 引擎中对场景数据的接口设计 »

会抽到自己的那张吗？

周末和一个朋友聊天，说是要去阿里巴巴报道了。听说阿里巴巴的入职培训中有个有趣的游戏。所有学员都要在一张纸条上写下自己的一个短期愿望，投进纸箱中。然后大家各抽一张。抽到别人的愿望后，要想办法帮那个人实现愿望，且不能告诉对方是你抽到了他的愿望。

我突然想，如果抽到自己的愿望怎么办？:D

抽到自己的写的那张的概率是 1/n （n 为人数），这个概率和你先抽后抽无关。当人数很多时，概率自然是很小的，但是整个集体中，至少有一个人抽到自己那张的概率看起来却不小。到底是多少呢？我饶有兴趣的算了一下。

简化一下题目，其实就是把 1-n 个自然数，排成一个数列里，至少有一个数字 i 刚好排到第 i 个位置的概率。

n 个数字的全排列有 n! 种，我们只需要计算出，没有一个数字排在它所在次序位置的排列数。

先定义一个函数 f(n) ，表示把 n-1 个数字排到 n 个位置上，每个数字都不在自己位置上的排列数。

可知 f(2)=1 （把 1 排在两个位置上 ， X 1） f(3)=3 （把 1 2 排在三个位置上， X 1 2 ，2 1 X ，2 X 1） ...

再定义一个函数 g(n) ，表示把 n 个数字，排到 n 个位置上，每个数字都不在自己位置的排列数。

可知 g(n+1) = n * f(n) ，这么理解， g(3)=g(1+2) 也就是排 3 个数字时，先把 2 或 3 排到第一个位置。剩下的两个数字中，1 一定不会在自己位置了。另一个数字排到 2 个空位不在自己位置的排列数就是 f(2)

又可以推导出： f(n+1) = g (n) + n * f(n)

这样理解： f(n+1) 可以分成两种情况，一种是空出那个多余的位置，剩下 n 个数字都不在自己位置的排列数即 g(n) ；另一种情况是，从 n 个数字里挑出一个放在多余的位置上，剩下 n-1 个数字去排 n 个空位，这种情况总数为 n 倍的 f(n) 。

两式联立得到 g(n+1) = n * ( g(n-1) + g (n) )

这样，我们就得到了一个递推式。由于已知 g(3) = 2 * f(2) = 2 ；g(4) = 3 * f(3) = 9 ，所以写个程序很容易求出后续数值。

然后来算概率，n 个数时，概率 h(n) = g(n)/n! 。

我用程序计算了前 100 项，发现从第 8 项开始，概率就几乎不变了，稳定在 0.3679 左右。这引起了我的好奇心，然后重新用笔来推导上面的公式。

h(n+1) * (n+1)! = n * ( h(n-1) * (n-1)! + h(n) * n! )

可以得到

和 ( h(n+1) - h (n) ) *(n+1) = h(n-1) - h (n)

我们可以看到， h(n) 这个数列，相邻两项的差是 1/2! , -1/3! , +1/4! ....

因为我们已知，h(2) = g(2) / 2! = 1/2 ， h(3) = g(3) / 3! = 1/3

可以得到 h(n) = 1 -1 + 1/2! - 1/3! + 1/4! - 1/5! .... 1/n!

这看起来是什么？哈，正好是 1/e 的麦克劳林展开式 :D 所以 h(n) 当 n 增大时，它会收敛到 1/e = 0.367879 。且收敛速度极快 :D

结论：当 n 较大(n>5) 时，没有一个人抽到自己那张纸条的概率是 1/e = 36.8% 左右。还句话说，至少有一个人抽到自己写的那个愿望的可能性有 63.2% 左右，这种事情还是很容易发生的，无论人多还是人少。这个概率随 n 变化的量很小。

哈，怎么又绕到欧拉数 e上面去了，数学还真是神奇啊。

云风 提交于 May 25, 2008 10:00 PM |

Comments

((n-1)/n)^n这个答案不对，这应该是每个人抽完之后再放回去再抽的答案。楼主的意思应该是抽完之后不放回的。虽然两个答案的极限是一致的，但是收敛速度不一样，从n=2开始，两个结果就不等了。

Posted by: 周星星 | (26) March 13, 2016 09:09 AM

如果小组之间互换了下纸条呢？

Posted by: Anonymous | (25) September 11, 2012 12:25 PM

还是楼下的方法简单，容易理解。 这个方法的理论基础是概率论中的一个定理：抽签抽中的概率和抽签顺序无关。

Posted by: 海洋 | (24) April 15, 2012 06:25 PM

很简单的联合概率问题，为什么搞的那么复杂呢？ 假设有n个人 第1个人抽不到自己的概率是(n-1)/n 第1和第2个人都抽不到自己的概率是(n-1)/n的2次方 所有n个人都抽不到自己的概率是 (n-1)/n的n次方 验算，(9999/10000)的10000次方，结果是0.36786104，和楼主给出极限一致

Posted by: test | (23) April 23, 2010 03:52 PM

我只想知道 100! 你是怎么用程序算的,我知道是一个158位的大数,能不能给我程序.最好是C程序呀. Email: 282015535@qq.com

Posted by: hanzi | (22) November 19, 2008 10:21 PM

楼主想必是一个技术牛人,很喜欢你的blog,虽然我只学了一点C的皮毛,但是还是很认真的看了你的文章

Posted by: 34 | (21) June 13, 2008 09:16 AM

就是这个题的后面还有一问，我也答不出，这N个人编号为1,2,...,N放至一个数组中，哪些没有拿到自己的号的人，比如说原来是123，变成231了，这个与数组的序号就构成一个环，1->2,2->3,3->1,就是这个环，问的是这样的环的平均长度是多少？

Posted by: Anonymous | (20) June 7, 2008 03:53 PM

云风师兄,好想和你交个朋友啊!我最佩服的不是你的技术水平多高,也不是你多么专业执着.而是你对于金钱的淡泊.我想我的水平也是不错,做游戏也是挺认真的,当然,比起你来,还是有差距的,哈哈.可是有一点我似乎很难做到:我没有你那么一点也不在乎钱.可能是我生来俗气吧,或许是我现在很需要钱吧.我挺希望自已能和你一样淡泊名利

Posted by: 亮 | (19) May 31, 2008 09:19 PM

如果有N个人抽中的概率是多少？怎么算？

Posted by: 笑笑和尚 | (18) May 29, 2008 05:17 PM

我觉得163是中国互联网最有技术实力的一家公司，干什么说到底还是技术是根本。

Posted by: emil | (17) May 28, 2008 11:39 PM

这个和说曹操,曹操 jiu dao,yiyang,hehe,you can bc it chance?

Posted by: Anonymous | (16) May 28, 2008 09:39 PM

哈哈，大家用递归解的比较多。 我说一个不用递归的解法吧。 设A(i）[i＝1，。。。N] 表示第i个人抽到自己的愿望。 很明显， P[A（i）] = 1/n. 由条件概率有： P[A(i)A(j)] = P[A(i)]P[A(j)|A(i)] = 1/n(n-1) （1 无穷大时，该式收敛于1－1/e :-) 叹造物之精妙，赞数学之神奇！

Posted by: 红色警戒 | (15) May 28, 2008 02:38 PM

作为用程序解决生活问题，这是非常好的教材~

Posted by: chinainvent | (14) May 28, 2008 01:47 PM

真是数学天才，我只能说一个字：囧

Posted by: govo | (13) May 27, 2008 01:24 AM

只能说明你很无聊

Posted by: 吴明 | (12) May 26, 2008 11:48 PM

这个是组合数学中一个比较经典的问题，叫更列或者错位排列，就是把n封信放进n个信封并且都放错的方式数，knuth在taocp里讨论过，随便拿一本组合数学的书也都有讲，用递归解比较容易懂，但是得到的递推公式求通项时需要点技巧，最经典的一个解法是用容斥原理。 好像有一年高考题出过一次计算5的derangement，结果随后几届的高中小孩都会玩这个了，呵呵，包括我~~~~ 不过风哥能直接推出来也不容易~~~~~~~~

Posted by: dongxie | (11) May 26, 2008 03:03 PM

g(n+1) = n * f(n) 我没有理解这步是怎么来的，但是你让我看到了数学归纳法的威力

Posted by: ywchen2000 | (10) May 26, 2008 01:52 PM

我的愿望是把英语学好一点!

Posted by: 开心 | (9) May 26, 2008 11:34 AM

下界勘误：省略号后的n应为(n+1)...

Posted by: Kusk | (8) May 26, 2008 10:55 AM

有(n+1)个数时，假设数字“1”选择了位置x，则剩下n个数的放置方法分两种情况： 1）若数字x选择了位置1，则剩下2,3,...,x-1,x+1,...,n共(n-1)个数，且每个数均有自己对应不能摆的位置，故此情况共有g(n-1)种摆法； 2）若数字x不选择位置1，则可将数字x视为新的数字"假1"，相当于"假1",2,3,...,x-1, x+1,...n共n个数字，且每个数字均有自己对应不能摆的位置（"假1"不能摆在位置1），故此情况共有g(n)种摆法。 综1）及2），数字1选择位置x之后共有(g(n-1)+g(n))种摆法，由于位置x有2,3,...,n种选择，故有g(n)=n(g(n-1)+g(n)).

Posted by: Kusk | (7) May 26, 2008 10:12 AM

= = 我的第一反应也是：如果抽到自己的怎么办？ = =

Posted by: kevinlynx | (6) May 26, 2008 10:07 AM

= = 我的第一反应也是：如果抽到自己的怎么办？ = =

Posted by: kevinlynx | (5) May 26, 2008 10:07 AM

题目的原型是伯努利装错信封问题，还的确是欧拉解决的，欧拉威武~

Posted by: Dingding | (4) May 26, 2008 09:06 AM

真是相当有意思!

Posted by: srdrm [TypeKey Profile Page] | (3) May 26, 2008 08:32 AM

一个365人的集体，有与自己同天过生日的人的概率是不是1/365？（排列组合全忘光了）想想不是。但是至少有人同天过生日的概率就很高，据说20多人的团队里概率就超过一半，50多人中几乎肯定有同天过生日的。 有人觉得枯燥深奥，有人觉得生动有趣的概率问题。

Posted by: 老黄牛 | (2) May 26, 2008 08:05 AM

抢个沙发。这个是组合数学中的错排问题。上周刚好在群里让学数学的策划mm做了一下这个题目，结果一个程序dd推出了这个递推公式，呵呵

Posted by: along | (1) May 26, 2008 12:20 AM

Post a comment

非这个主题相关的留言请到：留言本