Difference between revisions of "2002 USAMO Problems/Problem 1"
m (This is a guess about what the problem is supposed to say) |
(→Solution 1) |
||
Line 13: | Line 13: | ||
=== Solution 1 === | === Solution 1 === | ||
− | Let a set colored in such a manner be ''properly colored''. We prove that any set with <math> | + | Let a set colored in such a manner be ''properly colored''. We prove that any set with <math>n </math> elements can be properly colored for any <math> 0 \le N \le 2^n </math>. We proceed by induction. |
− | The base case, <math> | + | The base case, <math>n = 0 </math>, is trivial. |
− | Suppose that our claim holds for <math> | + | Suppose that our claim holds for <math>n = k </math>. Let <math>s \in S </math>, <math>|S| = k + 1 </math>, and let <math>S' </math> denote the set of all elements of <math>S </math> other than <math>s </math>. |
− | If <math> N \le 2^k </math>, then we may | + | If <math> N \le 2^k </math>, then we may color all subsets of <math>S </math> which contain <math>s </math> blue, and we may properly color <math>S' </math>. This is a proper coloring because the union of any two red sets must be a subset of <math>S' </math>, which is properly colored, and any the union of any two blue sets either must be in <math>S' </math>, which is properly colored, or must contain <math>s </math> and therefore be blue. |
− | If <math> | + | If <math>N > 2^k </math>, then we color all subsets containing <math>s </math> red, and we color <math>N - 2^k </math> elements of <math>S' </math> red in such a way that <math>S' </math> is colored properly. Then <math>S </math> is properly colored, using similar reasoning as before. Thus the induction is complete. |
=== Solution 2 === | === Solution 2 === |
Revision as of 02:07, 28 June 2009
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.