Interview Question

Interview(Student Candidate) New York, NY

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?
Answer

Interview Answer

5 Answers

5

No. Set of amounts mod 3 is always {0, 1, 2}

Interview Candidate on Nov 3, 2011
0

I'm stating a particular case where this is possible let us assume if 9 green combines with 9 red to form 9 more blues.. then now 3 green and 1 red are left. if 1 green combines with 1 more blue then 1 red will be generated and now the number of red and green are equal which is 2 So just combine these 2 and get all blues

Tanuj on Sep 11, 2013
1

I think you misunderstood Tanuj. 9 Green will combine with 9 Red to form 18 Blues. And 1 Green will combine with 1 Blue to make 2 Reds (not 1).

Billy on Sep 18, 2013
2

The interview candidate's answer is horribly unclear. I don't understand how "No. Set of amounts mod 3 is always {0, 1, 2}" answers this question at all. Here's a cleaner solution: Suppose that we start off with (a, b, c). A transition could be (a', b', c') = (a - 1, b - 1, c + 2). Now, note that each time we take a transition, we see that b' - a' = b - a mod 3 c' - b' = c - b mod 3 a' - c' = a - c mod 3 This is an invariant in the problem! Specifically, this means that in our case, b' - a' = c' - b' = 1 mod 3 and a' - c' = 2 mod 3, always. Now, we want to get to the state (0, 0, 33). This isn't possible, since b' - a' = 0 mod 3 (this violates our invariant). So, this isn't possible.

Anonymous on Sep 13, 2014
0

I just think the problem this way and I am not sure if it makes sense. Since each time we can only convert any two chameleons into the third color, so definitely the final case cannot be all red or all green, since 11 blue ones cannot be paired with others, that means it finally reaches the state (0, 1, 32). So the only possible case is all blue finally. But as the # of red and green ones are imbalanced, so it only to arrive at the state (0, 2, 30), which cannot reach (0,0,33) neither.

Peng on Feb 14, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.