last byte

DOI: 10.1145/1461928.1461952
Peter Winkler

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

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.

104 CommunICatIons of the aCm | feBRuaRY 2009 | vol. 52 | No. 2