Chameleons of Three Colors
The following problem first appeared in the Kvant magazine (1985). It was offered in Tournaments of Towns competition (1989) and included in at least two problem collections ([Cofman, p. 97, and Tao, p. 83]. We discuss an interactive variant elsewhere.
| |
Chameleons on an island come in three colors. They wonder and meet in pairs. When two chameleons of different colors meet, they both change to the third color. Given initial amounts of the lizards of each color are 13, 15, and 17, may this happen that, after a while, all of them acquire the same color?
|
Solution
Copyright © 1996-2008 Alexander Bogomolny
Solution 1
Assume the three colors are red, blue and yellow and the letters r, b, and y stand for the number of chameleons of a particular color. For convenience, we combine the numbers into a vector (r, b, y) so that (13, 15, 17) represent the original state of affairs.
An encounter between a pair of chameleons of different colors can be described as addition of one of the three vectors
| |
u = (-1, -1, 2), v = (-1, 2, -1), w = (2, -1, -1)
|
to the current "state" vector (r, b, y). The trick is to consider all operations modulo 3. In the arithmetic modulo 3, all three "encounter" vectors are equal:
| |
u = (2, 2, 2), v = (2, 2, 2), w = (2, 2, 2)
|
and the initial vector, say V, is
| |
V = (13, 15, 17) = (1, 0, 2) (mod 3).
|
Observe that
| |
(1, 0, 2) + (2, 2, 2) = (0, 2, 1) (mod 3),
(0, 2, 1) + (2, 2, 2) = (2, 1, 0) (mod 3),
(2, 1, 0) + (2, 2, 2) = (1, 0, 2) (mod 3).
|
We see that, with the initial vector (1, 0, 2) modulo 3, the only possible combinations of colors on the island are (1, 0, 2), (0, 2, 1), and (2, 1, 0), and these occur cyclically with period 3.
The combination in question is one of (45, 0, 0), (0, 45, 0), or (0, 0, 45), all of which are (0, 0, 0) (mod 3). None may appear in the 3-cycle of possible configurations.
Solution 2
A different approach has a more arithmetic flavor. Introduce a function T - the Total color - as
| |
T(r, b, y) = 0·r + 1·b + 2·y = b + 2y.
|
T is a linear function. In particular, for two vectors s and t,
The same, of course, holds modulo 3.
For the initial vector, T(V) = 2·2 = 1 (mod 3). For the "encounter" vector, T(2, 2, 2) = 0 (mod 3) so that no encounter modifies the value of function T which, thus, remains always the same, 1. However, for the vector in question, T(0, 0, 0) = 0 (mod 3) proving the impossibility of reaching such a combination under conditions of the problem.
References
- J. Cofman, What To Solve?, Oxford Science Publications, 1996.
- T. Tao, Solving Mathematical Problems, Oxford University Press
Copyright © 1996-2008 Alexander Bogomolny
No, the condition is not sufficient. For example, (2, 2, 2) is not reducible to a single shape at all. (1, 1, 1) is not reducible either. Try them.
Copyright © 1996-2008 Alexander Bogomolny
|
