Problem:
Given are two-element subsets of the set . Prove that one can select of these subsets whose union contains no more than elements.
(Dušan Đukić)
Problem:
Given are two-element subsets of the set . Prove that one can select of these subsets whose union contains no more than elements.
(Dušan Đukić)
Solution:
We shall show by induction on that one can discard of the subsets so that the cardinality of the union of the remaining ones is no greater than .
For this is trivial. Suppose that and that we have discarded subsets so that the union of the remaining ones contains no more than elements. Since , there exists an element 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 subsets does not contain the element , which completes the induction step.
The assertion of the problem follows for , since .