techInterview Discussion

Answers to technical interview questions. A part of

A part of 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
Ohmigod! You killed one! SPCA will get you for this...
Tapori Send private email
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.

Arun Patnaik Send private email
Tuesday, November 08, 2005
your conclusion is correct but your reasoning is wrong.

if you do a difference of 3 twice, you get a difference of 6 which is even.

you need to look at the differences mod3 not mod2
WanFactory Send private email
Thursday, November 10, 2005
May be I am missing something or I didn't state my reasoning

The effective difference after any number of changes
will be 2 (initial diffference) +/- 3 * n .
This can never be zero.

- Arun
Arun Patnaik Send private email
Friday, November 11, 2005
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.
WanFactory Send private email
Friday, November 18, 2005
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.
Weiting Send private email
Thursday, December 29, 2005
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..
hence poosible
anubhav jain
Friday, December 30, 2005
you killed one...
Weiting Send private email
Friday, December 30, 2005

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
Powered by FogBugz