The Ant Collision Problem

Problem :

There are three ants on different vertices of a equilateral triangle. What is the probability of collision (between any two or all of them) if they start walking on the sides of the triangle?
Similarly find the probability of collision with ‘n’ ants on an ‘n’ vertex polygon.  

Solution :

Note that equilateral has nothing to do with how they will collide. Also, ants are allowed to move on the sides only.

For each single ant, it can move towards two directions - clockwise and counter clockwise. Denote them as 0 or 1 If two ants are moving towards two different directions (clockwise and counter-clockwise), they will eventually meet. The ants can only avoid a collision if they all decide to move in the same direction (either clockwise or anti-clockwise).

P (No collision) = number of ways ants can't collide / total number of ways ants can move.
                        = A/ B

As, we discussed A = 2 when all ants move in either counter clockwise or clockwise direction
B = 2^3 as each ant can move in either of direction.

P(No collision) = 2/8 = 0.25

So, P(collision) = 1 - .25 = .75

Another way to get P(No collision) = P(No collision) = P(All ants go in a clockwise direction) + P( All ants go in an anti-clockwise direction) = 0.5 * 0.5 * 0.5 + 0.5 * 0.5 * 0.5 = 0.25

For general n,
P (collision) in general = (2^n-2)/2^n.

For n = 3, P(collision) = 6/8 = 0.75.