chamaleons puzzle answer
the answer is that its NOT possible for all chameleons
to be of same color. Logic is:
lets assume for a minute that its is possible. that means
at some point down the line there must be exact same
number(say X) of chamaleons of two different colors and
all others (say Y) must be of third color.
it gives us 2*X + Y = 45 (odd number)
implies that Y = odd number.
one can observe that since all the three colored chameleons
are odd number to start out with, #of chams in a specific color
can change to even only if some chams leave the group, otherwise
it grows by even number keeping the total odd.
which implies that if any one color has odd numer population,
population of other two colors must have changed by same # of chams.
since the initial population of any color differs by 2, its
impossible that any two color's population would change by same
amount and end up being exactly same!
so I think its impossible that all chameleons will be of same color
Tuesday, June 3, 2003
Sure it's possible
green meets blue:
14 red and 14 green
reds keep meeting green
Wednesday, June 4, 2003
nope! when green meets blue, now there are 15 reds!
Wednesday, June 4, 2003
Actually it is impossible since there is a difference of 2 (13-15, 15-17) and any movement has to be in multiples of 3 (-1 for 2 of them +2 for the other)
Thursday, June 5, 2003
Simple solution is the following. Let's consider remainders of division by 3. In the beginnig we have 13 = 3*4 +1, 15 = 3*5, 17 = 3*5 +2. We can see that they are all diferent. Now the idea is that always they will be different. Prove can be done by induction
Sunday, June 8, 2003
In this case it is NOT possible but if the following condition holds it is possible:
y-z=3p and p < x+2*z
each of x y and z stand for the quantity of any of the colors
5 blue, 8 red, 10 green
z=5, y=8, x=10
combine 5b and 8r to get 10g
now we have 20g and 3r
combine 1r with 1g to get 2b
now we have 19g 2b and 2r
Thursday, June 19, 2003
Let R,G and B be the number of chameleons of different colors. We want that in the end R=G=0.
When 2 chameleons meet, the possible transitions are:
R G B
+2 -1 -1
-1 +2 -1
-1 -1 +2
If we look at the R and G columns, we see that they can both go down together or the difference between them will change by 3.
R - G = 3*k where k integer
Proof by induction (k)
1) k = 0 R = G then they can decrease together
2) k => k+1
Consider that it works if R-G = 3*k.
Now we get R = G + 3*(k+1) = G + 3*k +3
Let 1 B meet one R
Initial : R = G+3*k+3 G B
R = G + 3*k +2 G+2 B-1
Now R and G can decrease together twice and we end up with:
Final: R = G+3*k G B+3
Which is the induction assumption.
Note: B>0 is another necessary condition
If we want to get all chameleons Blue, we need either :
a) R=G or
b) R-G = 3*k and B>0
Monday, June 23, 2003
Simple answer -- a) the blue chameleons kill four of their own and eat the remains, b) the green chameleons kill two of their own and eat the remains, and c) the conditions are satisfied for all three groups of chameleons to potentially be of the same color.
Wednesday, June 25, 2003
Fog Creek Home