Last byte

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. Article
  2. Author
  3. Footnotes

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.

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

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

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More