# How to prove that such a coloring of the subsets exists?

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.

What does the phrase coloring of subsets mean? I also found a link which provides the solution

https://artofproblemsolving.com/wiki/index.php?title=2002_USAMO_Problems/Problem_1

In this solution why do we consider the case where $N \geq 2^k$. N equal to $2^k$ is fine, but isn't N an integer less than $2^k$ since in the solution we proceed by induction to generalise it for any integer n, not only 2002?

• Once again, you are just cutting and pasting problems with absolutely no effort shown. This one comes from the $2002$ usamo. As with your other problems, the solution to this one can easily be found online. here is the solution to this one. – lulu Sep 11 '18 at 14:08
• @lulu I haven't checked, but I would be flabbergasted if that last paragraph made its way into the problem's original statement. :-) – Theo Bendit Sep 11 '18 at 14:30
• The "coloring of the subsets" refers to a function from the power set of $S$ to a two element set $\lbrace \text{red}, \text{blue}\rbrace$. Basically, you can define a rule that takes any subset of $S$ and assigns it one of two values. – Theo Bendit Sep 11 '18 at 14:32
• @TheoBendit Thanks for the help – saisanjeev Sep 11 '18 at 14:33
• @lulu You are right, I did do that, I even found the solution but didn't really understand it. Do you think I add this solution and also show the step I didn't add, perhaps that would satisfy and maintain the reputation of this website? – saisanjeev Sep 11 '18 at 14:35

## 1 Answer

In the inductive step we assume we have proven that for any set of size $k$ we can properly color the subsets so that $N$ of them are red for any $N$ in the range $[0,2^k]$. We now want to prove the same for $k+1$, which means there are $2^{k+1}$ subsets and we need to show that we can properly color them for any $N$ in the range $[0,2^{k+1}]$. We divide the set into $\{s\}$, the new element and $S'$, which is everything else and has $k$ elements.

The proof then says essentially, if $N \le 2^k$ we had a proper coloring of $S'$ with $N$ subsets colored red, so color all the subsets that include $s$ blue and we are done. If $N \gt 2^k$ you can take all the subsets that include $s$, which is $2^k$ of them, color them red, and fill out with a proper coloring of the set with $k$ elements that has $N-2^k$ red subsets.