last byte
DOI: 10.1145/1467247.1467272
Peter Winkler
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. Pentagon Problem

Solution. This puzzle first appeared, as
far as I know, at the International Math-
ematics Olympiad of 1986. Known to-
day as “the pentagon problem,” it gen-
erated 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 Ber-
nard Chazelle, a computer scientist at
Princeton University. Let x , x , x , x ,
0123
and x be the five numbers, summing
4
to s > 0, with indices taken modulo 5.
Define a doubly infinite sequence z by
z = 0 and z = z + x . The sequence z is
0 i i- 1 i
not periodic but is periodically ascend-
ing; z = z + s. In the example, the x
i+ 5 i
values are 2, 4,– 3, 1,– 3; s = 1; and the z
sequence is

 

…–20412–1152302634 13745 2 4 8 5 6 …

 

where the rightmost 0 represents z .

0

If x is negative, z < z – 1 and flipping
i ii
x has the effect of switching z with z – 1
i ii

they are now in ascending order. Simultaneously, it does the same for all pairs z , z – 1 whose indices are shifted jj

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 or-
der. Let i⁺ be the number of indices j > i for
which z < z ; note i⁺ is finite and depends
ji
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 z ), 1⁺ is 1, 2⁺ is 13, 3⁺ is 2, and
0

4⁺ is 4, for a total of 20.

When x is flipped, i⁺ decreases by i+ 1

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

 

…11111 22222 33333 44444 5 5 5 5 5 …

 

where the first 3 is the z term, and thus
0
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.

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 de-

liberately 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 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.dart-mouth.edu/~pw/papers/sort.pdf. I am indebted to mathematician and writer Barry Cipra of Northfield, MN, for bringing the puzzle to my attention.

 

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.

All readers are encouraged to submit prospective puzzles for future columns to [e-mail].

Peter Winkler ( [e-mail]) is Professor of mathematics and of computer science and albert Bradley third century Professor in the sciences at dartmouth college, hanover, nh.