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?

Solution

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

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

  1. J. Cofman, What To Solve?, Oxford Science Publications, 1996.
  2. T. Tao, Solving Mathematical Problems, Oxford University Press
  3. A Decade of the Berkeley Mathematical Circle, The American Experience, Volume I, Z. Stankova, Tom Rike (eds), AMS/MSRI, 2008
  4. P. Winkler, Mathematical Mind-Benders, A K Peters, 2007

Related material
Read more...

  • A Three Pegs Question
  • Solitaire on a Circle
  • Peg Solitaire
  • The Game of Fif
  • Nim
  • Sums and Products
  • Splitting Piles
  • Moving Chips in Pairs Down a Checkerboard
  • White and Black Balls in Urn. 1 in, 2 out. What Color Remains?
  • Extension of Euclid's Game
  • |Contact| |Front page| |Contents| |Algebra| |Up|

    Copyright © 1996-2018 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.

    |Contact| |Front page| |Contents| |Algebra| |Up|

    Copyright © 1996-2018 Alexander Bogomolny

    71471355