last byte
DOI: 10.1145/1506409.1506432
Peter Winkler
Puzzled
understanding Relationships
among numbers
Welcome to three new challenging mathematical puzzles. Solutions to the first
two will be published next month; the third is as yet (famously) unsolved. In each
puzzle, the issue is how numbers interact with one another.
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
43
same color?
32
22
14
0
“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.
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?
For example, if you start with
the sequence 43, 11, 21, 3,
here’s what happens:

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

11 21
10 18
8 22
14 14
0 0
3
40
8
14
0
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.

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.

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.