a) We want to choose subsets $A _ { 1 } , A _ { 2 } , \ldots , A _ { k }$ of $\{ 1,2 , \ldots , n \}$ such that any two of the chosen subsets have nonempty intersection. Show that the size $k$ of any such collection of subsets is at most $2 ^ { n - 1 }$. b) For $n > 2$ show that we can always find a collection of $2 ^ { n - 1 }$ subsets $A _ { 1 } , A _ { 2 } , \ldots$ of $\{ 1,2 , \ldots , n \}$ such that any two of the $A _ { i }$ intersect, but the intersection of all $A _ { i }$ is empty.
a) We want to choose subsets $A _ { 1 } , A _ { 2 } , \ldots , A _ { k }$ of $\{ 1,2 , \ldots , n \}$ such that any two of the chosen subsets have nonempty intersection. Show that the size $k$ of any such collection of subsets is at most $2 ^ { n - 1 }$.\\
b) For $n > 2$ show that we can always find a collection of $2 ^ { n - 1 }$ subsets $A _ { 1 } , A _ { 2 } , \ldots$ of $\{ 1,2 , \ldots , n \}$ such that any two of the $A _ { i }$ intersect, but the intersection of all $A _ { i }$ is empty.