I am trying to understand the solution to the below puzzle
There are 13 Red, 15 Green, and 17 Blue Chameleons at some point of
time. Whenever two Chameleons of the different colors meet both of
them change their color to the third color. Is it ever possible for
all Chameleons to become of the same color?
I am able to figure out "manually step by step" that it is not possible to get all in one color.
However I don't understand the more formal solution using the modulo, for example Solution 1 here.
I realize that after every change the differennce between the second and first terms is -3, 0 or 3.
What are the vectors (2,2,2) representing?
I don't understand the final statement there:
We see that, with the initial vector (1, 0, 2) modulo 3, the only possible combinations of colors on the island are (1, 0, 2), (0, 2, 1), and (2, 1, 0), and these occur cyclically with period 3.
Can anybody explain in simple way this solution to the problem?
Best Answer
The trick is to show that:
$$(17,15,13)+a(-1,-1,2)+b(-1,2,-1)+c(2,-1,-1)$$ is never $(45,0,0), (0,45,0),$ or $(0,0,45)$ for $a,b,c$ integers.
But since $(2,-1,-1)=(-1)(-1,2,-1)+(-1)(2,-1,-1)$, you can eliminate the third term and ask to find $a,b,$ so that we only need to show that:
$$(17,15,13)+a(-1,-1,2)+b(-1,2,-1)$$
can never be $(45,0,0), (0,45,0),$ or $(0,0,45)$ when $a,b$ are integers.
If we have such $a,b$, then $a+b\equiv 17\pmod {45}, 2b-a\equiv -15\pmod{45}$ and thus $3b\equiv 2\pmod{45}$, which is impossible.
Another way to state this is:
So if $(x',y',z')=(45,0,0),(0,45,0)$ or $(0.0,45)$ then $x-y\equiv 0\pmod 3$. But $17-15\equiv 2\pmod 3$.
This also means you can't get to $(15,15,15)$ since again it would mean $x-y\equiv 0\pmod 3$.