Fog Creek Software
Discussion Board




chameleons

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

correct me if i am wrong ...

suppose we produce 15 reds by combining all of green and 15 of blue, 2 of the blue remains, giving 2 blue 28 red.

if we combine red and green, we get 30 blue and 2 green.. and so on.

everytime, at least 2 of a different color remain... so, its not possible.

victim
Friday, September 12, 2003

Simpler answer.  There are 45 chameleons.  Since they always change colors in pairs there will always be at least one chameleon which doesn't match the rest.

Idris
Monday, September 29, 2003

I like the simpler answer but it doesn't really work.

Suppose the initial distribution is:

Red: 8
Green: 8
Blue: 29

You've still got 45 chameleons and they still change color in pairs.
This one can lead to all Blue chameleons though.

bile
Thursday, October 02, 2003

I think you have to observe the differences in the sizes of the populations.

If you can create a situation with two colors having the same number of chameleons you "win" (simply having them all meet in pairs of one color each).
It is also absolutely necessary to have such a situation, because the last step must involve the last two of both "other" colors to meet.

Let's look at the given numbers and their respective differences:
    red(13), green(15): +2
    red(13),blue(17): +4
    green(15), blue(17): +2
Now you need to get one of these down to 0. Each meeting causes one color to increase by 2 and two colors to decrease by one. As a result the difference between the two "meeting-colors" stay the same, while the other two differences change by three.
Example (blue meets green):
  red(13+2),green(15-1): -1
  red(13+2),blue(17-1): +1
  green(15-1), blue(17-1): +2

None of the original differences is dividable by 3 (being +2 and +4). That means that no matter how many chameleon-meetings you arrange you will never get a difference down to zero!
Therefore it is impossible to have all chameleons have a single color.

Stefan Leppert
Friday, October 03, 2003

I have done it in 15 steps, leaving 0 Red, 0 Green, and 30 Blue.

Start by creating as many Blues as possible till you get down to:

Red:    1
Green:  3
Blue:    29

Now you can combine a Green and a Blue to leave:

Red:    2
Green:  2
Blue:    28

Follow through with:

Red:    1
Green:  1
Blue:    29

And finally:

Red:    0
Green:  0
Blue:    30



Am I missing something here? Perhaps, but I don't think so.

Paul Jensen
Tuesday, October 14, 2003

Yep you are missing something 1+2 = 3!

1
3
29

yields

3
2
28

matt m
Friday, October 17, 2003

You are missing 15 chameleons!!!

markp
Friday, October 17, 2003

Yes Paul.... U are missing one thing.
Combining 1 red and 1 green Chameleon yields 2 blue Chameleons.
So In your first step, the data should be like :
Red    : 1
Green : 3
Blue  : 41 <<-------- Not 29

Amit Kumar
Saturday, October 18, 2003

The missing blue chameleons are irrelevant.  The important part is what matt m points out:  combining a green and a blue increases the count of red chameleons by 2, not by 1.

neal
Tuesday, October 28, 2003

>"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?"
>
>
The relation between the numbers of each colors mod 3 can not be changed: when two chameleons of two different colors meet, each of these two colors loses 1 (the relation does not change) and the third color gains 2 (the difference with the other two colors increases by 3, hence does not change). As our goal is n-0-0 (all become of the same color) the relation between some two mod 3 must be 0. So:

1) The answer is NO.

2) Should we have 13 red chameleons, 15 green chameleons, 18 blue chameleons we could end up with 46 red ones. Should we have 14 red chameleons, 15 green chameleons, 17 blue chameleons we could end up with 46 green ones.

3) Should we have 10 red chameleons, 16 green chameleons, 19 blue chameleons we could end up with 45 ones of any color we'd like.

Is that right?

vadim khaldey
Wednesday, November 19, 2003

*  Recent Topics

*  Fog Creek Home