Chameleons
20 Sep 2008
Puzzle

On an island live 13 purple, 15 yellow and 17 maroon chameleons. When two chameleons of different colors meet, they both change into the third color. Is there a sequence of pairwise meetings after which all chameleons have the same color?

Source

A problem from Tournament of Towns, 1984.

Solution

Let <p, y, m> denote a population of p purple, y yellow and m maroon chameleons. Can population <13, 15, 17> can be transformed into <45, 0, 0> or <0, 45, 0> or <0, 0, 45> through a series of pairwise meetings? Define function X(p, y, m) = (0p + 1y + 2m) mod 3. An interesting property of X is that its value does not change after any pairwise meeting because X(p, y, m) = X(p-1, y-1, m+2) = X(p-1, y+2, m-1) = X(p+2, y-1, m-1). Now X(13, 15, 17) equals 1. However, X(45, 0, 0) = X(0, 45, 0) = X(0, 0, 45) = 0. This means that there is no sequence of pairwise meetings after which all chameleons will have identical color.

© Copyright 2008—2018, Gurmeet Manku.