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₀, 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_i = z_i−1 + x_i. The sequence z is not periodic but is periodically ascending; z_i+5 = z_i + 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 z₀.

If x_i is negative, z_i < z_i–1 and flipping x_i has the effect of switching z_i with z_i–1 they are now in ascending order. Simultaneously, it does the same for all pairs z_j, z_j–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 z_j < z_i; 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_i+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 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.

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 2ⁿ⁻¹ – 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