Difference between revisions of "2002 USAMO Problems/Problem 1"
Line 35: | Line 35: | ||
{{alternate solutions}} | {{alternate solutions}} | ||
− | |||
− | |||
== Resources == | == Resources == |
Revision as of 09:52, 27 April 2011
Problem
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.
Solutions
Solution 1
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.
Solution 2
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.