# Sea of Noise

## Mon, 30 Apr 2007

meta-creation_date:04/05/2007
For those with time left over after turning their old toasters into robots, the awesome magazone Make also has a puzzle section. I particularly enjoyed this one from issue #9:

At one point, a tropical 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. For example, if green meets red, they both change their color to blue. Is it ever possible for all the chameleons to become the same color?

There's an answer posted on the Make web site, but (**spoiler alert!**) I took a different, inductive approach that appeals to me a bit more:

Consider an island population of n chameleons at time t of P_{t} = (R_{t}, G_{t}, B_{t}), where R_{t}, G_{t}, and B_{t} are the number of red, green, and blue chameleons at time t, respectively. We show by induction that if the population consists of n red chameleons, then the population must have always contained an equal number of blue and green chameleons.

Let k = 0 and suppose that at time t = t -k , R_{t-k} = n = n-2k. Then G_{t-k} = B_{t-k} = 0 = 2k. That is, P_{t-k} = (n,0,0) = (n-2k,k,k).

For k>=0, if P_{t-k} = (n-2k,k,k), then by the statement of the problem P_{t-(k+1)} = (n-2(k+1),k+1,k+1). That is, if we have n-2k red chameleons, it must be the case that immediately before we had n-2(k+1) red chameleons and then one green chameleon met one blue chameleon and the two of them changed color to blue, reducing the number of green and blue chameleons from k+1 each to k each.

So, to end up with a population of all red chameleons, we must have started with a population containing an equal number of green and blue chameleons; which we didn't, so we can never end up with all red chameleons.

The argument for why we can't end up with all green or all blue chameleons proceeds the same way.

*[/science]
permanent link*

Syndicate Me via RSS!

(Instructions)

Copyright 2003-2009 Robert Szarka

Powered by Blosxom!