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 16 subsets of such that for any two subsets, they share at least 1 element.
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 K in the collection , so this wouldn't work.
Now, suppose that the smallest subset has 1 element in it. For whatever element it is, notice that the number of subsets that contain some element k is
Thus, the collection is uniquely made based off whatever element k is, so there are solutions in this case.
The next set of cases are when the smallest subsets have 2 elements. Let's bash it by doing casework on how many have 2 elements, and our first case will be only one subset in our collection has 2 elements.
Notice that if those two numbers are , the number of subsets that contain at least 3 elements is
which satisfies our requirements perfectly as the one 3 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 3, which means that the collection C is uniquely determined by the values of a and b, yielding
The next case is that there are 2 subsets that have 2 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 3 elements work, except 2 which uniquely determines the collection of subsets after choosing the values of yielding
The last 3 cases are based off 3 subsets that contain 2 elements, but determining the specific "shared elements between them.
These cases are as following:
This case yields 20 elements, as again they uniquely determine the collection C.
The next case is that the numbers are of the form
This case yields
And the last case for subsets of size 2 is 4 subsets of size 2, of the form
This yields 5 solutions.
The last case is if the minimum size subset has 3 elements, and we notice from our previous case that
and so our answer would just be 1 for this case.
Adding these up yields
The problems on this page are the property of the MAA's American Mathematics Competitions