2002 IMO Shortlist Problems/C5
Contents
[hide]Problem
(Brazil) Let be a fixed positive integer, and let be an infinite family of sets, each of size , no two of which are disjoint. Prove that there exists a set of size that meets each set in .
Solutions
Solution 1
We will show that if is a subset of infinitely many sets in , then either meets every element of , or there exists some such that is a subset of infinitely many sets in .
To prove this, suppose that there is some that is disjoint from . Since there are infinitely many sets in which contain and finitely many elements of , then there must exist such that infinitely many sets in which contain the elements of also contain . Then we may let .
Now, we may start with . We may then iterate this process, and we will stop before , for clearly no set of size can be a subset of every set of .
Solution 2
Lemma. If there is no set of size that meets each set in , then there exists some finite family of sets such that there is no set of size that meets each set in . To see this, we note that if is not a subset of some , then
Proof. Suppose satisfies the lemma's conditions. We will say that a set is characteristic of a finite collection if has at most elements, each set in has an element in common with , and . Since is finite, can only have finitely many characteristic sets.
Now, for every characteristic set with minimal cardinality, there exists some such that , or else any set of size of which was a subset would meet every element of . Now, if we let , then in changing to we have either increased the minimal cardinality of the characteristic sets, or decreased the number of characteristic sets with minimal cardinality, without changing that cardinality. Iterating this process, we will eventually arrive at some finite with no characteristic sets. ∎
Since is infinite, is infinite. It follows that for any finite , there exists some that contains an . Then has size and meets every element of . It then follows from the lemma that there must be some set of size which meets all the sets in .
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.