Maths Olympiad Prep

Library / /291 of 520

Combinatorics Difficulty 7.0 National olympiad, round 2 Prove it

There are 2n12n-1 twoelement subsets of set 1,2,...,n1,2,...,n. Prove that one can choose nn out of these such that their union contains no more than 23n+1\frac{2}{3}n+1 elements.

Solution

1. Lemma: We start by proving the lemma:
(2nn)=2n135(2n1)n!23n1 \binom{2n}{n} = 2^n \cdot \frac{1 \cdot 3 \cdot 5 \cdots (2n-1)}{n!} \ge 2 \cdot 3^{n-1}
Proof: The proof of this lemma can be found here. For the second part, note that 2k1>32k2k-1 > \frac{3}{2}k for k>1k > 1. This inequality can be used to show that the product of odd numbers up to 2n12n-1 is greater than a certain bound.

2. Problem Setup: Let xix_i (for 1in1 \le i \le n) be the number of two-element sets among the 2n12n-1 sets that ii belongs to. Note that xin1x_i \le n-1.

3. Random Selection and Probability Calculation: Pick nn sets randomly from the 2n12n-1 sets. The probability that a particular element ii is in at least one of the chosen sets is:
P(Xi)=j=1n(xij)(2n1n)2n11(2n1n) \mathbb{P}(X_i) = \frac{\sum_{j=1}^n \binom{x_i}{j}}{\binom{2n-1}{n}} \le \frac{2^{n-1} - 1}{\binom{2n-1}{n}}
Here, Xi=1X_i = 1 if ii belongs to at least one of the chosen sets, and Xi=0X_i = 0 otherwise.

4. Expected Number of Elements in the Union: The expected number of elements in the union of nn sets is:
E[X]n(2n11)(2n1n) \mathbb{E}[X] \le \frac{n(2^{n-1} - 1)}{\binom{2n-1}{n}}

5. Inequality and Bound Calculation: It suffices to prove that:
2n11<(2n1n)k 2^{n-1} - 1 < \binom{2n-1}{n} \cdot k
for the best kk possible. This is equivalent to:
2n2<(2nn)k 2^n - 2 < \binom{2n}{n} \cdot k
Using the lemma, we have:
(2nn)23n1 \binom{2n}{n} \ge 2 \cdot 3^{n-1}
Therefore, we need:
2n2<23n1k 2^n - 2 < 2 \cdot 3^{n-1} \cdot k
Solving for kk, we find that k=23k = \frac{2}{3} is sufficient. Thus:
E[X]23n \mathbb{E}[X] \le \frac{2}{3}n
This means there exists nn subsets such that their union has at most 23n\frac{2}{3}n elements.

6. Conclusion: Therefore, we have shown that one can choose nn out of the 2n12n-1 two-element subsets such that their union contains no more than 23n+1\frac{2}{3}n + 1 elements.

\blacksquare

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.