Problem:
Let , where . Each of the subsets of is to be colored red or blue. (The subset itself is assigned a color and not its individual elements.) For any set , we then write for the number of subsets of that are blue.
Determine the number of colorings that satisfy the following condition: for any subsets and of ,
Solution:
The answer is .
Specifically, the colorings we want are of the following forms: either there are no blue sets; or for each element we define one of three types of restriction - either must be in can't be in , or is unrestricted - and the blue sets are exactly the ones that satisfy every restriction. It's easy to check such a coloring meets the condition, using the formula
where if is unrestricted and 1 otherwise, and if is required to be present and 1 otherwise.
We want to show that if there's at least one blue set, then the class of blue sets is of this form.
If some element of is in every blue set, take it out and induct. If some element of is not in any blue set, take it out and induct. Otherwise, every element has some blue set containing it and some blue set not containing it. In this case we'll show that all sets are blue (i.e. every element is unrestricted).
First show is blue. To show this, let be a minimal blue set. If nonempty, take ; by assumption there's blue not containing . Then the condition is violated with and , since . Next, show any singleton is blue. Otherwise, let be a minimal blue set containing , and let and . We get (where ), a contradiction. Finally, any set is blue. Otherwise, let be a minimal non-blue set and two different elements. Taking gives a contradiction.
The problems on this page are the property of the MAA's American Mathematics Competitions