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 3, 2003 Sure it's possible green meets blue: 14 red and 14 green reds keep meeting green Binyomin Wednesday, June 4, 2003 nope! when green meets blue, now there are 15 reds! saurabh Wednesday, June 4, 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 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 Gans 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 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   Fog Creek Home