2002 USAMO Problems/Problem 1
Let be a set with 2002 elements, and let be an integer with . Prove that it is possible to color every subset of either blue or red so that the following conditions hold:
(a) the union of any two red subsets is red;
(b) the union of any two blue subsets is blue;
(c) there are exactly red subsets.
Let a set colored in such a manner be properly colored. We prove that any set with elements can be properly colored for any . We proceed by induction.
The base case, , is trivial.
Suppose that our claim holds for . Let , , and let denote the set of all elements of other than .
If , then we may color all subsets of which contain blue, and we may properly color . This is a proper coloring because the union of any two red sets must be a subset of , which is properly colored, and any the union of any two blue sets either must be in , which is properly colored, or must contain and therefore be blue.
If , then we color all subsets containing red, and we color elements of red in such a way that is colored properly. Then is properly colored, using similar reasoning as before. Thus the induction is complete.
If , color every subset blue. If , color every subset red. Otherwise, let be . Write in binary, i.e., let
where each of the is an element of . We color each of the red and all the other elements of blue. We color the empty set blue, and we color any other set the color of its largest element. This satisfies the problem's first two conditions, as the largest element of the union of two red (or blue) sets will have a red (or blue) number as its largest element. In addition, for each integer , there are subsets of with as a maximal element, so subsets of are colored red, as desired.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
|2002 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAMO Problems and Solutions|