Let S be a set with 2002 elements and P the set of all its subsets. Prove that for any n (in the range from zero to |P|) we can color n elements of P white, and the rest black, so that the union of any two elements of P with the same color has the same color.
Solution
Let S have m elements and P be the set of its subsets. We show by induction on m that a coloring is possible for any n ≤ |P|. If m = 1, we color both subsets black for n = 0, the empty set white (and the other subset black) for n = 1, and both subsets white for n = 2. Suppose now that a coloring is possible for m (and any n). Consider a set S with m+1 elements. Let b be any element of S. For n ≤ 2m, use induction to color just n subsets of S - {b} white and color black all subsets of S which include b. Then the union of two white subsets is still a subset of S - {b} and hence (by assumption) white. The union of two black subsets of S - {b} is black for the same reason. If one black subset includes b, then so does the union, which must therefore be black. For n > 2m, we have 2m+1 - n < 2m, so we can find a coloring for 2m+1 - n and then swap the colors.
© John Scholes
jscholes@kalva.demon.co.uk
11 May 2002