Ants walk

Ants walk

Postby Guest » Wed Dec 28, 2016 1:47 pm

N ants are randomly placed on a circle with diameter of 1m. Each ant starts walking along the circle at a random direction, clockwise or counter-clockwise. All ants walk at the same speed, 1m/sec and when two of them meet, they bounce off each other and change direction. One of the
ants is named Alice. Can you calculate the probability that Alice is back to the point where she started, 1 minute after the ants start
walking?





Guest
 

Re: Ants walk

Postby Guest » Wed Dec 28, 2016 4:42 pm

The probability that after 1 minute that any ant is where Alice started is zero.

You most probably got the question wrong or were told it wrong. If instead the circumference was 1m then the question would be interesting, as every second the ants would be in the same positions as when they started just permuted slightly.

The question was most probably taken from
http://gurmeet.net/puzzles/ants-in-a-circle/
which was incorrectly copied from
http://www.cs.cmu.edu/puzzle/puzzle9.html
which has a version of the question which makes sense and is interesting.
The site also outlines a solution.

Hope this helped,

R. Baber.

Guest
 

Re: Ants walk

Postby Guest » Fri Dec 30, 2016 10:08 am

So the second version concludes that, in order for Alice to return to her original location, she must be either the first or the last or the middle Ant?
So, if there are, say, 20 ants in total, the probability is 3/20?

Guest
 

Re: Ants walk

Postby Guest » Fri Dec 30, 2016 10:09 am

Happy new year to all of you! May you have a great time these days and the year to come brings you health, joy and luck!

Guest
 

Re: Ants walk

Postby Guest » Fri Dec 30, 2016 10:59 am

No, in the correct version of the problem, Alice ends up where she started, if all the ants are going in the same direction (clockwise or anti-clockwise) or if the number of ants going clockwise is the same as the number going anti-clockwise (this can only ever happen if there are an even number of ants).

So for 20 ants, the probability is [tex]\frac{1}{2^{20}}+\frac{1}{2^{20}}+\frac{1}{2^{20}}\binom{20}{10} = \frac{92379}{524288} = 0.176...[/tex]

R. Baber.

Guest
 

Re: Ants walk

Postby Guest » Sat Dec 31, 2016 1:21 pm

Thank you R. Baber!

Guest
 


Return to Math Riddles



Who is online

Users browsing this forum: No registered users and 1 guest