MathNet 2017-part-02 — 176 problems (EN–VI) Question 161

Let $A_{1}, A_{2}, \ldots, A_{m}$ be distinct subsets of $\{1,2, \ldots, n\}$ such that for all $1 \leqslant i, j \leqslant m$ we have $A_{i} \cap A_{j} \neq \emptyset$. Show that $m \leqslant 2^{n-1}$.