Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
6  
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
add comment

3 Answers

up vote 16 down vote accepted

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.

share|improve this answer
1  
+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
add comment

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$.

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.