Sign In

Communications of the ACM

Last byte

Puzzled: Solutions and Sources


View as: Print Mobile App ACM Digital Library Full Text (PDF) In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook

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 = zi1 + 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 < zi1 and flipping xi has the effect of switching zi with zi1 they are now in ascending order. Simultaneously, it does the same for all pairs zj, zj1 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 upwarda contradiction.

In fact, the algorithm always terminates in at most 2n1 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), 323; www.cecm.sfu.ca/organics/papers/lagarias/paper/html/paper.html.

Back to Top

Author

Peter Winkler (puzzled@cacm.acm.org) is Professor of Mathematics and of Computer Science and Albert Bradley Third Century Professor in the Sciences at Dartmouth College, Hanover, NH.

Back to Top

Footnotes

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

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account
Article Contents:
  • 1. Pentagon Problem
  • 2. Billiard Balls
  • 3. Notorious Collatz Conjecture
  • Author
  • Footnotes
  • ACM Resources