Problem:
Find the number of collections of distinct subsets of with the property that for any two subsets and in the collection, .
Solution:
We need collections of distinct subsets of with the property that for any two subsets and in the collection, .
Let's do casework on the subset in our collection that has the least number of elements.
Suppose the smallest subset has no elements. Notice that for any other subset in the collection, , so this wouldn't work.
Now, suppose that the smallest subset has element in it. For whatever element it is, notice that the number of subsets that contain some element is . Thus, the collection is uniquely made based off whatever element is, so there are solutions in this case.
The next set of cases are when the smallest subsets have elements. Let's bash it by doing casework on how many have elements, and our first case will be only one subset in our collection has elements.
Notice that if those two numbers are , the number of subsets that contain at least elements is which satisfies our requirements perfectly as the one element subset that contains no elements of won't work, meaning we have our initial set followed by all the remaining subsets that are of at least size , which means that the collection is uniquely determined by the values of and , yielding .
The next case is that there are subsets that have elements each, and notice they must have an intersection so we can label them and . We see that again, all subsets that have at least elements work, except which uniquely determines the collection of subsets after choosing the values of yielding .
The last cases are based off subsets that contain elements, but determining the specific "shared elements between them.
These cases are as following:
This case yields elements, as again they uniquely determine the collection .
The next case is that the numbers are of the form . This case yields .
And the last case for subsets of size is subsets of size , of the form . This yields solutions.
The last case is if the minimum size subset has elements, and we notice from our previous case that and so our answer would just be for this case.
Adding these up yields .
The problems on this page are the property of the MAA's American Mathematics Competitions