Home → Magazine Archive → June 2009 (Vol. 52, No. 6) → Puzzled: Solutions and Sources → Full Text

Puzzled: Solutions and Sources

By Peter Winkler

Communications of the ACM, Vol. 52 No. 6, Page 103

Save PDF

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.

Back to Top

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 k:th 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), 426439. Here, integers are replaced by arbitrary real numbers, and, amazingly, you still get 0 0 0 0 after a finite number of differencing operationsalmost 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 equation q3 q2 q 1 = 0.

Back to Top

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

Back to Top


Peter Winkler ([email protected]) is Professor of Mathematics and of Computer Science and Albert Bradley Third Century Professor in the Sciences at Dartmouth College, Hanover, NH.

Back to Top


ALL readers are encouraged to submit prospective puzzles for future columns to [email protected].

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

©2009 ACM  0001-0782/09/0600  $10.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