Problem A. 637. (February 2015)
A. 637. Let \(\displaystyle n\) be a positive integer. Let \(\displaystyle \mathcal{F}\) be a family of sets that contains more than half of all subsets of an \(\displaystyle n\)-element set \(\displaystyle X\). Prove that from \(\displaystyle \mathcal{F}\) we can select \(\displaystyle \lceil\log_2n\rceil+1\) sets that form a separating family on \(\displaystyle X\), i.e., for any two distinct elements of \(\displaystyle X\) there is a selected set containing exactly one of the two elements.
Miklós Schweitzer competition, 2014
(5 pont)
Deadline expired on March 10, 2015.
Statistics:
0 student sent a solution.
Problems in Mathematics of KöMaL, February 2015