Sign In

Communications of the ACM

Last byte

Puzzled: Solutions and Sources


View as: Print Mobile App ACM Digital Library Full Text (PDF) In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
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 observationalso useful in the other two puzzlesis 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 antincluding Aliceis 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 12k 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(12k) = 2k12. 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

Author

Peter Winkler (puzzled@cacm.acm.org) is William Morrill Professor of Mathematics and Computer Science, at Dartmouth College, Hanover, NH.

Back to Top

Footnotes

All readers are encouraged to submit prospective puzzles for future columns to puzzled@cacm.acm.org.


©2013 ACM  0001-0782/13/06

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from permissions@acm.org or fax (212) 869-0481.

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


 

No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account
Article Contents:
  • 1. Time to fall.
  • 2. Same order throughout.
  • 3. There and back.
  • Author
  • Footnotes
  • ACM Resources