chameleons Before I start: x := y (mod 3) Means  that x = (multiple of 3) + y Here are 2 examples to make the notation clear: 10 := 1 (mod 3) because 10 = (3 x 3) + 1 -4 := 2  (mod 3) because -4 = (3 x -2) + 2 Now, let B and R denote the number of blue and red chameleons respectively. I will now show that B - R := 1 (mod 3) is always true. (i)  Before the first change occurs we have B - R = 17 - 13 = 4 := 1 (mod 3) (ii) Now, suppose it is true after a certain number of changes, then at the next change we have 3 possibilities: One red and one blue chameleon combine to form 2 green ones. In which case new B - new R = (B - 1) - (R - 1) = B - R := 1 (mod 3) One red and one green chameleon combine to form 2 blue ones. In which case new B - new R = (B + 2) - (R - 1) = (B - R) + 3 := b - r := 1 (mod 3) One blue and one green chameleon combine to form 2 red ones. In which case new B - new R = (B - 1) - (R + 2) = (B - R) - 3 := b - r := 1 (mod 3) By (i) and (ii) we have established that B - R := 1 (mod 3) is always true. Now, I will show that if all the chameleons become the same colour then B - R := 0 (mod 3) I've listed the three possibilites below with the appropriate calculations for B - R. R    G    B 45  0    0    B - R = -45 = 3 X (-15) := 0 (mod 3) 0    45  0      B - R = 0 := 0 (mod 3) 0    0  45    B - R = 45 = 3 x 15 := 0 (mod 3) To summarise, all the chameleons cannot become the same colour because in that case we would have: B - R := 0 (mod 3) Whereas, we have proved that B - R := 1 (mod 3) is always true. Sajid Umerji Thursday, December 30, 2004 >>x := y (mod 3) >> >>Means  that >> >>x = (multiple of 3) + y That mod notation really bothers me.  It detracts the formality and elegance of the proof. What if I say 10 := 4 (mod 3) because 10 = (3 x 2) + 4 or -4 := -1  (mod 3) because -4 = (3 x -1) + -1 What we have shown is that even though B - R := 1 (mod 3) is always true, that does not mean it cannot be something else. B - R := 4 (mod 3) could also be true. The proof relies on the assumption that B - R := 1 (mod 3) is always true implies nothing else can be true, therefore B - R := 0 (mod 3) can never be true. However, that assumption is false, although the result of the proof is true. JHY Thursday, December 30, 2004 It's true that B - R := 4 (mod 3) However, if x := y (mod 3) Then y can be ultimately reduced to one and only one of the numbers from the set {0, 1, 2 } Sajid Umerji Friday, December 31, 2004 It's a little more complicated than that: B - R can equal 1 or 2 % 3, and you have to show that in either case it can never end up at 0 % 3, but otherwise your solution works. Erik Monday, January 3, 2005 Another solution: after each color change, the difference between the population of different colors can either remain the same or change by 3. Since the inital difference between populations is initially 2 and 4, it is not possible to reach a difference of 0 following any sequence of color changes (which at most changes the difference by 3). This even proves that two different colors can never have the same population (i.e. difference=0), be it zero or more. Radu Tuesday, January 4, 2005 Since we seem to like Red and Blue... R +2 G -1 B -1 (net change to R-B = 3 .. call this delta1) R -1 G +2 B -1 (net change to R-B = 0 .. delta2) R -1 G -1 G +2 (net change to R-B = -3 .. delta3) We know that the initial value of R-B = 4 It should be obvious that Adding 3, 0, or -3 to 4 will never yield 45 (13+15+17). after some number of meetings (x+y+z) new R-B = original R-B + x(delta1) + y(delta2) + z(delta3) new R-B = 4 + 3x + 0y - 3z new R-B = 1 + 3(1 + x - z) 45 = 3k where k = 15 0 = 3k where k = 0 R-B = 3k + 1 3k + 1 is never equal to 3k thus R-B can be neither 45 nor 0, and the cameleons will never be the all same color. Will Smith Thursday, January 6, 2005 I agree with Will because it's what I proved in my original post but none of the subsequent posters seemed to agree with me. Sajid Umerji Friday, January 7, 2005 A non algabraic solution just occured to me. Since there are 13 red chameleons, 15 green, and 17 red. Since there are not the same number of chameleons of any color, so it is impossible for all the chameleons to become the same color, since this would require all red (for example) to combine with green so that all the chameleons would be blue. After all this, there would still be left 2 green chameleons left which wouldn't be able to become blue without other red chameleons. One of them could combine with a blue chameleon to become 2 reds, and then one red could combine with a green, leaving only 1 red left over, and so nothing more could happen, except changing of the color of chameleon left over. Gregory Johnson Tuesday, January 11, 2005 Suppose there are 12 red, 15 green, and 17 blue. Then a green and a blue can meet leaving us with 14 red, 14 green and 16 blue. You don't have to start with two colors with the same count to end up with valid set. In the case of 13, 15 and 17, there can never be two colors with the same count.  The net change (in the difference between two colors) is always 0 or 3. if 12R, 15G, 17B then R-G= -3, R-B= -5, G-B= -2 now let G & B meet then 14R, 14G, 16B gives R-G= 0, R-B= -2, G-B= -2 notice the change in R-G = 3, R-B = 3, G-B = 0 Cheers Will Smith Thursday, January 13, 2005 hi red - 3x+1 blue - 3y+2 green - 3z it is something of that form itself  right however if we subtract 1 from any 2 of them and add 2 the other the no shall always remain in the same format. to have all of the same color we should first have 2 of the same. agree with sajit think Thursday, January 27, 2005 Sajid's original solution is perfect. He does make an unstated (but true) assumption that if x - y = 0 mod 3 then x - y = 1 mod 3 is false x - y = 2 mod 3 is false. It was pointed out that if x - y = 1 mod 3 then it is also true that x - y = 4 mod 3 is true, this seemingly contradicts his assumption. It is, however, an elementary result of algebra that when operating in the mod 3 system, every number is congruent to exactly one of: 0, 1, 2. If you want to end with a particular color, you need the other two colors to start out congruent mod 3. WanFactory Monday, March 21, 2005   Fog Creek Home