Can the Chameleons Ever Be All One Colour?
On a remote island live 45 chameleons: 13 are red, 15 are green and 17 are blue. Whenever two chameleons of different colours meet, both of them change to the third colour (for example, a red and a green chameleon that meet both turn blue). When two chameleons of the same colour meet, nothing happens. Meetings happen one pair at a time, in any order.
Is it possible for all 45 chameleons to eventually become the same colour? Prove your answer.
Hints
- Write down how one meeting changes the three counts $(r, g, b)$: one colour goes up by 2 and the other two go down by 1 each.
- Look at the differences between counts, such as $r - g$. A meeting changes each pairwise difference by $0$, $+3$ or $-3$. What does that say modulo $3$?
- Initially the three counts are $13, 15, 17$, which are $1, 0, 2$ modulo $3$, all different. An all-one-colour state needs two counts equal to zero, so two counts would be congruent modulo $3$, which can never happen.
Worked Solution
How to Think About It: Reachability questions for a state machine with simple transitions call for an invariant: a function of the state that every transition preserves. If the invariant differs between the start and the target, the target is unreachable. Here the transitions are so symmetric that differences of counts modulo $3$ are the natural candidate.
Quick Estimate: Every meeting changes the counts by $(+2, -1, -1)$ in some order. The difference between any two counts changes by $2 - (-1) = 3$, by $-1 - 2 = -3$, or by $(-1) - (-1) = 0$. So differences modulo $3$ never move, and $13, 15, 17$ have pairwise differences $2, 2, 4$, none of which is a multiple of $3$.
Formal Solution:
*Step 1 -- The transitions.* Let the state be $(r, g, b)$ with $r + g + b = 45$. A meeting of a red and a green chameleon maps $(r, g, b) \to (r - 1, g - 1, b + 2)$; similarly the other two meeting types give $(r - 1, g + 2, b - 1)$ and $(r + 2, g - 1, b - 1)$.
*Step 2 -- The invariant.* Consider the differences $r - g$, $g - b$ and $b - r$ modulo $3$. Under the first transition, $r - g$ is unchanged, $g - b$ decreases by $3$, and $b - r$ increases by $3$. The other transitions likewise change each difference by $0$ or $\pm 3$. Hence $$r - g \pmod 3, \quad g - b \pmod 3, \quad b - r \pmod 3$$ are all invariant under every possible meeting. Equivalently, the residues $(r \bmod 3, g \bmod 3, b \bmod 3)$ are shifted by a common amount ($-1$ or $+2 \equiv -1$) at each step, so whether any two of them coincide never changes.
*Step 3 -- The initial state.* $(13, 15, 17) \equiv (1, 0, 2) \pmod 3$. The three residues are pairwise distinct, so no pairwise difference is $0$ modulo $3$: $r - g \equiv 1$, $g - b \equiv 1$, $b - r \equiv 1 \pmod 3$.
*Step 4 -- The target state.* An all-one-colour state is $(45, 0, 0)$, $(0, 45, 0)$ or $(0, 0, 45)$. In each, two of the counts are equal (both $0$), so at least one pairwise difference is $0 \equiv 0 \pmod 3$.
*Step 5 -- Conclusion.* The invariant takes the value "all pairwise differences nonzero modulo $3$" at the start and would have to take the value "some pairwise difference is $0$ modulo $3$" at the target. Since it never changes, no sequence of meetings reaches a monochromatic state. (A breadth-first search over the 360 reachable states from $(13, 15, 17)$ confirms that none of them is monochromatic.)
*Step 6 -- When it would be possible.* If two colour counts were congruent modulo $3$ (for example $13, 16, 16$), the island could become monochromatic: repeatedly have the two congruent colours meet until they are both zero, adjusting with intermediate meetings as needed. So the modulo-$3$ condition is exactly the obstruction.
Answer: No. Every meeting changes each pairwise difference of colour counts by $0$ or $\pm 3$, so the differences modulo $3$ are invariant. Initially the counts $13, 15, 17$ are $1, 0, 2$ modulo $3$, pairwise distinct, whereas a single-colour island would have two counts equal to $0$. The required state is unreachable.
Intuition
Each meeting moves the count vector by $(+2, -1, -1)$ or a permutation of it, and every such move shifts each pairwise difference of counts by a multiple of $3$. The residues of the pairwise differences modulo $3$ are therefore invariant. Starting from $13, 15, 17$ the three counts are pairwise incongruent modulo $3$, but a monochromatic island has two counts equal to $0$, which are congruent. So the target is unreachable. Finding a conserved quantity that separates the start state from the goal state is the standard way to prove a process cannot reach a configuration, and the same instinct is useful for spotting when a rebalancing rule or state machine can never hit a desired state.