Solution. This puzzle was sent to me by Boris Schein, a mathematician at the University of Arkansas, and appeared in the Fall 1984 International Mathematics Tournament of the Towns. The key is to note that after each meeting of two chameleons, the difference between the number of chameleons of any two colors remains the same or changes by three; it remains the same modulo 3. But in the given population none of these differences is a multiple of three. It follows that we can never get equal numbers of chameleons of two different colors, and, thus, it can never happen that two such numbers are zero.
If there had been two colors (say, red and green) for which the number of chameleons differed by a multiple of 3, meetings of a chameleon from the larger group and blue chameleons could bring the red and green populations to the same number, say, n. After that, n meetings of red with green would (sadly) leave only the blues.
2. non-negative integers Solution. I first heard this puzzle from my substitute math teacher in Fair Lawn Senior High School, Fair Lawn, NJ. Try it with just zeroes and ones, modulo 2, and you’ll see that every pattern reaches 0 0 0 0 in at most four operations. It follows that with ordinary arithmetic, all the numbers become even in at most four moves. But we may as well divide them all by two, though doing so has no effect on the time needed to reach 0 0 0 0. As we proceed this way, the maximum value of
the four numbers can never increase, being halved at least every four operations, and so must eventually hit 0. (If initially the largest number is less than two to the kth power, this argument shows that the number of operations needed to reach 0 0 0 0 is at most 4k.)
If we generalize the problem by using n integers instead of four, we can again reduce the problem to the question of whether every string of n zeroes and ones comes down to all zeroes. This turns out to be true exactly when n is a power of 2.
A different way to generalize was considered in the paper “The Convergence of Difference Boxes” by Antonio Behn, Christopher Kribs-Zaleta, and Vadim Ponomarenko in The American Mathematical Monthly 112, 5 (2005), 426–439. Here, integers are replaced by arbitrary real numbers, and, amazingly, you still get 0 0 0 0 after a finite number of differencing operations— almost always. There is essentially (up to rotation, reflection, translation, and scaling) only one 4-tuple of real numbers that stubbornly refuses to hit all zeroes: 0, 1, q(q- 1), q, where q is the unique real solution of the cubic equationq3 – q2 – q – 1 = 0.
33. Lonely Runner
Solution. This problem, apparently first posed by the mathematician J.M. Wills in 1967 (but later named by Luis God-dyn of Simon Fraser University, Burna-by, B.C., Canada), shows up in a variety of contexts; for example, it turns out to be related to a conjecture concerning graphs, the chromatic numbers of which depend on the axioms of set the-
ory. When the ratios of runners’ speeds are all irrational, it’s easy to prove; it’s when the speeds are related that things get tough. However, recent progress has been made; in 2008, the statement was proved for up to seven runners by Javier Barajas and Oriol Serra (of the Universitat Politècnica Catalunya, Barcelona, Spain) in the Electronic Journal of Combinatorics 15 (2008), R48.
All 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.
Coming Next Month in COMMUNICATIONS
The Metropolis Model
Self-Awareness Networks
Probabilistic Databases
Point/Counterpoint on Education
The 2008 ACM A. M. Turing Award Winner Barbara Liskov
Plus the latest news on fault-tolerance in distributed systems, micro-robots in medicine, and the technical impact of critical thinking.
References:
Archives