The Old techInterview Forum - Changing chameleons

Changing chameleons

http://www.flooble.com/perplexus/show.php?pid=16

(And no looking at the solution!)

levik
Monday, April 22, 2002

I didn't see a solution, so I left one there. :-)

Paul Brinkley
Monday, April 22, 2002

(That is, other than the "See the Solution" link, which I avoided until I had posted, of course. D'oh.)

Paul Brinkley
Monday, April 22, 2002

It is not possible

Reason - If the chameleons ever get into a state where each population differs from the others by mod 3, it must always have been in that state. The goal state is like that (45 of one colour), but the start state isn't (13,15,17). Therefore we can't get to the goal state from our start

Proof
Assume populations differ by mod 3 this generation
Look at previous generation - difference between any two colour populations - either we both lost one (merging to the 3rd colour), so the difference is still mod 3, or one color lost one and the other gained 2, a difference of 3, so the difference is still mod 3

jim dallas
Friday, April 26, 2002

It is possible once any one of the chameleons dies.

Michael Terry
Sunday, April 28, 2002

I have taken a different approach. To show that it is possable I only have to come up with one example where all become the same colour, so

If 13 green meet 13 red that we have
0 green
2 red
30 blue

if 1 red then meets 1 blue then we have
1 green
1 red
30 blue

if the 1 green meets 1 red
we end up with
32 blue.

or am I missing something?

Dreyno
Sunday, April 28, 2002

Yes, you are missing something. After 13 red meet 13 green, you would have

0 red
2 green
17+13+13=43 blue.

You start with 45 chameleons. You must end with 45. Remember, BOTH chameleons at the meeting will change color.

My solution was a bit different. I thought of a way to get 44 of one color. Since I only have one left, I know I can't get them all one color. (This basically is a case of the mod 3 argument above, which is better than mine.)

gila monster
Sunday, April 28, 2002

Not possible, my arguments took a slightly different route before I checked this discussion.

We all realize that if the number of any 2 colors is the same then we can convert all chameleons into the third color.

Let R, G, B, be the number of Red, Green and Blue chameleons and let x be the number of times blue and green converted to reds, y be the number of times red and blue converted to greens, and z be the number of times red and green convert to blues.

So,

R = 13 + 2x - y - z
G = 15 + 2y - x - z
B = 17 + 2z - x - y

If we set R = G, then x - y = 2/3, but this is not possible since chameleons only come in the integer persuasion.

Making similar arguments for R = B and G = B, we conclude there will always be a rainbow of chameleons.

(I wonder if you can trick them with model chameleons?)

Andrew Shafer
Friday, May 24, 2002

Assign the colors values, Red to 0 Green to 1 and Blue to 2.
The sum of the color values mod 3 of all the chameleons never changes in any switch. This sum mod three would be zero in any state where the 45 chameleons are the same but in the initial state it is 1. Thus it is impossible.

Jonathan
Friday, May 31, 2002