, 2015

Let $n$ be a positive integer. Let $\mathcal{F}$ be a family of sets that contains more than half of all subsets of an $n$-element set $X$. Prove that from $\mathcal{F}$ we can select $\lceil\log_2n\rceil+1$ sets that form a separating family on $X$, i.e., for any two distinct elements of $X$ there is a selected set containing exactly one of the two elements.
Miklós Schweitzer competition, 2014
(5 pont)