## techInterview Discussion |
||

A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor |
"at one point, a remote island's population of chameleons was divided as follows:
* 13 red chameleons * 15 green chameleons * 17 blue chameleons each time two different colored chameleons would meet, they would change their color to the third one. (i.e.. If green meets red, they both change their color to blue.) is it ever possible for all chameleons to become the same color? why or why not?" ===== Simple. "Yes" Blue meets Red. Now 12 R, 16 G, 16 B G meets B 16 times, turning red. All red.
anon Tuesday, November 01, 2005
After 1 B met 1 R, the result should be 12 R, 17 G, 16 B
Both B and R turn into G, so you need to add 2 to G The total number does not change
j Thursday, November 03, 2005
The initial difference(in count) between the 3 colours is even i.e. 2 or 4.
Every colour change results in the reduction of the count of 2 colours by 1 and increase of 1 colour by 2 so effective change in differences will be 0 or 3 (odd) so there is no way the differences between any 2 colour strengths can ever be 0. so we can never get to a stage where 2 colours have the same count to be able to completely turn into the 3rd colour. Thanks Arun
I got distracted by your argument that the difference of two disqualifies an eventual equality because two is even.
I agree that two can never become zero but it has nothing to do with being even and everything to do with not being divisible by three. For example, if the initial difference were 6, you could make it equal even though 6 is even.
suppose we have a,b,c (numbers of chamelions).
let f(a,b,c) = |a-b| + |b-c| + |c-a|. Then for each operation, the f() value changes by 0,3,6; anyway the changes is 3k. So if finally all have the same color, then f() = 2(a+b+c). In the case a=13, b=15, c=17, f()=8; Finally we need f()=2(13+15+17)=90. This implies 8+3k = 90. This is impossible. |

Powered by FogBugz