Communications of the ACM

Last byte

Puzzled: Solutions and Sources

By Peter Winkler
Communications of the ACM, June 2009, Vol. 52 No. 6, Page 103
10.1145/1516046.1516069
Comments

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), 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 equation q³ − q² − 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

Back to Top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.

---

No entries found