Problem:
Find the number of collections of distinct subsets of with the property that for any two subsets and in the collection, .
Solution:
Answer (081):
Note that the subsets of can be paired, where each pair is comprised of two complementary sets. Any collection of 16 subsets satisfying the given nonempty-intersection condition cannot contain two sets from the same pair. Because there are 16 pairs, the collection must have one subset from each pair. Note that the empty set cannot be one of the sets in the collection, implying that the collection must contain .
Suppose the collection contains the size-1 subset . Then every other set in the collection must contain . In other words, the collection must be the 16 subsets that contain . There are 5 possibilities for , so there are 5 collections that contain a size- 1 subset.
Alternatively, suppose the collection contains no size-1 subset. This implies that it contains all 5 of the size4 subsets because they are paired with the size- 1 subsets. The collection must also contain 10 of the size- 2 or size- 3 subsets, one from each of the 10 size- 2 and size- 3 complementary pairs. Note that any subset with 3 or more elements will have nonempty intersection with all subsets with size 3 or greater and all subsets of size 2 that are not its complement. Thus the collection of all the size- 3 subsets (and all the size- 4 and size- 5 subsets) will all satisfy the required condition.
It is left to determine which collections of size-2 subsets-call them doublets-are pairwise non-disjoint.
Therefore the total number of collections is .
The problems and solutions on this page are the property of the MAA's American Mathematics Competitions