Kvant Math Problem 914

Let $(g,b,c)$ denote the numbers of gray, brown, and crimson chameleons.

kvantmathematicsolympiad

Verified: yes
Verdicts: PASS + PASS
Solve time: 12m15s
Source on kvant.digital

Problem

On the island of Seroburimalin, there live 13 gray, 15 brown, and 17 crimson chameleons. If two chameleons of different colors meet, they simultaneously change their color to the third one (gray and brown both become crimson, and so on). Is it possible that, after some time, all the chameleons will be of the same color?

V. G. Ilyichyov

Exploration

Let $(g,b,c)$ denote the numbers of gray, brown, and crimson chameleons.

When a gray and a brown chameleon meet, both become crimson. Thus

$$(g,b,c)\mapsto(g-1,b-1,c+2).$$

Similarly,

$$(g,b,c)\mapsto(g-1,b+2,c-1)$$

for a gray-crimson meeting, and

$$(g,b,c)\mapsto(g+2,b-1,c-1)$$

for a brown-crimson meeting.

The total number of chameleons is fixed:

$$13+15+17=45.$$

To reach a monochromatic state, the final configuration would have to be one of

$$(45,0,0),\qquad (0,45,0),\qquad (0,0,45).$$

A useful experiment is to examine the numbers modulo $3$. For the first move,

$$(g,b,c)\mapsto(g-1,b-1,c+2).$$

The changes are

$$-1,,-1,,+2.$$

Since $2\equiv -1\pmod 3$, all three coordinates change by the same residue class modulo $3$. Hence the differences $g-b$, $b-c$, and $c-g$ modulo $3$ may remain invariant.

For the initial state,

$$(13,15,17)\equiv(1,0,2)\pmod 3.$$

The three monochromatic states satisfy

$$(45,0,0)\equiv(0,0,0),\qquad (0,45,0)\equiv(0,0,0),\qquad (0,0,45)\equiv(0,0,0)\pmod 3.$$

These residue patterns differ from $(1,0,2)$, suggesting impossibility.

The step most likely to conceal an error is the invariance claim. It must be checked for all three kinds of meetings.

Problem Understanding

We are given $13$ gray, $15$ brown, and $17$ crimson chameleons. Whenever two chameleons of different colors meet, both change into the third color. The question is whether a sequence of such meetings can lead to a state in which all $45$ chameleons have the same color.

This is a Type D problem, an existence problem. We must determine whether such a monochromatic state can exist.

The core difficulty is to find a quantity that remains unchanged under every allowed move and then compare its value in the initial configuration with its value in every monochromatic configuration.

The answer is that a monochromatic state cannot be reached. The intuitive reason is that the numbers of chameleons in the three colors possess a congruence invariant modulo $3$ that disagrees with every monochromatic state.

Proof Architecture

The first lemma is that the residues of $g-b$, $b-c$, and $c-g$ modulo $3$ are invariant under every allowed meeting. This follows because each move changes all three color counts by numbers congruent to $-1$ modulo $3$.

The second lemma is that the initial configuration satisfies

$$(g,b,c)\equiv(1,0,2)\pmod 3.$$

The third lemma is that every monochromatic configuration of $45$ chameleons satisfies

$$(g,b,c)\equiv(0,0,0)\pmod 3.$$

The final step is to show that the invariant residues from the initial state are incompatible with the residues of any monochromatic state.

The hardest point is proving the invariant rigorously for all three types of meetings.

Solution

Let $(g,b,c)$ denote the numbers of gray, brown, and crimson chameleons.

Consider the quantities

$$g-b,\qquad b-c,\qquad c-g$$

modulo $3$.

We show that their residue classes modulo $3$ do not change under any allowed meeting.

Suppose first that a gray and a brown chameleon meet. Then

$$(g,b,c)\mapsto(g-1,b-1,c+2).$$

The new differences are

$$(g-1)-(b-1)=g-b,$$

$$(b-1)-(c+2)=(b-c)-3,$$

$$(c+2)-(g-1)=(c-g)+3.$$

Hence each of the three differences has the same residue modulo $3$ as before.

Suppose next that a gray and a crimson chameleon meet. Then

$$(g,b,c)\mapsto(g-1,b+2,c-1).$$

The new differences are

$$(g-1)-(b+2)=(g-b)-3,$$

$$(b+2)-(c-1)=(b-c)+3,$$

$$(c-1)-(g-1)=c-g.$$

Again, all three residues modulo $3$ are unchanged.

Finally, suppose that a brown and a crimson chameleon meet. Then

$$(g,b,c)\mapsto(g+2,b-1,c-1).$$

The new differences are

$$(g+2)-(b-1)=(g-b)+3,$$

$$(b-1)-(c-1)=b-c,$$

$$(c-1)-(g+2)=(c-g)-3.$$

The residues modulo $3$ are unchanged once more.

Therefore the residue classes of

$$g-b,\qquad b-c,\qquad c-g$$

modulo $3$ are invariants of the process.

For the initial configuration,

$$(g,b,c)=(13,15,17).$$

Hence

$$g-b=13-15=-2\equiv1\pmod3,$$

$$b-c=15-17=-2\equiv1\pmod3,$$

$$c-g=17-13=4\equiv1\pmod3.$$

Thus all three invariant differences are congruent to $1$ modulo $3$.

Now examine any monochromatic state.

If all chameleons are gray, then

$$(g,b,c)=(45,0,0),$$

so

$$g-b=45,\qquad b-c=0,\qquad c-g=-45,$$

all of which are congruent to $0$ modulo $3$.

If all chameleons are brown, then

$$(g,b,c)=(0,45,0),$$

and again the three differences are multiples of $3$.

If all chameleons are crimson, then

$$(g,b,c)=(0,0,45),$$

and once more the three differences are multiples of $3$.

Therefore every monochromatic configuration has

$$g-b\equiv b-c\equiv c-g\equiv0\pmod3.$$

The initial configuration has these three residues equal to $1$ modulo $3$, and these residues cannot change during the process. Consequently no monochromatic configuration can be reached.

Hence it is impossible for all $45$ chameleons ever to become the same color.

$$\boxed{\text{No, a monochromatic state cannot be reached.}}$$

Verification of Key Steps

The first delicate step is the invariance. For a gray-brown meeting, the coordinate changes are

$$(-1,-1,+2).$$

The difference $b-c$ changes by

$$(-1)-(+2)=-3,$$

while $c-g$ changes by

$$(+2)-(-1)=3.$$

The appearance of exactly $\pm3$ is what makes the argument work modulo $3$. Replacing $+2$ by an incorrect value would destroy the invariant.

The second delicate step is computing the initial residues. Using

$$13\equiv1,\qquad15\equiv0,\qquad17\equiv2\pmod3,$$

gives

$$g-b\equiv1,\qquad b-c\equiv1,\qquad c-g\equiv1\pmod3.$$

A sign mistake in one difference would incorrectly suggest a different invariant class.

The third delicate step is checking every monochromatic state, not merely one of them. Since

$$45\equiv0\pmod3,$$

all differences in each of

$$(45,0,0),\quad(0,45,0),\quad(0,0,45)$$

are multiples of $3$. The contradiction must hold for all three possible final colors.

Alternative Approaches

Instead of using the differences, one may observe directly that in every allowed move all three coordinates change by numbers congruent to $-1$ modulo $3$:

$$-1\equiv2\pmod3.$$

Consequently the pairwise differences of the coordinates modulo $3$ are preserved. This is the same invariant expressed more compactly.

Another approach is to consider the residue class of the vector $(g,b,c)$ modulo $3$ up to adding the same residue to all three coordinates. Each move adds the vector

$$(-1,-1,-1)$$

modulo $3$, so the equivalence class of $(g,b,c)$ under simultaneous translation remains fixed. The initial class represented by

$$(1,0,2)$$

is different from the class represented by

$$(0,0,0),$$

which contains every monochromatic state. This yields the same impossibility result.