There are 13 red chameleons, 15 green chameleons, and 17 blue chameleons. When two chameleons of different colors meet, they both change to the third color. Can all chameleons ever become the same color?
Try any sequence of meetings. Watch what happens to the counts and the invariant.
The key idea is to look at the counts modulo 3.
In a legal meeting, one count decreases by 1, another decreases by 1, and the third increases by 2.
Since +2 ≡ -1 (mod 3),
all three counts are shifted by the same amount modulo 3. Therefore, the differences between residues stay unchanged.
| Invariant | Value |
|---|---|
| R - G (mod 3) | 1 |
| G - B (mod 3) | 1 |
| R - B (mod 3) | 2 |
No — it is impossible.
Initially, the state is (13, 15, 17) ≡ (1, 0, 2) mod 3.
Any all-one-color state would be one of:
Each of these is congruent to (0, 0, 0) mod 3, which does not have the same invariant differences as the initial state. Since legal moves preserve those differences, such a state can never be reached.