Shell's Home

Jul 30, 2010 - 1 minute read - Comments

一根棍上的蚂蚁引发的问题

一道高盛的面试题,在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*(12)^(1/N)。

当N趋于无限大时,t bar = 5。