Difficult problem

Problem 1 of Tournament of Towns 1984

On the island of Camelot live 13 gray, 15 brown and 17 crimson chameleons. If two chameleons of different colors meet they both simultaneously change color to the third color (e.g. if a gray and a brown chameleon meet each other they both change to crimson). Is it possible that they will eventually all be the same color?

Solution

Let the three groups of chameleons right before the two groups with the same number of chameleons meet the last time to transform them into the same color (if such a condition is possible) be m, n and n. We have m + 2n = 13 + 15 + 17 = 45. To easily describe the solution let’s write a chart as follow:

Quantity in group A, B and C           Step                   __________

A             B                    C

               m+2n                                      1. Final state

n             m                   n                        2. Only possible step before final meeting

n+p        m+p             n–2p                3. Only possible next to last  step above (p is an integer)

n+p+q    m+p–2q   n–2p+q           4. Possible step before step 3 (q  is an integer)

n+p+q    m+p+q     n–2p–2q         5. Another possible step before step 3.

n+p–2p  m+p+q     n–2p+q           6. Another possible step before step 3.

…

Note that the differences between the two chameleon groups A and C are always multiples of 3 (in step 3, A – C = 3p, in step 4, A – C = 3p, in step 5, A – C = 3(p+q) and in step 6, A – C = 3(p – q)), and this pattern continues. But the differences between the chameleons in the problems are 2 and 4. Therefore, it is not possible that they will eventually all be the same color.