Communications of the ACM
Home/Magazine Archive/February 2009 (Vol. 52, No. 2)/Puzzled: Will My Algorithm Terminate?/Full Text
Last byte
Puzzled: Will My Algorithm Terminate?
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 timeamong mathematicians anywayis 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.
Footnotes
Readers are encouraged to submit prospective puzzles for future columns to [email protected].
DOI: http://doi.acm.org/10.1145/1461928.1461952
©2009 ACM 0001-0782/09/0200 $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