Fog Creek Software
Discussion Board




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
eventually.

Any thoughts?

saurabh
Tuesday, June 03, 2003

Sure it's possible

green meets blue:
14 red and 14 green

reds keep meeting green

Binyomin
Wednesday, June 04, 2003

nope! when green meets blue, now there are 15 reds!

saurabh
Wednesday, June 04, 2003

oops !

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)

Binyomin
Thursday, June 05, 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

Gans
Sunday, June 08, 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

where,

each of x y and z stand for the quantity of any of the colors 

Example:

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

Alex Czarian
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


Conclusion:
If we want to get all chameleons Blue, we need either :
a) R=G or
b) R-G = 3*k and B>0

Tibi Doman
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.

Patrick
Wednesday, June 25, 2003

*  Recent Topics

*  Fog Creek Home