MathDB

1

Part of 2014 Miklós Schweitzer

Problems(1)

Select a separating family

Source: Miklós Schweitzer 2014, problem 1

12/23/2014
Let nn be a positive integer. Let F\mathcal{F} be a family of sets that contains more than half of all subsets of an nn-element set XX. Prove that from F\mathcal{F} we can select ⌈log⁡2n⌉+1\lceil \log_2 n \rceil + 1 sets that form a separating family on XX, i.e., for any two distinct elements of XX there is a selected set containing exactly one of the two elements.
Moderator says: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=614827&hilit=Schweitzer+2014+separating
ceiling functionlogarithmscombinatorics unsolvedcombinatorics