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?
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 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,
T(s + t) = T(s) + T(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.
Solution 3
Observe that, say, the quantity (r - b) mod 3 remains invariant under the conditions of the problem. Originally, it is 13 - 15 = - 2 = 1 (mod 3). Since, it would be 0 if all the chameleons were of the same color. Thus the answer to the question is, no, it is impossible for all chameleons turn the same color.
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
