Cardinality of the subsets

Question

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$?

Doctor Who · Answer

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$.

006 Delta · Answer

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.

Cardinality of the subsets

2 Answers

Add your own answers!

Ask a Question