Last byte

Puzzled: Solutions and Sources

Last month (February 2009, p. 104) we posed a trio of brain teasers concerning algorithm termination. Here, we offer some possible solutions. How did you do?
  1. 1. Pentagon Problem
  2. 2. Billiard Balls
  3. 3. Notorious Collatz Conjecture
  4. Author
  5. Footnotes

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 x0, x1, x2, x3, and x4 be the five numbers, summing to s > 0, with indices taken modulo 5. Define a doubly infinite sequence z by z0 = 0 and zi = zi−1 + xi. The sequence z is not periodic but is periodically ascending; zi+5 = zi + s. In the example, the x values are 2,4,–3,1,–3; s = 1; and the z sequence is

… –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 z0.

If xi is negative, zi < zi–1 and flipping xi has the effect of switching zi with zi–1 they are now in ascending order. Simultaneously, it does the same for all pairs zj, zj–1 whose indices are shifted from them by multiples of five. Thus, flipping labels amounts to sorting z by adjacent transpositions.

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 zj < zi; note i+ is finite and depends only on i modulo 5. We let Φ be the sum 0+ + 1+ + 2+ + 3+ + 4+. In the example, 0+ is 0 (since there are no entries smaller than 0 to the right of z0), 1+ is 1, 2+ is 13, 3+ is 2, and 4+ is 4, for a total of 20.

When xi+1 is flipped, i+ decreases by one, and every other j+ is unchanged, so Φ decreases by 1. When Φ hits 0 the sequence is fully sorted so all labels are non-negative and the process must terminate. In the example, 20 steps later the sequence has turned into

… 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 z0 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.

Back to Top

2. Billiard Balls

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 upward—a contradiction.

In fact, the algorithm always terminates in at most 2n−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.

Back to Top

3. Notorious Collatz Conjecture

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), 3–23; www.cecm.sfu.ca/organics/papers/lagarias/paper/html/paper.html.

Back to Top

Back to Top

    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

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