XXI OM - I - Problem 10

Find the largest natural number $ k $ with the following property: there exist $ k $ different subsets of an $ n $-element set, such that any two of them have a non-empty intersection.
Let the sought number be denoted by $ k(n) $. We will prove that $ k(n) = 2^{n-1} $. To each $ n $-term sequence with values $ 0 $ or $ 1 $, we assign the set of indices such that the corresponding terms of the sequence are equal to $ 1 $. This assignment establishes a one-to-one correspondence between the set of all $ n $-term sequences with values $ 0 $ or $ 1 $ and the set of all subsets of an $ n $-element set. It follows that the number of all subsets of an $ n $-element set is the same as the number of sequences with $ n $ terms, i.e., $ 2^n $ (see preparatory problem D, series III).

Consider in an $ n $-element set $ X $ the family of its subsets containing a fixed element $ a $. Any two subsets in this family have a non-empty intersection, as the element $ a $ belongs to it. The number of subsets in this family is equal to the number of all subsets of the $ (n-1) $-element set $ X - \{a\} $, which is $ 2^{n-1} $. Therefore, $ k(n) \geq 2^{n-1} $.

On the other hand, if a set $ A $ belongs to some family $ R $ of subsets of the set $ X $, in which any two subsets have a non-empty intersection, then the set $ X - A $ does not belong to $ R $. Therefore, the number of subsets belonging to the family $ R $ does not exceed half the number of all subsets of the set $ X $, i.e., $ k(n) \leq \frac{1}{2} \cdot 2^n = 2^{n-1} $.

From both proven inequalities, it follows that $ k(n) = 2^{n-1} $.