1. Pentagon Problem
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?
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 ,
and x be the five numbers, summing
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
2 4 8 5 6 …
where the rightmost 0 represents z .
If x is negative, z < z – 1 and flipping
x has the effect of switching z with z – 1
they are now in ascending order. Simultaneously, it does the same for all
pairs z , z – 1 whose indices are shifted
from them by multiples of five. Thus,
flipping labels amounts to sorting z by
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
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
4+ is 4, for a total of 20.
When x 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
…11111 22222 33333 44444 5
5 5 5 5 …
where the first 3 is the z 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.
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 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.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;
All readers are encouraged to submit prospective
puzzles for future columns to firstname.lastname@example.org.
Peter Winkler ( email@example.com) is Professor
of mathematics and of computer science and albert
Bradley third century Professor in the sciences at
dartmouth college, hanover, nh.