Communications of the ACM

last byte

DOI: 10.1145/2447976.2447998
Peter Winkler
Puzzled
ant alice’s adventures

These three puzzles involve my favorite ant, Ant Alice. Like all ants on this page, Alice moves at exactly one centimeter per second in whichever direction she happens to be facing; if she meets another ant head on, both immediately reverse direction and walk away from each other, each still at speed 1 cm/sec. Figuring out how Alice and her friends behave is surprisingly easy if viewed the right way; here’s a tip: Certain physical principles may play a role in your reasoning.

1.Ant Alice is the middle ant of 25 ants on a
meter-long stick, some facing
east, some facing west. (We
may assume ants are tiny
compared to the distances
between them, so they can be
thought of as moving points.)
At a signal, all begin to march
in whichever direction they
are currently facing, bouncing
and reversing direction
whenever two collide. Those
reaching the end of the stick
fall off and float gently to the
ground (no ants were harmed

A

in the creation of these
puzzles). How long must we
wait before we are sure Alice
has fallen off the stick?
2.Suppose the ants’ initial positions, and the
directions they face, are
uniformly random. What is the
probability that when Alice falls
off the stick, she falls off the
end she was initially facing?

3.Suppose Alice is one of only 12 ants, each initially placed uniformly at random on a circle of length (circumference) one meter (see the figure here). Each ant initially faces clockwise or counterclockwise with equal probability. At a signal, they begin marching (and bouncing off one another) according to the usual rules. What is the probability that 100 seconds later Alice will find herself exactly where she began?