IMO 2002 SL C5

Origin: BRA | Category: Combinatorics

Problem

Let r \geq2 be a fixed positive integer, and let F be an infinite family of sets, each of size r, no two of which are disjoint. Prove that there exists a set of size r −1 that meets each set in F.

Solution

Assume to the contrary that no set of size less than r meets all sets in F. Consider any set A of size less than r that is contained in infinitely many sets of F. By the assumption, A is disjoint from some set B \inF. Then of the infinitely many sets that contain A, each must meet B, so some element b of B belongs to infinitely many of them. But then the set A\cup{b} is contained in infinitely many sets of F as well. Such a set A exists: for example, the empty set. Now taking for A the largest such set we come to a contradiction.