Communications of the ACM

Last byte

Puzzled: Solutions and Sources

By Peter Winkler
Communications of the ACM, June 2013, Vol. 56 No. 6, Page 117
10.1145/2461256.2461280
Comments

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 2¹² = 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

The Digital Library is published by the Association for Computing Machinery. Copyright © 2013 ACM, Inc.

---

No entries found