一道高盛的面试题,在cupg的论坛里面引发了口水大战。原题如下:一根棍子上面有无数只蚂蚁,假设两只蚂蚁碰到之后就会180度调头反向前进,碰到,再调头,直到棍子的某一头,然后掉下来;然后再假设1只蚂蚁从棍子的这头到那头一共需要5分钟,那么问题是:需要多少时间,这根棍子上所有的蚂蚁会掉下来?
开始的时候,我想的很简单,两只蚂蚁碰到就会掉头,因此相当于对穿前进。因此,一只蚂蚁要爬过整个棍子需要五分钟。
后来有人质疑,怎么论证呢?为什么不可能是别的情况呢?
论坛里的结论,基本是2.5/5/10分钟三种结论。
现在,我基本论证如下:
坚持蚂蚁碰撞的观点。
每只蚂蚁掉下的时间,等于蚂蚁初始前进方向上的距离。我们假定这个距离是随机的。
因此,t分钟内掉下的概率,等于t/5。
每只蚂蚁如此,N只蚂蚁,重复的概率是(t/5)^N。即,N只蚂蚁的情况下,在t分钟内掉下的概率为F(t) = (t/5)^N。
可以求得概率P(t) = N*t^(N-1)/5^N,以及期望,t bar = 5*(1/2)^(1/N)。
当N趋于无限大时,t bar = 5。
没有评论:
发表评论