Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
There are 10 red, 11 blue, 12 green chameleons. Sometimes, two chameleons meet. If they are the same color, nothing happens. If they are different colors, they will both change to the third color. Can all chameleons ever be the same color?
Doesn't seem like it is possible but not quite sure how to prove it. Seems like it might have something to do with modular arithmetic.
Let $R$, $B$, and $G$ be the number of red, blue, and green chameleons at the moment. After any meeting of chameleons, we have one of $$R\mapsto R,\quad B\mapsto B,\quad G\mapsto G$$
$$R\mapsto R-1,\quad B\mapsto B-1,\quad G\mapsto G+2$$ $$R\mapsto R+2,\quad B\mapsto B-1,\quad G\mapsto G-1$$ $$R\mapsto R-1,\quad B\mapsto B+2,\quad G\mapsto G-1$$ Note that $B-G\pmod 3$, $R-B\pmod 3$, and $G-R\pmod 3$ are preserved under any meeting. Supposing (WLOG) that all chameleons at some point became green, then both $R$ and $B$ would be $0$, and thus $R-B\equiv 0\pmod 3$. But having started with $R-B\equiv 2\pmod 3$, this is impossible. Thus, the chameleons can never all be the same color.
Let the numbers of red, blue, and green chameleons mod $3$ be $\langle r,b,g\rangle$. When two of different colors meet, the resulting numbers after the color changes are $\langle r-1,b-1,g+2\rangle$, $\langle r-1,b+2,g-1\rangle$, or $\langle r+2,b-1,g-1\rangle$. Each of these is the same mod $3$ as a change to $\langle r-1,b-1,g-1\rangle$. Since the initial numbers are $\langle 1,2,0\rangle$, all of which are distinct, and they will always be distinct. In fact, they cycle through the permutations $\langle 1,2,0\rangle$, $\langle 0,1,2\rangle$, and $\langle 2,0,1\rangle$.
Here is a more mechanical, far less elegant strategy, which ended up being the same as above. I realize that one is looking for invariants, but always have a hard time spotting them. The following technique may provide some solution structure who share my difficulty...
Let $A = \begin{bmatrix} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2\end{bmatrix}$. I look for 'neat' eigenvalue/left eigenvector pairs, and find $v^T=(1,-1,0)$ corresponding to eigenvalue $3$. The 'system' we have is $x_{x+1} = x_n + u_n$, where at each $n$, $u_n$ is one of the three columns of $A$, and $x_n = (r_n, g_n, b_n)^T$ represents the number of each color at time $n$. The solution is $x_n = x_0+u_0+...+u_{n-1}$.
Now I look at $v^T x_n$, and notice that $v^T x_n \pmod 3 = v^T x_0 \pmod 3 = 1$. However, $v^T (33,0,0) = 0 \pmod 3$, and similarly for the other extreme distributions. Hence we can never reach these states.
