• Support PF! Buy your school textbooks, materials and every day products Here!

Mutating salamanders

  • Thread starter pivoxa15
  • Start date
  • #1
2,255
1

Homework Statement


There are 7 red, 8 blue and 15 green salamanders on a small island. Whenever two of the same colour meet they mutate, one into each of the other colours. Whenever two of a different colour meets they both mutate into the third colour. Can it ever happen that they are all the same colour? Justify your answer. [Hint: Think about the integers mod 3.]


The Attempt at a Solution


I made my computations by brute force and found the following combinations left

29R and 1G
29G and 1B
29B and 1R

There might be other combinations like it but it just shows that it is not possible to get all 30 to be all R, G nor B because when you get 29 of one colour than it’s impossible to turn the other colour into another because to do that, one of the 29 itself must change which after a bit of combining leads to at best 29 again. My solution is not rigours and kind of intuitive. Is it okay? I didn’t make use of the hint which is not good I think.
 

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,808
933
You didn't try to use the hint? 15= 0 mod 3, 7= 1 mod 3, and 8= 2 mod 3.
Whenever there is a "mutation", 2 numbers are reduced by 1 and the third is increased by two. In other words, if the numbers are a mod 3, b mod 3, c mod 3, after a "mutation", we have a-1 mod 3, b-1 mod 3, c+ 2, mod 3. What are the three possible values?

Of course, it all 30 were of the same color, they would all be 0 mod 3. Is that possible?
 
  • #3
2,255
1
The trouble is I don't see the significance of mod 3. Why use mod 3. Why do all of them have to intially start with a mod 3 number?
 
  • #4
737
0
Although there is not mathematical significance in choosing mod 3, there is practical significance. The math should hold in all bases, but choosing mod 3 gives several advantages. There is a convenience that [tex]30 \equiv 0 \pmod{3}[/tex] so we do not need to keep track of two different final answers, one for the color that might have all 30 salamanders and the other for the depleted colors.

Every number in mod 3 is equivalent to 0, 1, or 2. Using HallsofIvy's explanation of what a mutation does to the number of red, blue, and green salamanders, you will find that only a few options need to be checked because the numbers begin wrapping around.

Suppose, as in the problem, there are 7 red, 8 blue and 15 green salamanders. These numbers are equivalent to 1, 2, and 0, respectively, in base 3. If red were the final color of choice, we find that after one mutation there are 0 reds [9 = 3 = 0 (mod 3)], 1 [7 = 1 (mod 3)] blue, and 2 [14 = 2 (mod 3)]. Carrying this same mutation out twice more, you will find that once again there are 1 red, 2 blue, and 0 green salamanders mod 3, so you can stop since any further of the same treatment would repeat.

The simple example shows a snippet of what would happen if you were to do this systematically. Compare it to the amount of work you would do if you had chosen mod 60 (problem isn't simplified at all!) or even mod 10. As it turns out, in base 3, you don't even have to do it completely systematically if you can reason it out a little with logic.
 
  • #5
HallsofIvy
Science Advisor
Homework Helper
41,808
933
There is enormous "mathematical significance"!

pivoxa15, try answering my question:
Whenever there is a "mutation", 2 numbers are reduced by 1 and the third is increased by two. In other words, if the numbers are a mod 3, b mod 3, c mod 3, after a "mutation", we have a-1 mod 3, b-1 mod 3, c+ 2, mod 3. What are the three possible values?

Suppose a= 0 , b= 1, c= 2, all mod 3, and we subtract 1 from a and b and add 2 to c. What are the new values for a, b, c mod 3?

Suppose a= 0 , b= 1, c= 2, all mod 3, and we subtract 1 from b and c and add 2 to a. What are the new values for a, b, c mod 3?

Suppose a= 0 , b= 1, c= 2, all mod 3, and we subtract 1 from a and c and add 2 to b. What are the new values for a, b, c mod 3?

What does that tell you?
 
  • #6
737
0
I didn't mean to imply that selecting mod 3 was not significant; it just wasn't technically necessary. In other bases, it would be a lot of brute forcing, however, so there isn't a better way to do it not in mod 3.
 
  • #7
2,255
1
There are two types of mutations.

1. same colour
2. different colour

HallsofIvy, you described the mutation between different colours and by following your example, I got that for all three cases, I am always left with 1,2,0 for a,b,c respectively.

With mutation 1, I got 0,1,2 following the same groups and order of colloisions. The different types of mutations and order of mutations can mix but for a,b,c mod 3 they will always contain the three numbers 0,1 and 2. The question started with 3 groups of salamanders that when calculated modulo 3 was left with the numbers 0,1,2 to start with. Therefore no matter how many mutations not all three types will be left with 0 mod 3 which it should if all were to mutate to the same colour. Is this the argument?
 
  • #8
HallsofIvy
Science Advisor
Homework Helper
41,808
933
Yes, exactly. You start with the number of each color being 0, 1, and 2 mod 3. Any one mutation changes the number but it is easy to look at the three possible changes and see that you are always left with 0, 1, and 2 mod 3. If all salamanders were of one color, that would be all three kinds 0 mod 3 which is impossible.

Tedjn, yes, we were basically saying the same thing.
 
Top