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


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?

  • $\begingroup$ 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. $\endgroup$ – lulu Sep 11 '18 at 14:08
  • $\begingroup$ @lulu I haven't checked, but I would be flabbergasted if that last paragraph made its way into the problem's original statement. :-) $\endgroup$ – Theo Bendit Sep 11 '18 at 14:30
  • 1
    $\begingroup$ 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. $\endgroup$ – Theo Bendit Sep 11 '18 at 14:32
  • $\begingroup$ @TheoBendit Thanks for the help $\endgroup$ – saisanjeev Sep 11 '18 at 14:33
  • $\begingroup$ @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? $\endgroup$ – saisanjeev Sep 11 '18 at 14:35

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.