Can Anyone Work This Out?!?!

[Maths_Idiot]

I came accross this problem in an old maths textbook of my fathers and its really annoying me because i cant seem to work it out
can anyone do it?:

A particular species of chameleon comes in three colours: red, blue and green. Whenever two chameleons of different colours meet they change colour, both changing to the third colour. Thus if a red chameleon meets a blue chameleon they both change to green. When two chameleons of the same colour meet, neither change colour. If there are originally 13 red chameleons, 14 blue chameleons and 15 green chameleons is it possible for all the chameleons to become the same colour? Generalise.

Good Luck!

[Spooner]

Aaaaaaaaaarrrrrrrrrrrrrrghhhhhhhhhhh.. that stuff makes my brain hurt. But it's probably dead simple if you do as they say and generalise, because if you try to map out all the possible meetings on a piece of paper a) you'll need a big piece of paper, and b) your brain will start to turn to mush.

Good luck.

[TheAlchemist]

hey man,
my brain is on fire! try writting a program to map all the possible meetings and see, thats the easiest way to solve it and still be alive after!

[Maths_Idiot]

what do you mean write a program?
im just 17 i cant write a program

CAN ANYONE SOLVE IT FOR ME

im really interested in the answer but i just cant seem to find it out

[siyan]

I think you can simplify the problem first...

is it possible with 1 red, 2 blue, 3 green.....

i can't figure it out but i'm sure there's a sneaky way. math books are like that.

[Dillinger4]

Are they meeting only one time or multiple times? Im pretty sure that either permutations or combinations are used to figure out a problem like this except that i have yet to learn them I can't see how it possible for all the chameleons to become the same colour though. If the problem is simplified as siyan suggested........ 1 red, 2 blue, 3 green.

gb = r
gb = r
gr = b

nope

rb = g
bg = r
g
g

nope

rg = b
gb = r
gb = r

nope

[sql_lall]

Hehe! a mod question:
thing of when they meet:
b/r -> gg
#greens increses by 2 (mod 3)
#blues increases by -1 = 2 (mod 3)
#reds increases by -1 = 2 (mod 3)

=> say initially
#red = r (mod 3)
#blue = b (mod 3)
#green = g (mod 3)

=> after one meeting, the number of each (mod 3) will be:
r+2 (mod 3)
b+2 (mod 3) and
g+2 (mod 3)

=> after k meetings, the number of each (mod 3) will be:
r+2k (mod 3)
b+2k (mod 3)
g+2k (mod 3)

now, the question asks is it possible to have two of these = 0??
well, this means two of these are true:
1 + 2k = 0 (mod 3) => k = 1 (mod 3)
2 + 2k = 0 (mod 3) => k = 2 (mod 3)
0 + 2k = 0 (mod 3) => k = 0 (mod 3)

however, it is obvois that only one of these can be true
=> It it impossble for all to be one colour.

[Maths_Idiot]

sql_lall, i understand yours except for the (mod 3)
this may be a stupid question but wats a mod and wat has it got to do with it?

[sql_lall]

#1: "What is mod"
When in VBforums, maths section, instead of opening this post, if you go down about 10 or so threads lower there is one called 'Mod Questions'. It has some info about mods, and if you want more i'm sure there's some stuff, just search for it.

#2: "What has it (mod) got to do with this"
You will notice that any time two meet, the number of chameleons of these colours decreases by 1. (i.e. goes up by -1)
The number of cham. of the third colour goes up 2.
It so happens that 2=-1 (mod 3), so we have what is called an invariant. (Something that always stays the same) It is useful in this case, as 13, 14 and 15 are all different (mod 3)

#3: Yes, Australia is #1

[pradeepkrao]

A particular species of chameleon comes in three colours: red, blue and green. Whenever two chameleons of different colours meet they change colour, both changing to the third colour. Thus if a red chameleon meets a blue chameleon they both change to green. When two chameleons of the same colour meet, neither change colour. If there are originally 13 red chameleons, 14 blue chameleons and 15 green chameleons is it possible for all the chameleons to become the same colour? Generalise.

I guess the answer is Yes or No..

Do we need a VB code for this.. .. dont think so..

why 13,14,15..

make it 1R , 2B , 3G (Should not make a difference as they are sequence numbers)

1R meet 1G = 4B

and 0 Red and 2 Green..

2 G meets 2 B = 2 Red

and 0 G and 2 B..

This is never ending.. as it is repetative.

[Maths_Idiot]

thanks guys all your help is great

When in VBforums, maths section, instead of opening this post, if you go down about 10 or so threads lower there is one called 'Mod Questions'. It has some info about mods, and if you want more i'm sure there's some stuff, just search for it.

i had a look at that thread but it didnt really make sense to me
is there a way you can breifly explain to me in lamens terms in relation to this?

thank you

[sql_lall]

Ok, Mod tutorial:

Think of an integer, and another integer less than it.
Divide the bigger by the smaller, you're left with some integer + a remainder (the remainder can be between 0 and (smaller integer-1) I.e:
5/3 = 1 + remainder of 2
9/4 = 2 + remainder of 1
6/2 = 3 + remainder of 0

Now, what mods are, is taking this remainder, and saying the origional number (5 in the 1st example) is "congruent to" the remainder (2) in modulus the divisor (3)
This can be written in short form as:
5 £ 2 (mod 3) //N.B. the "£" is in replace of an equals sign with 3 lines in it, for which i couldn't find the shortcut for.

So you can say stuff like: 29 £ 53 £ 17 £ 5 (mod 6)

Mods are useful for many things (like, proving something is always divisible by a number, WITHOUT using induction), you just need to be able to spot a mod question when it appears (like this one)

[Maths_Idiot]

thanks for all your help guyz
really appreciate it
any more insights will still be extremely helpful

[NotLKH]

Originally posted by Maths_Idiot
IIf there are originally 13 red chameleons, 14 blue chameleons and 15 green chameleons is it possible for all the chameleons to become the same colour?

Turn out the lights!


Seriously, here is the method to get them all Red:

With 13 Red, 14 Blue, and 15 Green,

	Step 1)	Input:		13 Red, 14 Blue, 15 Green
		Process:	14 Blue-Green into 28 Red
		Result:		41 Red, 0 Blue, 1 Green

	Step 2: Input:		41 Red, 0 Blue, 1 Green
		Process:	Sub 1:	Take 1 Red, 1 Green, Slice each into Head, Body, Tail.
				Sub 2:	1 RedHead, 1 Green Head, Becomes 2 Blue Heads
		Result:		40 Whole Red, with 1 Red Body and 1 Red Tail,
				2 Blue Heads,
				1 Green Body, 1 Green Tail.
	Step 3:	Have 1 Blue Head meet 1 Green Body, Becoming 1 RedHead and 1 Red Body
		Have the other Blue Head meet the Green Tail, Becoming 1 Red Head and 1 Red Tail.
		Result:		42 Red, made from 40 Whole Red, 2 Red Heads, 2 Red Bodies and 2 Red Tails.

	TaDaa!!!

[Maths_Idiot]

hahaha way to think outside the box :P
some how i dont think thats what they want you to do

[NotLKH]

Hmm, well I believe its the only way, if any.
Here's My reason why:

Can {13, 14, 15} be converted to any of {42,0,0}, {0,42,0}, or {0,0,42}?

You can determine if a Town of Chamelions can be converted to 
another town quite easily.

For example, say we want to determine if we can convert Town A, 
consisting of {13, 14, 15} to Town B, consisting of {42,0,0}.

Calling our conversion processes RED_BLUE = {-1,-1,2}, 
RED_GREEN = {-1,2,-1}, BLUE_GREEN = {2,-1,-1}, we can set up 
the following formula:

	{13, 14, 15}  + rb*{-1,-1,2} + rg*{-1,2,-1} + bg*{2,-1,-1} = {42,0,0}

Which can easily be expressed as three simultaneous equations:

	13 - rb - rg + 2bg = 42
	14 - rb + 2rg - bg = 0
	15 + 2rb - rg - bg = 0.

These ultimately reduce into the following identities:
	rg = rb + 1/3
	bg = rb + 14 & (2/3)

So,
	{13, 14, 15}  + rb*{-1,-1,2} + (rb + 1/3)*{-1,2,-1} + (rb + 14 & (2/3))*{2,-1,-1} = {42,0,0}
for all rb.

Upon closer inspection, you will see that rb zeros out, so that you 
are left with the final equation {Identity}:
	
	{13, 14, 15}  + (1/3)*{-1,2,-1} + (14&(2/3))*{2,-1,-1} = {42,0,0}

Therefore, you cannot change {13, 14, 15} to {42,0,0} without 
slicing up a couple of chamelions.

I expect that you will come to a similar conclusion after analyzing the other two possibilities.
I only did this one, so the other two might be possible.

However, I also created a progie that treats this similarly to a 
traveling salesman style puzzle, { shortest distance from A to B analyzer}
It finds no answer to any of these three. But, if you wanted to 
know how to go from R(09), B(15), G(18) to R(00), B(42), G(00), 
you'd do it this way:

R(09), B(15), G(18) transforms to R(00), B(42), G(00) in 18 Waves
	Wave 1:: R(09), B(15), G(18) -> RG = R(08), B(17), G(17)
	Wave 2:: R(08), B(17), G(17) -> RG = R(07), B(19), G(16)
	Wave 3:: R(07), B(19), G(16) -> RG = R(06), B(21), G(15)
	Wave 4:: R(06), B(21), G(15) -> RG = R(05), B(23), G(14)
	Wave 5:: R(05), B(23), G(14) -> RG = R(04), B(25), G(13)
	Wave 6:: R(04), B(25), G(13) -> RG = R(03), B(27), G(12)
	Wave 7:: R(03), B(27), G(12) -> RG = R(02), B(29), G(11)
	Wave 8:: R(02), B(29), G(11) -> RG = R(01), B(31), G(10)
	Wave 9:: R(01), B(31), G(10) -> BG = R(03), B(30), G(09)
	Wave 10:: R(03), B(30), G(09) -> RG = R(02), B(32), G(08)
	Wave 11:: R(02), B(32), G(08) -> RG = R(01), B(34), G(07)
	Wave 12:: R(01), B(34), G(07) -> RG = R(00), B(36), G(06)
	Wave 13:: R(00), B(36), G(06) -> BG = R(02), B(35), G(05)
	Wave 14:: R(02), B(35), G(05) -> RG = R(01), B(37), G(04)
	Wave 15:: R(01), B(37), G(04) -> RG = R(00), B(39), G(03)
	Wave 16:: R(00), B(39), G(03) -> BG = R(02), B(38), G(02)
	Wave 17:: R(02), B(38), G(02) -> RG = R(01), B(40), G(01)
	Wave 18:: R(01), B(40), G(01) -> RG = R(00), B(42), G(00)

-Lou

[Jared]

I like your explanation.....

but can u help me understand how you put this together?

Calling our conversion processes RED_BLUE = {-1,-1,2},
RED_GREEN = {-1,2,-1}, BLUE_GREEN = {2,-1,-1}, we can set up
the following formula:

{13, 14, 15} + rb*{-1,-1,2} + rg*{-1,2,-1} + bg*{2,-1,-1} = {42,0,0}

I am being dense right now, and just can't *see* the relation.

Thanks,

[NotLKH]

Certainly. It was initially established by Maths_Idiot, that if a Red and a Blue met, they become Green. This meens that the number of red decreases by 1 and the Number of green Increases by 1, when a Red Cham turns into a Green Cham, and similarly The Blues lessen by 1 and the greens Increase by 1 when a Blue turns Green.

So, when RED Meets Blue,
TOTAL # Red ==> TOTAL # Red - 1,
TOTAL # Blue ==> TOTAL # Blue - 1,
TOTAL # Green ==> TOTAL # Green + 2

So, if we represent a Group of Chamilions with initial counts of {R_i, B_i, G_i}, then
if you have n pairs of Red Blue Chams meet, you end up having a balance of chamelions with the count of {R_f, B_f, G_f}, which can be calculated with the following relation:

{R_f, B_f, G_f} = {R_i, B_i, G_i} + n*{-1,-1,2}

Similarly, again with RedGreen, and BlueGreen. So ultimately, the overall formula to go from one Town of Chams to another Town of Chams is:

{R_f, B_f, G_f} = {R_i, B_i, G_i} + n_rb*{-1,-1,2} + n_rg*{-1,2,-1} + n_bg*{2,-1,-1}

-Hope this helps
-Lou

[Jared]

Thanks, I get it now.

[Shaggy Hiker]

This is sort of like Fermats Last Theorem. NotLKH has come up with the answer, but one is left with the feeling that there is probably a simpler answer. After all, that particular solution seems unlikely to be the one asked for in a math class.

I agree that the answer is no, but I can't quite seem to articulate the reason why it must be no. The step before {42,0,0} must be {x,y,x}. It seems like you might be able to reach this state for any triplet {x,y,z} where the difference between the largest and next largest member of the triplet is a multiple of 3, so long as the difference is not larger than the smallest member of the triplet.

That's about as tight as I have it for now, but there is a further generalization in there somewhere.

And if you're wondering about why I liken this to Fermat's Last Theorem, it is because the proof that has now been delivered was certainly not the one he was thinking of when he wrote the theorem.

[Shaggy Hiker]

Oops, I made a mistake. That answer only holds true for a subset of the whole problem.

In fact, it now appears that the answer is as simple as:

If you have three numbers {x,y,z} and x!=y!=z, then you can achieve a solid color population so long as (x+y+z) = 3n+2 where n is a positive integer.

Of course, if x=y or x=z or y=z, the problem becomes trivial.

So, is this true for all case?

[NotLKH]

Originally posted by Shaggy Hiker
This is sort of like Fermats Last Theorem. NotLKH has come up with the answer, but one is left with the feeling that there is probably a simpler answer. After all, that particular solution seems unlikely to be the one asked for in a math class.

I agree that the answer is no, but I can't quite seem to articulate the reason why it must be no. The step before {42,0,0} must be {x,y,x}. It seems like you might be able to reach this state for any triplet {x,y,z} where the difference between the largest and next largest member of the triplet is a multiple of 3, so long as the difference is not larger than the smallest member of the triplet.

That's about as tight as I have it for now, but there is a further generalization in there somewhere.

And if you're wondering about why I liken this to Fermat's Last Theorem, it is because the proof that has now been delivered was certainly not the one he was thinking of when he wrote the theorem.

Hmm, me, Fermat...
I Like It!



However, I do believe, what you read in my post is exactly what I meant!

If you read SQL_Lals post, with mine in mind, You'll see the comparison quite easily. Perhaps I stated it differently, but ultimately, the question wasn't how to do it, but wether it was possible. I showed how it was possible, because nowbody said we had to do integral math. It was also shown it was impossible to do it with whole chameleons because mathematically, you had to take partials.

Well, I'm no Fermat, but to do it without some chameleon-epitictomies appears to be impossible.


-Lou

[sql_lall]

Ok, in general, with r Red, b Blue and g Green chameleons:
It is possible to get all Chameleons of the same colour, according to the rules, if and only if:
r==b (mod 3) OR (all Chameleons green at the end)
r==g (mod 3) OR (all Chameleons blue at the end)
b==g (mod 3) (all Chameleons red at the end)

Of course, if they are all equal, then you can choose which colour chameleon to have at the end.

You can actually figure out the minimum number of moves, based on which two are equal (mod 3).
i.e. 4 red, 1 blue, 3 green (4==1(mod 3))
4,1,3 ->
3,3,2 ->
2,2,4 ->
1,1,6 ->
0,0,8 = 4 moves
I *think* it is simply whichever of the two is the largest.
Think about 28 red, 1 blue, 2 green (28==1(mod 3))
28,1,2 -> (6 moves, RG->BB twice, RB->GG 4 times)
22,1,8, which is basically the same, but 28 has decreased to 22.
You can see that, all you have to do is swap red with either green or blue, and you'll evetually get all green, after swapping 28 reds.

[Shaggy Hiker]

I see I made a bit of an error...that sucks

I'm still surprised that the answer is as complex as NotLKH stated. What chapter of the math textbook did the problem come from? What was the topic?

[RAEsquivelC]

The OP asked:

"A particular species of chameleon comes in three colours: red, blue and green. Whenever two chameleons of different colours meet they change colour, both changing to the third colour. Thus if a red chameleon meets a blue chameleon they both change to green. When two chameleons of the same colour meet, neither change colour. If there are originally 13 red chameleons, 14 blue chameleons and 15 green chameleons is it possible for all the chameleons to become the same colour? Generalise."

I will address the question at the end, that is, "is it possible for all the chameleons to become the same color?"
============================================
YES! Here is one way:
1) 13 greens meet the 13 reds, producing 26 blues, with 14 original blues and 2 'left-over' greens.
2) one green meets one blue, producing one red.
3) the remaining green meets the remaining red, producing a new blue, at which point ALL chamaleons are blue. Q.E.D.
============================================

[sql_lall]

Really sorry, but not right:
Your line is:
"one green meets one blue, producing one red"

should be
"one green meets one blue, producing two reds."

So you see, you now have an extra red, and if you keep playing about, you will find it is impossible (as the initial numbers are not equivalent in mod 3)