
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 RB = 3 .. call this delta1)
R 1
G +2
B 1 (net change to RB = 0 .. delta2)
R 1
G 1
G +2 (net change to RB = 3 .. delta3)
We know that the initial value of RB = 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 RB = original RB + x(delta1) + y(delta2) + z(delta3)
new RB = 4 + 3x + 0y  3z
new RB = 1 + 3(1 + x  z)
45 = 3k where k = 15
0 = 3k where k = 0
RB = 3k + 1
3k + 1 is never equal to 3k
thus RB 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 RG= 3, RB= 5, GB= 2
now let G & B meet
then 14R, 14G, 16B
gives RG= 0, RB= 2, GB= 2
notice the change in
RG = 3,
RB = 3,
GB = 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
Recent Topics
Fog Creek Home
