Cracking Coding Interview - 6.4 Ants on a Triangle

Ants on a Triangle: There are three ants on different vertices of a triangle. What is the probability of collision (between any two or all of them) if they start walking on the sides of the triangle? Assume that each ant randomly picks a direction, with either direction being equally likely to be chosen, and that they walk at the same speed.

Similarly, find the probability of collision with n ants on an n-vertex polygon.

Hints:#157, #195, #296

解法

因为所有蚂蚁的速度都是一样的，因此不存在快的追上慢的的情况。

什么时候不会撞车？就是大家方向都一致的时候

所以P(撞车) = 1 - P(方向一致)。

方向一致的情况有两种都向左和都向右，因此P(反向一致) = P(都向左) + P(都向右)。

而向左或向右的概率都是0.5，因此 P(撞车) = 1 - 0.5³ - 0.5³ = 0.75

所以如果有n个蚂蚁，那么P(撞车) = 1 - 2 * 0.5ⁿ = 1 - 0.5^{n - 1}（因为0.5 = 1/2）