Last byte

Puzzled: Will My Algorithm Terminate?

Welcome to three new challenging mathematical puzzles. Solutions to the first two will be published next month; the third is as yet unsolved. In them all, I concentrate on algorithm termination, outlining some simple procedures and asking whether they always terminate or might possibly run forever.
  1. Article
  2. Author
  3. Footnotes

1. Five integers with positive sum are assigned to the vertices of a pentagon. At any point you may select a negative entry (say, −x) and flip it to make it positive, or x, but then you must subtract x from each of the two neighboring values; thus, the sum of the five integers remains the same. For example, if the numbers are 2, 4, −3, 1, −3, you can either flip the first −3 to get 2, 1, 3, −2, −3 or the second to get −1, 4, −3, −2, 3. Now prove that no matter what numbers you start with and strategy you follow, all the numbers will eventually become nonnegative, and thus the procedure terminates after finitely many steps.

2. Billiard balls numbered 1 through n but not in their correct order lie together in a trough. In a naive attempt to put them in correct order, you repeatedly pick up a ball that is not where it belongs and put it where it does belong; the balls between their old and new positions naturally slide over by one space to accommodate the new ball. For example, if five balls are in the order 1 5 3 4 2, you can pick up ball 2 and place it in the second position to yield 1 2 5 3 4. Because this knocks balls 3 and 4 out of place, it is not obvious that you have made real progress toward 1 2 3 4 5. Now, is there a starting permutation from which, if you choose your steps sufficiently badly, you will never achieve 1 2 3…n?

3. Possibly the most notorious algorithm-termination puzzle of all time—among mathematicians anyway—is the Collatz Conjecture, sometimes called the 3x+1 problem (or the Syracuse problem, Kakutani’s problem, Hasse’s algorithm, or Ulam’s problem). Start with any positive integer and repeat: If it is even, divide by two; if odd, multiply by 3 and add 1. For example, if you start with 22, you get 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1,… The conjecture is that no matter what number you start with, you eventually get down to the same cycle 4, 2, 1, repeating over and over. Watch out though: If you intend to give this problem to your CS 101 students, make sure you have plenty of spare computer time.

Back to Top

Back to Top

    Readers are encouraged to submit prospective puzzles for future columns to puzzled@cacm.acm.org.

    DOI: http://doi.acm.org/10.1145/1461928.1461952

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