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.