2016 UMO Problems/Problem 3
Problem
Can each positive integer be colored either red or blue, such that for all positive integers (not necessarily distinct), if then are not all the same color?
Solution
Solution We claim that no such coloring exists. For the sake of contradiction, assume that such a coloring exists. Without loss of generality, we may assume that 1 is colored red. In the string of steps below, if a number n is known to be colored red, we denote it as , and if it is known to be colored blue, we denote it as . Each of the implications below follow from the fact that if all but one of the distinct numbers in are the same color, then the final number must be a different color. is blue. is red. is blue. Now we have is blue AND is red. This is a contradiction because can only have one color. Therefore, no such coloring exists.
See Also
2016 UMO (Problems • Answer Key • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All UMO Problems and Solutions |