I have the following problem. Let the sets $A_i$, $1 \leq i \leq k$ be distinct subest of $\{1,2,...,n\}$. Suppose $A_i \cap A_j \neq \emptyset$ for all $i$ and $j$. Show that $k \leq 2^{n-1}$ and give an example where equality holds.
For the first part my argument was the following, we know that we want the sets all to at least one common element, so say they all share element $x$. Now, to form different subsets we can only choose elements from the set $\{1,...,x-1,x+1,...,n\}$. So, this implies that the maximum number of subsets, where all share element $x$ will be $2^{n-1}$. Is this a right approach to the problem?
Also, do you have any suggestions for the second part of the problem?
You cannot assume that $\bigcap_{i=1}^kA_i=\varnothing$. If $n=3$, for instance, the sets might by $\{1,2\}$, $\{1,3\}$, $\{2,3\}$, and $\{1,2,3\}$, whose intersection is $\varnothing$ even though no two of them are disjoint.
HINT: Suppose that $k>2^{n-1}$, and use the pigeonhole principle. The $2^n$ subsets of $\{1,\ldots,n\}$ can be divided up into pairs of complementary subsets, like the pair $\big\{\{1\},\{2,3\}\big\}$ in the case $n=3$. In terms of $n$, how many such pairs are there? Can the family $\{A_1,\ldots,A_k\}$ contain both members of any pair?
Your incorrect argument for the first part essentially answers the second part. Let the subsets of $\{2,\ldots,n\}$ be $B_1,B_2,\ldots,B_{2^{n-1}}$, and for $i=1,\ldots,2^{n-1}$ let $A_i=\{1\}\cup B_i$. Now just verify that this actually works.