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 puzzled@cacm.acm.org.
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.
104 CommunICatIons of the aCm | feBRuaRY 2009 | vol. 52 | No. 2