weaselman
weaselman
  • Threads: 20
  • Posts: 2349
Joined: Jul 11, 2010
September 6th, 2010 at 10:06:05 AM permalink
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?
"When two people always agree one of them is unnecessary"
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
September 6th, 2010 at 10:48:35 AM permalink
I say 0%, but will refrain from saying why, for now.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
mkl654321
mkl654321
  • Threads: 65
  • Posts: 3412
Joined: Aug 8, 2010
September 6th, 2010 at 12:05:34 PM permalink
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.
The fact that a believer is happier than a skeptic is no more to the point than the fact that a drunken man is happier than a sober one. The happiness of credulity is a cheap and dangerous quality.---George Bernard Shaw
weaselman
weaselman
  • Threads: 20
  • Posts: 2349
Joined: Jul 11, 2010
September 6th, 2010 at 12:31:00 PM permalink
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 ...
"When two people always agree one of them is unnecessary"
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
September 6th, 2010 at 12:36:22 PM permalink
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.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
weaselman
weaselman
  • Threads: 20
  • Posts: 2349
Joined: Jul 11, 2010
September 6th, 2010 at 12:58:14 PM permalink
Two of the remainders being zero is indeed the sufficient condition. But not necessary.
"When two people always agree one of them is unnecessary"
Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
September 6th, 2010 at 2:25:22 PM permalink
I wonder if the explanation could be simplified even further.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
dwheatley
dwheatley
  • Threads: 25
  • Posts: 1246
Joined: Nov 16, 2009
September 6th, 2010 at 3:01:00 PM permalink
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.
Wisdom is the quality that keeps you out of situations where you would otherwise need it
weaselman
weaselman
  • Threads: 20
  • Posts: 2349
Joined: Jul 11, 2010
September 6th, 2010 at 5:59:29 PM permalink
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.
"When two people always agree one of them is unnecessary"
  • Jump to: