Patriotic chameleons: Difference between revisions
Jump to navigation
Jump to search
Oscarlevin (talk | contribs) Created page with "This is a problem I saw on someone's Putnam Exam review sheet. ==Puzzle== For last year's 4th of July party, you bought 2010 chameleons: an equal number colored red, white, and..." |
Oscarlevin (talk | contribs) No edit summary |
||
| Line 1: | Line 1: | ||
This is a problem I saw on someone's Putnam Exam review sheet. | This is a problem based on one I saw on someone's Putnam Exam review sheet. | ||
==Puzzle== | ==Puzzle== | ||
For | For next year's 4th of July party, you buy 2011 chameleons: some red, some white and some blue. These chameleons have the strange property that whenever two of different colors meet, they both change into the third color. Must there be a color among red, white and blue for which it is impossible for all of the chameleons to simultaneously become that color? | ||
==Help== | |||
{{Hint | You know you have some chameleons of each color. Do you know that there must be two colors with a different number of chameleons in each? What can that difference be? What happens to that difference when two chameleons meet?}} | |||
{{Answer | Yes, there must always be such a color.}} | |||
{{Solution | Since 2011 is not divisible by 3, there must be two colors (say red and white) which are not both multiples of 3. That is, the difference in the number of red and white chameleons is either 1 or 2 modulo 3. We will show that it is impossible for the chameleons to all change to the ''other'' color (in our case, blue). | |||
Let <m>D = R - W</m> be the difference between the number of red and white chameleons. Now consider what happens to <m>D</m> when two chameleons of different colors meet: | |||
:Case 1. A red and white chameleon meet: both chameleons change to blue. The number of red and white chameleons both drop by 1, so <m>D</m> remains constant. | |||
:Case 2. A red and and a blue chameleon meet: both chameleons change to white. The number of red chameleons drop by 1, and the number of white chameleons increases by 2. Thus <m>D</m> decreases by 3. | |||
:Case 3. A white and a blue chameleon meet: both change to red. The number of red chameleons increases by 2, and the number of white chameleons decreases by 1. Thus <m>D</m> increases by 3. | |||
Notice that in each case, the remainder of <m>D</m> when divided by 3 remains the same. Since <m>D</m> was 1 or 2 modulo 3 to begin with, it will always be such. Therefore it is impossible for all the chameleons to be simultaneously blue, as that would make <m>D = 0</m>.}} | |||
[[Category: Number theory]] | [[Category: Number theory]] | ||
Current revision as of 08:40, 1 December 2010
This is a problem based on one I saw on someone's Putnam Exam review sheet.
Puzzle
For next year's 4th of July party, you buy 2011 chameleons: some red, some white and some blue. These chameleons have the strange property that whenever two of different colors meet, they both change into the third color. Must there be a color among red, white and blue for which it is impossible for all of the chameleons to simultaneously become that color?
Help
Hint
You know you have some chameleons of each color. Do you know that there must be two colors with a different number of chameleons in each? What can that difference be? What happens to that difference when two chameleons meet?
Answer
Yes, there must always be such a color.
Solution
{{{1}}}