Fog Creek Software
Discussion Board




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 03, 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 04, 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 06, 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 07, 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

*  Recent Topics

*  Fog Creek Home