This work is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.
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 Pt = (Rt, Gt, Bt), where Rt, Gt, and Bt 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 , Rt-k = n = n-2k. Then Gt-k = Bt-k = 0 = 2k. That is, Pt-k = (n,0,0) = (n-2k,k,k).
For k>=0, if Pt-k = (n-2k,k,k), then by the statement of the problem Pt-(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.
Syndicate Me via RSS!
(Instructions)
Copyright 2003-2009 Robert Szarka
Powered by Blosxom!