Communications of the ACM
Home/Magazine Archive/May 2009 (Vol. 52, No. 5)/Puzzled: Understanding Relationships Among Numbers/Full Text
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.
Footnotes
Readers are encouraged to submit prospective puzzles for future columns to [email protected].
DOI: http://doi.acm.org/10.1145/1506409.1506432
©2009 ACM 0001-0782/09/0500 $5.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