a bit of maths: Sets Coloring (Mathematical Induction)

USAMO/2002

Let S be a set with 2002 elements, and let $0 \leq N \leq 2^{2002}$. Prove that it is possible to color every subset of S either blue or red satisfying the following properties:

(1) The union of 2 red subsets is a red subset

(2) The union of 2 blue subsets is a blue subset

(3) There are exactly N red subsets

Solution:

The proof is by the magic of mathematical induction (and of course a clever way to abuse certain relationship about the subsets!). We will perform induction on the size of S.

For $|S| = 1$, the subsets of S are $\{ \{\}, \{a\} \}$. Easily we can color the subsets to fulfill the requirements for all N. This will be the base case.

Induction step: suppose that we have shown that the proposition is true for $|S| = k$ for some $k \geq 1$. To build $T$ where $|T| = k+1$. Notice that the subsets of $T$ can be divided into 2 groups $V$ and $U$ where $V$ is the set of subsets of $T$ containing the $k+1$-th element, while $U$ is the set of subsets of $T$ without the $k+1$-th element. This means that $U$ is exactly the subsets of $S$. Furthermore, $|U| = |S| = 2^k$.

 From here, we have 2 cases to color those N subsets of $T$.

Case 1: where $0 \leq N \leq 2^k$

Using our induction hypothesis, we can color these N subsets of $U$ red, and the remaining subsets of $T$ blue. This is possible since the 2 subsets in $U$ cannot map to $V$ under union, since all subsets in $V$ contains the $k+1$-th element, while $U$ does not.

Case 2: where $2^k < N < 2^{k+1}$

This seems to be a totally new problem, but actually it is just the other side of the same coin! Let $M = 2^{k+1} - N$, and we know that $M < 2^k$. Then we are back with the same situation in Case 1, just that now we want to color $M$ subsets of $U$ blue, and the rest of $T$ red. This construction completes our proof.