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

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