Problem:
Let be a set with elements, and let be an integer with . Prove that it is possible to color every subset of either black or white so that the following conditions hold:
Solution:
First Solution: We prove that this can be done for any -element set. where is an positive integer, and integer with .
We induct on . The base case is trivial. Assume that the desired coloring can be done to the subsets of set and integer with . We show that there is a desired coloring for set and integer . I with . We consider the following cases.
(i) . Applying the induction hypothesis to and . we geet a coloring of all subsets of satisfying conditions (a), (b), (c). All uncolored subsets of contains element , we color all of them blue. It is not hard to see that this coloring of all the subsets of satisiying conditions (a). 1). (c).
(ii) . Applying the induction hypothesis to and , we geet a coloring of all subsets of satisfying conditions . All uncolored subsets of contains element , we color all of then blue. Finally, we switch the color of each subset: if it is blue now, we recolor it red: it is red now, we recolor it blue. It is not hard to see that this coloring of all the subsets of satisfying conditions .
Thus our induction is complete.
Second Solution: If , we color every subset black; if , we colu: every subset white. Now suppose neither of these holds. We may assume that . Write in binary representation:
where the are all distinct; then each is an element of . Color each red. and color all the other elements of blue. Now declare each nonempty subset of to he\
the color of its largest element, and color the empty subset blue. If are any two nonempty subsets of , then the largest element of equals the largest element of or the largest element of , and if is empty, then . Statements (a) and (b) readily follow from this. To verify (c), notice that, for each , there are subsets of whose largest element is (obtained by taking in combination with any of the elements ). If we sum over all , each red subset is counted exactly once. and we get red subsets.
The problems on this page are the property of the MAA's American Mathematics Competitions