# Chameleons Riddle

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.

-
A general strategy for problems like this is to write down some invariant of the configuration of colors that doesn't change when two chameleons meet. If your invariant is different for the initial setup as opposed to the setup where all of the chameleons are the same color, then you're done. –  Qiaochu Yuan May 16 '12 at 3:01

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.

-
+1. Your presentation of the solution is way more elegant than what I was writing. –  user17762 May 16 '12 at 3:09
Thank you for your kind words, Marvis. –  Zev Chonoles May 16 '12 at 3:24

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.

-
Does this strategy only work when the number of variables and the number of possible actions is equal? Or, what would you do if, unluckily, your matrix was rectangular? –  Rahul May 16 '12 at 4:26
Well, it is still a very ad-hoc approach. And yes, most likely to work only in the 'square' case. The issue is finding suitable equivalence classes of states, with the equivalence relation unaffected by inputs. –  copper.hat May 16 '12 at 4:41