2002 USAMO Problems/Problem 1

Problem

Let $S$ be a set with 2002 elements, and let $N$ be an integer with $0 \le N \le 2^{2002}$ . Prove that it is possible to color every subset of $S$ 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 $N$ red subsets.

Solutions

Solution 1

Let a set colored in such a manner be properly colored. We prove that any set with $n$ elements can be properly colored for any $0 \le N \le 2^n$ . We proceed by induction.

The base case, $n = 0$ , is trivial.

Suppose that our claim holds for $n = k$ . Let $s \in S$ , $|S| = k + 1$ , and let $S'$ denote the set of all elements of $S$ other than $s$ .

If $N \le 2^k$ , then we may color all subsets of $S$ which contain $s$ blue, and we may properly color $S'$ . This is a proper coloring because the union of any two red sets must be a subset of $S'$ , which is properly colored, and any the union of any two blue sets either must be in $S'$ , which is properly colored, or must contain $s$ and therefore be blue.

If $N > 2^k$ , then we color all subsets containing $s$ red, and we color $N - 2^k$ elements of $S'$ red in such a way that $S'$ is colored properly. Then $S$ is properly colored, using similar reasoning as before. Thus the induction is complete.

Solution 2

If $N = 0$ , color every subset blue. If $N = 2^{2002}$ , color every subset red. Otherwise, let $S$ be $\{ 0, 1, \ldots , 2^{2002}-1 \}$ . Write $N$ in binary, i.e., let

$N = \sum_{i=1}^{k} 2^{a_i}$ ,

where each of the $a_i$ is an element of $S$ . We color each of the $a_i$ red and all the other elements of $S$ 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 $n \in S$ , there are $2^{n}$ subsets of $S$ with $n$ as a maximal element, so $\sum_{i=1}^{k} 2^{a_i} = N$ subsets of $S$ 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.

Color 2001 subsets of 1 element blue, color the 2002nd subset red, and color the empty set blue. There are $2^{2001}$ blue subsets and the union of each of those subsets and the red "1 element" subset can be colored either red or blue. That takes care of cases $\{0,1, \ldots , 2^{2001} \}$ . In order to take care of the rest, switch blue and red and do the same thing.

Resources

Page

Toolbox

Search