There are twoelement subsets of set . Prove that one can choose out of these such that their union contains no more than elements.
Solution
1. Lemma: We start by proving the lemma:
Proof: The proof of this lemma can be found here. For the second part, note that for . This inequality can be used to show that the product of odd numbers up to is greater than a certain bound.
2. Problem Setup: Let (for ) be the number of two-element sets among the sets that belongs to. Note that .
3. Random Selection and Probability Calculation: Pick sets randomly from the sets. The probability that a particular element is in at least one of the chosen sets is:
Here, if belongs to at least one of the chosen sets, and otherwise.
4. Expected Number of Elements in the Union: The expected number of elements in the union of sets is:
5. Inequality and Bound Calculation: It suffices to prove that:
for the best possible. This is equivalent to:
Using the lemma, we have:
Therefore, we need:
Solving for , we find that is sufficient. Thus:
This means there exists subsets such that their union has at most elements.
6. Conclusion: Therefore, we have shown that one can choose out of the two-element subsets such that their union contains no more than elements.