## Friday, January 6, 2006

### Colorful! Topic: Sets. Level: Olympiad.

Problem: (1985 IMO - #2) Let $n$ and $k$ be relatively prime positive integers with $k Solution: We will start from some element$a$and show that we can equate it with any other element in$M$. First, we note that if$a \equiv b \pmod{k}$,$a$and$b$have the same color since they differ by a multiple of$k$, so it is only necessary to show that all residues modulo$k$are the same color. Also,$a \pmod{k}$and$n-a \pmod{k}$have the same color, as given. (1) By the second condition, we can also infer that$a \pmod{k}$and$ -a \pmod{k}$are the same color (2) because we just take an element$x \equiv a \pmod{k}$such that$x < k$and we have$x \equiv a \pmod{k}$and$|x-k| = k-x \equiv -x \equiv a \pmod{k}$the same color. So we generate residues$\pmod{k}$as follows. We have$a$blue. If$mn+a$is blue for some integer$m$, we have$ -mn-a$is blue by (2) and$n-(-mn-a) = (m+1)n+a$is blue by (1). Hence by induction all$mn+a$are blue. But noting that$(n,k) = 1$,$mn+a$clearly takes on all residues modulo$k$and the proof is complete. QED. -------------------- Practice 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.