Chameleons of Three Colors
The following problem first appeared in the Kvant magazine (1985). It was offered in the 1989 Tournament of Towns competition and included in at least three problem collections ([Cofman, p. 97; Tao, p. 83], and [Stankova and Rike, p. 207]. 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?
|Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander BogomolnyChameleons 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 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
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
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
The combination in question is one of
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,
T(s + t) = T(s) + T(t).
The same, of course, holds modulo 3.
For the initial vector,
Solution 3
Observe that, say, the quantity (r - b) mod 3 remains invariant under the conditions of the problem. Originally, it is
This solution immediately suggests a more accurate and more general formulation:
Prove that a (r, b, y) - configuration is reducible to a single color configuration if and only if at least two of the quantities r, b, y have the same remainder of division by 3.
References
- J. Cofman, What To Solve?, Oxford Science Publications, 1996.
- T. Tao, Solving Mathematical Problems, Oxford University Press
- A Decade of the Berkeley Mathematical Circle, The American Experience, Volume I, Z. Stankova, Tom Rike (eds), AMS/MSRI, 2008
- P. Winkler, Mathematical Mind-Benders, A K Peters, 2007
|Contact| |Front page| |Contents| |Algebra| |Up|
Copyright © 1996-2018 Alexander BogomolnyNo, the condition is not sufficient. For example,
|Contact| |Front page| |Contents| |Algebra| |Up|
Copyright © 1996-2018 Alexander Bogomolny71471355