Interview Puzzles :: Discussion
-
Chameleons go on a date
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?
Explanation :
No Best Answer on this question yet!Asked In : Amazon
There are 3 possibilities for color-changing. A blue can meet a red, a blue can meet a green, and a red can meet a green. In each case, two of the color types decrease by 1, and the third color type increases by 2. The three possibilities can be represented by:
(blue – 1) + (red – 1) + (green + 2) = 45
(blue – 1) + (red + 2) + (green – 1) = 45
(blue + 2) + (red – 1) + (green – 1) = 45
The decrease in number for the colors that meet is exactly offset by the increase in number for the other color.
Returning to the original problem, after some experimentation, it is evident that the chameleons will not be able to “pair†up correctly so they can all become one color. We need a way to prove this.
To solve the problem, let us find an invariant that considers the pairing of red and blue chameleons. We will consider the simple difference between red and blue chameleons:
red – blue
How does this change as the chameleons mingle?
There are 3 possibilities for color-changing. A blue can meet a red, a blue can meet a green, and a red can meet a green. Let us calculate what happens to the quantity red – blue for those possibilities in order:
(red – 1) – (blue – 1) = red – blue
(red + 2) – (blue – 1) = red – blue + 3
(red – 1) – (blue + 2) = red – blue – 3
We have shown the difference can either be the same, or it can go up or down by 3. This makes sense: when a blue and a red meet, the number of each drops by 1 so the difference stays the same. In the other cases, one color drops by 1 and the other color increases by 2, for a net difference of plus or minus 3.
This is the key insight: the difference between red and blue is always the same as the start, plus or minus a multiple of 3.
In our problem we start with 13 blue and 15 red, so:
red – blue = 2
Regardless of how the chameleons meet, this difference will always be 2 plus a multiple of 3. So we have:
red – blue = 2 + 3k, for some integer k
Is it possible the chameleons will ever be the same color? There are 3 ways this could happen:
(45 blue, 0 red, 0 green), so red – blue = -45 = 3(-15)
(0 blue, 45 red, 0 green), so red – blue = 45 = 3(15)
(0 blue, 0 red, 45 green), so red – blue = 0 = 3(0)
If the chameleons all became the same color, then the difference red – blue would be a multiple of 3.
But this is not possible in the exhibit! Why? We showed the difference red – blue will never be a multiple of 3–it will always be 2 more than a multiple of 3.
Therefore it is not possible for the 13 blue, 15 red, and 17 green chameleons to ever all become the same color.
Let <p, y, m> denote a population of p purple, y yellow and m maroon chameleons. Can population <13, 15, 17> be transformed into <45, 0, 0> or <0, 45, 0> or <0, 0, 45> through a series of pairwise meetings?
We can define the 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.