Three chameleons problem
Thread Rating:
Poll
 | 1 vote (20%) | ||
| | 1 vote (20%) | ||
| | 1 vote (20%) | ||
| No votes (0%) | |||
| | 1 vote (20%) | ||
| | 1 vote (20%) | ||
| | 3 votes (60%) | ||
| | 2 votes (40%) | ||
| | 1 vote (20%) | ||
| | 1 vote (20%) |
5 members have voted
May 8th, 2019 at 10:29:35 AM
permalink
A small island has 10 red chameleons, 15 green chameleons, and 20 blue ones. Every time two chameleons of different colors meet, they both change colors to the color not present. Is it possible to get every chameleon the same color? If so, how? If not, why not, and what is a rule of thumb for which situations it is possible?
Usual 24-hold for anyone who has won a beer in the last year. As always, showing your work is required for the beer.
I'd like to suggest a couple of rules going forward for all math puzzles.
First. the person asking the question and giving out the prize gets to make the rules. This should not even need to be said. If you don't like my policy of showing your work, then you're invited to not participate or ask your own questions and you can have any rules you like.
Second, please don't ruin the fun by just plopping down a YouTube link that explains how to find the answer before a satisfactory solution has been provided here. Using spoiler tags does not excuse you from this rule. The point of these puzzles is not to cheat by finding the answer online but to challenge yourself finding the answer. If you give up and must cheat, please keep the answer and solution to yourself until a deserving winner is found.
Usual 24-hold for anyone who has won a beer in the last year. As always, showing your work is required for the beer.
I'd like to suggest a couple of rules going forward for all math puzzles.
First. the person asking the question and giving out the prize gets to make the rules. This should not even need to be said. If you don't like my policy of showing your work, then you're invited to not participate or ask your own questions and you can have any rules you like.
Second, please don't ruin the fun by just plopping down a YouTube link that explains how to find the answer before a satisfactory solution has been provided here. Using spoiler tags does not excuse you from this rule. The point of these puzzles is not to cheat by finding the answer online but to challenge yourself finding the answer. If you give up and must cheat, please keep the answer and solution to yourself until a deserving winner is found.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
May 8th, 2019 at 11:09:54 AM
permalink
No. You still couldn't get this to work out. You would need the difference between the two smaller populations to be a multiple of three. In this case, the difference in numbers between the red & green chameleons is 5, which is not a multiple of three.
The way to get chromatic homogeneity is to take chameleons from the two larger populations to increase the numbers of the smaller population until the smaller population equals the middle one. That way, chameleons from the two smaller populations would each have a partner of a different color so that they could all become the color of the largest population.
However, for each color swap, you increase the smaller population by 2 while, at the same time, reducing the middle population by 1. So, with each color swap, the difference between the two smallest groups would be reduced by 3, or what Patches O'Hoolihan would call a "3-lizard swing" (for you Dodgeball fans out there). So, if the difference in the numbers of the two smallest populations is not a multiple of three, they would bypass each other during one of the color swaps, never being equal to each other.
The way to get chromatic homogeneity is to take chameleons from the two larger populations to increase the numbers of the smaller population until the smaller population equals the middle one. That way, chameleons from the two smaller populations would each have a partner of a different color so that they could all become the color of the largest population.
However, for each color swap, you increase the smaller population by 2 while, at the same time, reducing the middle population by 1. So, with each color swap, the difference between the two smallest groups would be reduced by 3, or what Patches O'Hoolihan would call a "3-lizard swing" (for you Dodgeball fans out there). So, if the difference in the numbers of the two smallest populations is not a multiple of three, they would bypass each other during one of the color swaps, never being equal to each other.
"Dealer has 'rock'... Pay 'paper!'"
May 8th, 2019 at 11:13:15 AM
permalink
I agree with some statements in Joe's answer and disagree with others.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
May 8th, 2019 at 12:03:40 PM
permalink
Quote: WizardI agree with some statements in Joe's answer and disagree with others.
Since the relative sizes of the populations can change, I'll amend my answer to say: if the difference in numbers of any two populations is a multiple of 3, not just the two smallest, they can all get to the same color. If the largest population is one of the two, chameleons can swap color until the larger population becomes one of the two smaller populations that have a difference of three. Than, all can achieve the same color as stated above.
"Dealer has 'rock'... Pay 'paper!'"
May 8th, 2019 at 12:10:37 PM
permalink
I'm going to stay out of it for the rest of the day and hope the forum gets into a discussion about this.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
May 8th, 2019 at 12:47:34 PM
permalink
It's impossible.
In order to turn all the animals to one colour, then at the penultimate step there must be an equal number of two different colours (as well as some of the third), whereby they all turn into the third colour. The proof aims to show it is impossible for two different colours to have the same number.
Initially the number of each colour were 10 = 1 (mod 3), 15 = 0 (mod 3) and 20 = 2 (mod 3).
Assume each operation takes place with two animals changing colours such that the third colour gains two animals and the other colours lose one animal.
Scenario 1 = the colour with 0 (mod 3) is increased by 2 - becoming 2 (mod 3). Thus the others are reduced by 1 to (1-1) 0 (mod 3) and (2-1) 1 (mod 3).
Scenario 2 = the colour with 1 (mod 3) is increased by 2 - becoming 0 (mod 3). Thus the others are reduced by 1 to (0-1) 2 (mod 3) and (2-1) 1 (mod 3).
Scenario 3 = the colour with 2 (mod 3) is increased by 2 - becoming 1 (mod 3). Thus the others are reduced by 1 to (0-1) 2 (mod 3) and (1-1) 0 (mod 3).
Therefore after any transformation one colour is 0 (mod 3), another is 1 (mod 3) and the last is 2 (mod 3).
Therefore no two colours can ever have equal numbers.
In order to turn all the animals to one colour, then at the penultimate step there must be an equal number of two different colours (as well as some of the third), whereby they all turn into the third colour. The proof aims to show it is impossible for two different colours to have the same number.
Initially the number of each colour were 10 = 1 (mod 3), 15 = 0 (mod 3) and 20 = 2 (mod 3).
Assume each operation takes place with two animals changing colours such that the third colour gains two animals and the other colours lose one animal.
Scenario 1 = the colour with 0 (mod 3) is increased by 2 - becoming 2 (mod 3). Thus the others are reduced by 1 to (1-1) 0 (mod 3) and (2-1) 1 (mod 3).
Scenario 2 = the colour with 1 (mod 3) is increased by 2 - becoming 0 (mod 3). Thus the others are reduced by 1 to (0-1) 2 (mod 3) and (2-1) 1 (mod 3).
Scenario 3 = the colour with 2 (mod 3) is increased by 2 - becoming 1 (mod 3). Thus the others are reduced by 1 to (0-1) 2 (mod 3) and (1-1) 0 (mod 3).
Therefore after any transformation one colour is 0 (mod 3), another is 1 (mod 3) and the last is 2 (mod 3).
Therefore no two colours can ever have equal numbers.
May 8th, 2019 at 2:41:08 PM
permalink
Quote: charliepatrickIt's impossible.
In order to turn all the animals to one colour, then at the penultimate step there must be an equal number of two different colours (as well as some of the third), whereby they all turn into the third colour. The proof aims to show it is impossible for two different colours to have the same number.
Initially the number of each colour were 10 = 1 (mod 3), 15 = 0 (mod 3) and 20 = 2 (mod 3).
Assume each operation takes place with two animals changing colours such that the third colour gains two animals and the other colours lose one animal.
Scenario 1 = the colour with 0 (mod 3) is increased by 2 - becoming 2 (mod 3). Thus the others are reduced by 1 to (1-1) 0 (mod 3) and (2-1) 1 (mod 3).
Scenario 2 = the colour with 1 (mod 3) is increased by 2 - becoming 0 (mod 3). Thus the others are reduced by 1 to (0-1) 2 (mod 3) and (2-1) 1 (mod 3).
Scenario 3 = the colour with 2 (mod 3) is increased by 2 - becoming 1 (mod 3). Thus the others are reduced by 1 to (0-1) 2 (mod 3) and (1-1) 0 (mod 3).
Therefore after any transformation one colour is 0 (mod 3), another is 1 (mod 3) and the last is 2 (mod 3).
Therefore no two colours can ever have equal numbers.
Charlie has nailed it. I use the same explanation, but use a handwave mathematics argument.
To satisfy the goal, you must make two colors have the same number, so clearly, invoking clock arithmetic and representing every number as x(mod 3) a minimum requirement is to make two colors have the same x when their number is written as x(mod 3).
Initially the numbers of each colour were 10 = 1 (mod 3), 15 = 0 (mod 3) and 20 = 2 (mod 3). So initially the three colors all have different values of X, that is, 1, 0 and 2, when written as x (mod 3).
Now, every transformation available to us will increase one of the three x values by +2 while the other two x's will be diminished by -1.
However, in mod 3 -or on a clock with 3 hashmarks - increasing a number by +2 has the same effect (on x) as decreasing a number by -1. So all of the transformations will involve changing the value of all three values of x by the same amount. So, these transformations cannot ever result in two of the three starting numbers having identical values of x when written as x(mod 3), therefore no two colors can ever have the same number. So, it is impossible to get to any rotation of (45,0,0).
Initially the numbers of each colour were 10 = 1 (mod 3), 15 = 0 (mod 3) and 20 = 2 (mod 3). So initially the three colors all have different values of X, that is, 1, 0 and 2, when written as x (mod 3).
Now, every transformation available to us will increase one of the three x values by +2 while the other two x's will be diminished by -1.
However, in mod 3 -or on a clock with 3 hashmarks - increasing a number by +2 has the same effect (on x) as decreasing a number by -1. So all of the transformations will involve changing the value of all three values of x by the same amount. So, these transformations cannot ever result in two of the three starting numbers having identical values of x when written as x(mod 3), therefore no two colors can ever have the same number. So, it is impossible to get to any rotation of (45,0,0).
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
May 8th, 2019 at 2:46:12 PM
permalink
Summary: The problem can be reduced to a set of linear equations. Gaussian elimination can then be used to show that no solution exists that can be implemented by the chameleons.
Details:
The solution requires a sequence of operations in which each operation reduces 2 populations by 1 and increases the third by 2. This can be expressed in matrix form as
where [a,b,c] is the # of times a particular population is increased at the expense of the other two (e.g., 'a' is the # of times a red and green pair change into 2 blue).
For the problem to be solveable, there most exist integer values of a, b, and c such that [x, y, z] is equal to one of the following:
- only blue chameleons remain: [-10, -15, +25]
- only green chameleons remain: [-10, +30, -20]
- only red chameleons remain: [+35, -15, -20]
Solutions are obtained using Gaussian Elimination. The easy way to do this (which did NOT exist when I learned this decades ago) is to use one of the many on-line calculators. Doing this for each of the possible outcomes returns, in all three cases, non integer solutions for [a, b, c]. Since we can't change the color of, for example, 2/3 of a chameleon, no solution exists that can be implemented by the chameleons.
My goal of being well informed conflicts with my goal of remaining sane.
May 8th, 2019 at 2:52:36 PM
permalink
Charlie and Gordon's approach is more elegant than mine. I like it.
My goal of being well informed conflicts with my goal of remaining sane.
May 10th, 2019 at 9:29:00 AM
permalink
Thanks Charlie, clever answer. Much cleaner than how I did it. Your answer and solution certainly qualify for the beer, but haven't you earned one in the last year, thus breaking the 24-hold rule?
I think we can call this one good and stop using spoiler tags.
That said, here is how I would frame the answer, which borrows heavily from Charlie's solution.
To eventually get to all chameleons the same color, you have to have the population of two colors the same. Once you do, mix both equal groups together and they will all become the other color, making them all the same.
How can you get two groups the same total? Any operation will increase one group by two and decrease the other two by one. Pick two colors you want to equalize. Call the greater of those two numbers x, the smaller one y, and the one left out z. Have x meet z, to decrease x by 1 and increase y by 2, and we can ignore the effect on z. The difference between x and y will decrease by 3 with each operation. So, to become eventually equal, their difference in the first place must be divisible by 3.
The populations given were 10, 15, and 20. The difference between 10 and 15 is 5, between 10 and 20 is 10, and between 15 and 20 is 5. No difference is divisible by 3 so we'll never be able to match two groups.
A way to quickly check if the difference between two groups is divisible by 3 is to take the difference, add the digits, and if that sum of digits is divisible by 3, then the whole difference is divisible by 3. I'll leave the proof to the reader.
I think we can call this one good and stop using spoiler tags.
That said, here is how I would frame the answer, which borrows heavily from Charlie's solution.
To eventually get to all chameleons the same color, you have to have the population of two colors the same. Once you do, mix both equal groups together and they will all become the other color, making them all the same.
How can you get two groups the same total? Any operation will increase one group by two and decrease the other two by one. Pick two colors you want to equalize. Call the greater of those two numbers x, the smaller one y, and the one left out z. Have x meet z, to decrease x by 1 and increase y by 2, and we can ignore the effect on z. The difference between x and y will decrease by 3 with each operation. So, to become eventually equal, their difference in the first place must be divisible by 3.
The populations given were 10, 15, and 20. The difference between 10 and 15 is 5, between 10 and 20 is 10, and between 15 and 20 is 5. No difference is divisible by 3 so we'll never be able to match two groups.
A way to quickly check if the difference between two groups is divisible by 3 is to take the difference, add the digits, and if that sum of digits is divisible by 3, then the whole difference is divisible by 3. I'll leave the proof to the reader.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
