Last byte
# Puzzled: Solutions and Sources

*Solution.* This puzzle first appeared, as far as I know, at the International Mathematics Olympiad of 1986. Known today as "the pentagon problem," it generated enormous interest and a variety of imaginative solutions. I present one of them here, due independently to at least two people, one of whom is Bernard Chazelle, a computer scientist at Princeton University. Let *x*_{0}, *x*_{1}, *x*_{2}, *x*_{3}, and *x*_{4} be the five numbers, summing to *s* > 0, with indices taken modulo 5. Define a doubly infinite sequence *z* by *z*_{0} = 0 and *z _{i}* =

... 2 0 4 1 2 1 1 5 2 3 0 2 6 3 4 1 3 7 4 5 2 4 8 5 6 ...

where the rightmost 0 represents *z*_{0}.

If *x _{i}* is negative,

Tracking the progress of the sorting process needs a potential function to measure the degree to which *z* is out of order. Let *i*^{+} be the number of indices *j* > *i* for which *z _{j}* <

When *x _{i}*

... 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 ...

where the first 3 is the *z*_{0} term, and thus the numbers around the pentagon are now 0, 0, 0, 0, 1.

We conclude that the process terminated in exactly the same number (the initial value of ) of steps regardless of choices, and the final configuration is independent of choices. The reason is there is only one sorted version of *z*. Moreover, the proof works with 5 replaced by any integer greater than 2.

*Solution.* If you've played with this puzzle you've found that the algorithm does seem to terminate, no matter where you start or what you do, but can take rather a long time to do so. One might hope that (as in Puzzle 1) some non-negative-integer-valued "potential function" must go down at each step, proving that the algorithm must terminate, though there seems to be no simple one here. For example, you might have noticed that the sum of the distances between each billiard ball's current position and where it belongs cannot go up; alas, it may not go down either.

The following argument was devised by Noam Elkies, a mathematician at Harvard University. The ball that is deliberately moved to its correct position in a given step is said to be "placed." Suppose there is an infinite sequence of steps. Then, since there are only finitely many possible states (permutations), there must be a cycle; so, let ball *k* be the highest-numbered ball placed *upward* in the cycle. (If no ball is placed upward, the lowest-number ball placed downward is used in a symmetric argument). Once ball *k* is placed, it can be dislodged upward and placed downward again, but nothing can ever push it below position *k*. Hence it can never again be placed upwarda contradiction.

In fact, the algorithm always terminates in at most 2^{n}^{1} 1 steps, but there are more than exponentially many permutations that can take exactly the maximum number of steps to sort. These and other results, plus some history of this horribly inefficient sorting algorithm can be found at math.dartmouth.edu/~pw/papers/sort.pdf. I am indebted to mathematician and writer Barry Cipra of Northfield, MN, for bringing the puzzle to my attention.

Readers interested in the rich history of this puzzle will appreciate a delicious survey article by Jeffrey C. Lagarias of the University of Michigan in *American Mathematical Monthly 92* (1985), 323; www.cecm.sfu.ca/organics/papers/lagarias/paper/html/paper.html.

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

DOI: http://doi.acm.org/10.1145/1467247.1467272

**©2009 ACM 0001-0782/09/0300 $5.00**

Permission to make digital or hard copies of all or part 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 the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

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

No entries found