Opinion
Computing Applications Last byte

Puzzled: Solutions and Sources

Last month (May 2013) we posed a trio of brainteasers concerning Ant Alice and her ant friends who always march at 1 cm/sec in whatever direction they are facing, reversing direction when they collide.
Posted
  1. 1. Time to fall.
  2. 2. Same order throughout.
  3. 3. There and back.
  4. Author
  5. Footnotes
Dartmouth College Professor of Mathematics and of Computer Science Peter Winkler

This problem has been around for decades, with one version appearing in Francis Su’s "Math Fun Facts" Web column at Harvey Mudd College (http://www.math.hmc.edu/funfacts). Recall that Alice is the middle ant of 25 ants on a meter-long stick, and the problem is to determine by what time she must have fallen off the end of the stick. The key observation—also useful in the other two puzzles—is that if you do not care about the identities of individual ants, you may as well think of them as passing through one another, instead of being bounced. That is, to an observer who thinks (mistakenly) all ants look alike, it appears that each ant simply walks from wherever he or she is to the end of the stick. Since this takes at most 100 seconds, it follows that every ant—including Alice—is off the stick by the time 100 seconds has passed.

Back to Top

2. Same order throughout.

In this problem the ants were placed randomly, and we want to determine the probability that Alice falls off the end she is facing initially. Now suppose, at the beginning, w ants face west, one being Alice. Then, at all subsequent times there will always be exactly w ants facing west (some of whom may have fallen off the west end), so w ants will ultimately fall off the west end of the stick. These ants will be exactly the first w ants counting from the west end at the beginning, since the ants stay in the same order throughout. It follows that Alice falls off the west end exactly when 13 or more ants were initially facing west, which occurs with probability approximately 58%. Since the same calculation applies if Alice initially faces east, the final answer is 58%.

Back to Top

3. There and back.

This problem takes place on a circle, one meter around, with only 12 ants, and the task is to determine the probability that Alice ends up where she started after 100 seconds. The first observation is that if we again ignore ant identities, it appears that each ant simply walks once around the circle. Thus, collectively, the ants’ final 12 positions are the same as their initial 12 positions; the only question is whether Alice ends up at her own initial position or in some other ant’s position. If the latter, the ants’ positions must have rotated, since their cyclic order cannot change. But can this really happen?

Well, suppose k ants face clockwise initially, thus 12–k counterclockwise. We know this collective orientation will continue throughout. Viewing it physically, the ants will, by "conservation of angular momentum," always have a net clockwise momentum of k–(12–k) = 2k–12. If k = 12, then each ant will travel once clockwise around the circle, never colliding, and ending up where it started. If k=6, the net angular momentum will be zero, so again the ants must end up where they began; if k is strictly between 6 and 12, the ants must end up rotated out of position. Similar arguments apply when k is 6 or less, so we conclude that Alice comes back home exactly when k is 0, 6, or 12.

What is the probability that Alice ends up where she began? There are 212 = 4,096 ways to orient the ants, of which two have all the ants in one direction and "12 choose 6" have half the ants clockwise, so the final probability is (2 + (12 choose 6))/4,096, or approximately 22.6%.

Back to Top

Back to Top

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More