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.
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
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.
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.
1G n 1B chameleon meets....both turn to red...
14R, 14G and 16B cameleons left...
every time now a R n G chameleon meet their colour change to blue...finally all Blue..
Friday, December 30, 2005
This topic is archived. No further replies will be accepted.Other recent topics
Powered by FogBugz