RGB Island

On an island named RGB there is a population of chameleons. Each chameleon is either red, green or blue. When two chameleons of different colors meet, they both change their color to the third one. What is the probability of the event that the entire population ends up being the same color if initially there are 18 red, 19 green and 20 blue chameleons?

I say 0%, but will refrain from saying why, for now.

The final meeting before everyone turns the same color would be between the last two holdouts. However, I was thinking, how could that situation have come about in the first place? The only way is if there were four holdouts, and two of them met just previously, and were turned to the majority color. This would have been happening, regressively, to PAIRS of chameleons. So it would seem that, working backwards, you need X number of the "final" color, and an equal number of each of the other colors, something like 19-18-18. Then each of the minority colors could meet in pairs, while the majority color hid somewhere, and the minorities would all be turned green. So it seems that the monochromatic result is at least POSSIBLE. The question becomes, then, is it possible given the stated conditions?

Let's assume deterministic chameleons, who WANT to become monochromatic (spurning diversity). Can the reds and greens conspire to all become blue? No, because there will always be one holdout (due to the odd number of non-blue chameleons). Can the greens and blue become red? No--same reason. The reds and blues can't all become green, because there will be a couple of blues left over after all the possible red-blue meetings take place.

So it seems that the question is, can the existing population reach a state where any two colors are equal in number? If that case occurs, then all they have to do is engage in a succession of meetings between those two colors, to the exclusion of all other meetings. It would also seem that if that state cannot be reached, then the probability is zero (due to my intuitive evaluation that if a given outcome cannot be FORCED, then it will also never happen randomly). For the number set 18,19,20, it is impossible to add 2 to one number, subtract 1 from the others, and then have any two numbers equal. I had initially thought that the mere fact that the total number of chameleons was odd was the reason for this, but then I realized that you could have a reducible population of, say, 19-19-19. Or for that matter, 37-10-10.

So my gut feeling is that monochromatic harmony will never happen, though I seem to be dancing around but not grasping the reason WHY.

Quote: mkl654321

I had initially thought that the mere fact that the total number of chameleons was odd was the reason for this, but then I realized that you could have a reducible population of, say, 19-19-19. Or for that matter, 37-10-10.

1-5-85 is another example. And 6-4-8 is an "all even" counterexample (no chance of harmony).
You are close, but not quite there yet ...

I note that at all times if you divide each total by 3, there will be one remainder each of 0, 1, and 2. If there were only one color left then two of the remainders would be 0.

Two of the remainders being zero is indeed the sufficient condition. But not necessary.

I wonder if the explanation could be simplified even further.

Quote: Wizard

I note that at all times if you divide each total by 3, there will be one remainder each of 0, 1, and 2.

This is enough to prove the population will never have colour harmony. At the beginning of the problem the 3 remainders mod 3 are 0, 1 and 2. After a meeting, the remainders are again: 0, 1 and 2.
[ why? - A meeting subtracts 1 from two colours and adds 2 to one colour. So if mod 0 and mod 1 meet, their old colours become mod 2 and mod 0, while the new colour becomes mod 1. The same thing happens if mod 0 and mod 2 meet, or if mod 1 and mod 2 meet. ]

So, like the wizard said, at all times the remainders mod 3 are 0,1,2. No colour harmony.

The other 9 starting possibilities are actually grouped into 3-tuple cycles. 0,0,0 becomes 2,2,2 after one meeting, which becomes 1,1,1, then back to 0,0,0.
0,0,1 becomes 0,2,2 becomes 1,1,2.
0,0,2 becomes 1,2,2 becomes 0,1,1.

These three cycles all have two zeroes in them, so colour harmony is possible with every other class of starting numbers mod 3, just not 0,1,2.

So, to answer an unasked question, if the number of chameleons of each colour was uniformly random, there is a 10% chance that colour harmony is outright impossible.

Yes, this is correct.
An easier way to see this is to consider the differences between the pairs of the three counts. The remainder mod 3 of any difference does not change after a meeting (n1-1)-(n2-1)=n1-n2, (n3+2)-(n1-1)=n3+3 etc.). If two counts ever become equal (0), the remainder of their difference is 0, and that means that it must have been 0 all along. Or equivalently, the two of the remainders of the original counts must be equal.