Probability of collision among ants walking on the sides of 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?
Similarly find the probability of collision with ‘n’ ants on an ‘n’ vertex polygon.

My initial thoughts:
For each single ant, it can move towards two directions. Denote them as 0 or 1. If two ants are moving towards two different directions (clockwise and counter-clockwise), they will eventually meet. Therefore the only case for not having a collision is 0, 0, 0 for the three ants. There are 2^3=8 possible combination of directions. Hence 7/8 probability to have a collision.
For general case, it’s (2^n-1)/2^n.

Solution:
I forgot the case 1, 1, 1, which can also avoid collision. Therefore, for three ants, it’s (8-6)/8=3/4 and in general, it’s (2^n-2)/2^n.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: