2002 IMO Shortlist Problems/C5

Problem

(Brazil) Let $r \ge 2$ be a fixed positive integer, and let $\displaystyle F$ be an infinite family of sets, each of size $\displaystyle r$ , no two of which are disjoint. Prove that there exists a set of size $\displaystyle r-1$ that meets each set in $\displaystyle F$ .

Solutions

Solution 1

We will show that if $\displaystyle A$ is a subset of infinitely many sets in $\displaystyle F$ , then either $\displaystyle A$ meets every element of $\displaystyle F$ , or there exists some $x \notin A$ such that $A \cup \{x\}$ is a subset of infinitely many sets in $\displaystyle F$ .

To prove this, suppose that there is some $S \in F$ that is disjoint from $\displaystyle A$ . Since there are infinitely many sets in $\displaystyle F$ which contain $\displaystyle A$ and finitely many elements of $\displaystyle S$ , then there must exist $\displaystyle s \in S$ such that infinitely many sets in $\displaystyle F$ which contain the elements of $\displaystyle A$ also contain $\displaystyle s$ . Then we may let $\displaystyle s = x$ .

Now, we may start with $A = \varnothing$ . We may then iterate this process, and we will stop before $\displaystyle |A| = r$ , for clearly no set of size $\displaystyle r$ can be a subset of every set of $\displaystyle T$ .

Solution 2

Lemma. If there is no set of size $\displaystyle r-1$ that meets each set in $\displaystyle F$ , then there exists some finite family of sets $S \subset F$ such that there is no set of size $\displaystyle r-1$ that meets each set in $\displaystyle S$ . To see this, we note that if $\displaystyle A$ is not a subset of some $S \in F$ , then

Proof. Suppose $\displaystyle F$ satisfies the lemma's conditions. We will say that a set $\displaystyle A$ is characteristic of a finite collection $\displaystyle S_{0} \subset F$ if $\displaystyle A$ has at most $\displaystyle r-1$ elements, each set in $\displaystyle S_{0}$ has an element in common with $\displaystyle A$ , and $A \subseteq \bigcup_{X\in S_0} X$ . Since $\bigcup_{X\in S_0} X$ is finite, $\displaystyle S_{0}$ can only have finitely many characteristic sets.

Now, for every characteristic set $\displaystyle A$ with minimal cardinality, there exists some $\displaystyle B \in F$ such that $A \cap B = \varnothing$ , or else any set of size $\displaystyle r-1$ of which $\displaystyle A$ was a subset would meet every element of $\displaystyle F$ . Now, if we let $\displaystyle S_1 = \{B\} \cup S_0$ , then in changing $\displaystyle S_{0}$ to $\displaystyle S_{1}$ 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 $S_n \subset F$ with no characteristic sets. ∎

Since $\displaystyle F$ is infinite, $\bigcup_{X\in F} X$ is infinite. It follows that for any finite $S \subset F$ , there exists some $T \in F$ that contains an $x \notin \bigcup_{X \in S}$ . Then $T \setminus \{x\}$ has size $\displaystyle r-1$ and meets every element of $\displaystyle S$ . It then follows from the lemma that there must be some set of size $\displaystyle r-1$ which meets all the sets in $\displaystyle F$ .