# Cardinality of the subsets

Mathematics Asked by Rajat Taneja on October 24, 2020

Let $$S$$ be a collection of subsets of $${1,2,dots,100}$$ such that the intersection of any two sets in $$S$$ is non empty.

What is the maximum possible cardinality $$|S|$$ of set $$S$$?

It's possible to get to $$2^{99}$$ sets by taking the set of all subsets containing 1.

It's not possible to get to any more than $$2^{99}$$ sets because if we did, we'd have a set and its complement both in $$S$$.

Answered by Doctor Who on October 24, 2020

As $${1,2,...,100}$$ is a finite set, then we can say that all sets in $$S$$ has a common element. Let $$1$$ be the common element. Then each other element can either be in or not be in a given subset. So using basic combinatorics, the total number of possible subsets with $$1$$ as one of its elements is $$2^{99}$$, as there are 99 other elements to choose from. So that's your answer. Total of $$2^{99}$$ sets in collection $$S$$.

Sorry for bad formatting by the way.

Answered by 006 Delta on October 24, 2020