1. Subsets (2)

We want to select as many subsets of [n] as possible so that any two selected subsets have at least one element in common. What is the largest number of subsets we can select?

2. Re: Subsets (2)

I may commit a mistake in my working so please check it.

Claim: There are at least $\displaystyle 2^{n-1}$ ways of doing this.
Proof: Consider the set $\displaystyle A=\{2,3, \ldots, n\}$. There are $\displaystyle 2^{n-1}$ possible sunsets of this set.
plug in the element $\displaystyle 1$ in each of the subsets of $\displaystyle A$ and we will have $\displaystyle 2^{n-1}$ subsets of $\displaystyle [n]$ any two of which have $\displaystyle 1$ as a common element.

Claim2: There are no more than $\displaystyle 2^{n-1}$ ways of doing this.
Proof: Suppose $\displaystyle 2^{n-1}$ subsets are found out which satisfy the question's demand. If $\displaystyle B$ is a subset then the complement of $\displaystyle B$ cant appear in our list of subsets. So for each subset of $\displaystyle [n]$ chosen there is one subset you can't choose namely its complement. Since we had chosen $\displaystyle 2^{n-1}$ subsets, there are precisely $\displaystyle 2^{n-1}$ subsets(complements of the chosen subsets) we can't chose. Since $\displaystyle 2^{n-1}+2^{n-1}=2^n$ we see that we can't choose any more subsets as there were only $\displaystyle 2^n$ possible subsets of $\displaystyle [n]$.