One Dimensional Ants

Ants on a stick may only march left or right, all with the same constant speed. They never stop, short of falling off the stick. When two ants bump into each other they bounce and reverse their directions.

Assume 25 ants were randomly dropped on a 1 meter stick and move with constant speed of 1 m/sec. 25 ants create real commotion marching this way and that way, bouncing off each other, and occasionally falling off the stick.

For a solitary ant it may take anywhere from 0 to 100 seconds to reach an edge of the stick and then fall off, depending on its position and orientation. The worst case scenario occurs when the ant is originally located at one edge of the stick and is oriented towards the other end. Generally speaking, the exact time for the stick to become ant free depends on the distribution of ants and their initial orientations. The worst case scenario, for a given number of ants, is such a configuration of their initial locations and orientations that results in the longest time for all of them fall off the stick.

Solution

Copyright © 1996-2009 Alexander Bogomolny

P. Winkler [Mind-Benders, pp 36-38, A Lifetime, pp 177-180] lists the sources of the problem and offers an enlightening solution.

Solution

Imagine that each ant carries a flag. Let's stipulate that when they bump into each other, in addition to reversing their directions, they exchange the flags. The usefulness of the introduction of the flags stems from the following observations:

Since within 100 seconds each flag will have fallen off the stick, 100 seconds is the longest for the stick to become flag (and hence ant) free.

A slight modification of the solution may be even more suggestive. Instead of endowing each ant with a flag, let's paint each with a special kind of individual colors. Let's request that at the time of a meeting the two ants exchange their colors. Since otherwise that ants are indistinguishable, observing their movements one would never see their bumping into each other. The ants will just go through each other as if each was the only ant around.

References

1. P. Winkler, The Adventure of Ant Alice, in A Lifetime of Puzzles, E. D. Demaine et all (eds), A K Peters, 2008
2. P. Winkler, Mathematical Mind-Benders, A K Peters, 2007

Copyright © 1996-2009 Alexander Bogomolny