Saturday, January 7, 2006

Inductfully Done. Topic: Sets. Level: Olympiad.

Problem: (2002 USAMO - #1) Let $S$ be a set with $2002$ elements, and let $N$ be an integer with $0 \leq N \leq 2^{2002}$. Prove that it is possible to color every subset of $S$ either black or white so that the following conditions hold:

(a) the union of any two white subsets is white;
(b) the union of any two black subsets is black;
(c) there are exactly $N$ white subsets.

Solution: We apply induction on the $2002$, which we will call $k$, with $0 \le N \le 2^k$. Let the set be $S = \{a_1,\ldots,a_k\}$.

For $k = 1$, we have $S = \{a_1\}$.

If $N = 0$, we may color both $\{\emptyset\}, \{a_1\}$ black.
If $N = 1$, we may color $\{\emptyset\}$ black and $\{a_1\}$ white.
If $N = 2$, we may color both $\{\emptyset\}, \{a_1\}$ white.

So assume the condition is satisfied for some $k = n$. We wish to show the condition is also satisfied by $k = n+1$.

First consider the case $0 \le N \le 2^n$. There exists some coloring when $k = n$, so we take the same coloring for $k = n+1$ and color all the new sets black. Clearly all the new sets have the new element $a_{n+1}$ so the union of any of the old sets cannot be a new one and the union of any of the new sets cannot be an old one. And we preserve the number of white subsets, $N$.

Now consider the case $2^n+1 \le N \le 2^{n+1}$. Take the same coloring as $M = 2^{n+1}-N$ except reverse white and black. The union condition obviously still holds by what was shown above and there are exactly $N$ white subsets now because there were originally $2^{n+1}-M = N$ black subsets for the $M$ case.

Hence the condition is true for all positive integral $k$, which means the case $k = 2002$ is true as well. QED.

--------------------

Practice Problem #1: (2005 AMC-12A - #23) Two distinct numbers a and b are chosen randomly from the set $\{ 2, 2^2, 2^3, \ldots, 2^{25} \}$. What is the probability that $\log_{a} b$ is an integer?

Practice Problem #2: (1971 IMO - #3) Prove that we can find an infinite set of positive integers of the form $2^n-3$ (where n is a positive integer) every pair of which are relatively prime.