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?
Readers are encouraged to submit
prospective puzzles for future columns
to puzzled@cacm.acm.org.
What is the probability alice
ends up where she started?
Peter Winkler ( puzzled@cacm.acm.org) is William
morrill Professor of mathematics and computer
science at Dartmouth college, hanover, nh.