会抽到自己的那张吗?
周末和一个朋友聊天,说是要去阿里巴巴报道了。听说阿里巴巴的入职培训中有个有趣的游戏。所有学员都要在一张纸条上写下自己的一个短期愿望,投进纸箱中。然后大家各抽一张。抽到别人的愿望后,要想办法帮那个人实现愿望,且不能告诉对方是你抽到了他的愿望。
我突然想,如果抽到自己的愿望怎么办?: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上面去了,数学还真是神奇啊。
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<=i<j)
以此类推: P[A(i)A(J).....A(n)] = 1/n(n-1)(n-2).... = 1/n!
至少有一个人抽到自己的那张是:U[A(1)+ A(2).... + A(n)] 由全概率公式有:P(U) = C(n,1)* 1/n - C(n,2)* 1/n(n-1) + ....... 1/n! = 1-1/2!+1/3!.....1/n!
当 n-> 无穷大时,该式收敛于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
| (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