# Communications of the ACM

Last byte

## Puzzled: Understanding Relationships Among Numbers

1. A colony of chameleons includes 20 red, 18 blue, and 16 green individuals. Whenever two chameleons of different colors meet, each changes to the third color. Some time passes during which no chameleons are born or die nor do any enter or leave the colony. Is it possible that at the end of this period, all 54 chameleons are the same color?

2. Four non-negative integers are written on a line. Below each number, now write the (absolute) difference between that number and the one to its right (that is, the result of subtracting the smaller from the larger of the two numbers). Below the fourth, write the absolute difference between it and the first number. The result is a new row of four non-negative integers. These four subtractions constitute one "operation" you can repeat on the four new numbers. Now show that after a finite number of such operations, you must reach a point where all four numbers are 0.

For example, if you start with the sequence 43, 11, 21, 3, here's what happens:

As you see, 0 0 0 0 was reached after only four operations.

Try it yourself with, say, random numbers between 0 and 100; you'll be amazed how quickly you get to 0 0 0 0.

Note, however, that if you do the same thing with five numbers, you might never stop.

If you found the first part of this problem too easy, try answering this question: For which n is it the case that this process, beginning with n numbers, always gets you to n zeroes?

3. The "lonely runner," an intriguing open problem in number theory, asks whether the following is true: Suppose you are one of n runners who start together on a circular track one kilometer in length, each running at a different constant speed. Then, at some moment in time you will be at distance at least 1/n kilometers from all the other runners. Note when the ratios between speeds are irrational, as they would, almost surely, be, if the speeds were, say, random real numbers between 0 and 1, then it is indeed true. It's when the speeds are rationally related that things start to get interesting.

### Author

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.

### Footnotes

Readers are encouraged to submit prospective puzzles for future columns to puzzled@cacm.acm.org.

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