## Tuesday, August 12, 2014

### 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.