Maths Olympiad Prep

Library / /7 of 87

Combinatorics Difficulty 5.1 AIME, harder Prove it Serbia

Problem:

Given are 2n12n-1 two-element subsets of the set {1,2,,n}\{1,2, \ldots, n\}. Prove that one can select nn of these subsets whose union contains no more than 23n+1\frac{2}{3}n+1 elements.

(Dušan Đukić)

Solution

Solution:

We shall show by induction on k(k2n13)k\left(k \leqslant \frac{2n-1}{3}\right) that one can discard 3k3k of the subsets so that the cardinality of the union of the remaining ones is no greater than nkn-k.

For k=0k=0 this is trivial. Suppose that k1k \geqslant 1 and that we have discarded 3(k1)3(k-1) subsets so that the union of the remaining ones contains no more than nk+1n-k+1 elements. Since 2n13(k1)<2(nk+1)2n-1-3(k-1)<2(n-k+1), there exists an element xkx_{k} of the union which lies in at most three of the remaining subsets. Thus we can discard three more subsets so that the union of the remaining 2n13k2n-1-3k subsets does not contain the element xkx_{k}, which completes the induction step.

The assertion of the problem follows for k=[n13]k=\left[\frac{n-1}{3}\right], since n[n13]nn33=23n+1n-\left[\frac{n-1}{3}\right] \leqslant n-\frac{n-3}{3}=\frac{2}{3}n+1.

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: MathNet, licensed CC-BY-4.0. Statement translated into English from sr; metadata (topic, difficulty) added by this project.