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.