Given two positive integers $r > s$, and let $F$ be an infinite family of sets, each of size $r$, no two of which share fewer than $s$ elements. Prove that there exists a set of size $r -1$ that shares at least $s$ elements with each set in $F$.
Problem
Source: 2016 Saudi Arabia IMO TST , level 4+, II p3
Tags: combinatorics, set, Subsets
19.05.2022 03:47
Call a set $S$ $dense$ if the subfamily $F_{S}=\{A\in F\;|\;S\subseteq A\}$ is infinite. Notice that dense sets exist, and to see this, fix an $A\in F,$ it only has $\binom{r}{s}$ subsets of cardinality $s,$ so by Peginhole Principle, one them is contained in infinitely many sets of $F.$ Moreover, a dense set can have no more than $r-1$ elements (because all sets of $F$ are of size $r$ and they are distinct). Now let $S$ be a dense set with $|S|=k$ is maximal, then $s\le k<r,$ we shall prove that $F_{S}=F.$ Suppose on contrary that $F_{S}\neq F$ and pick an $A\not\in F_{S}.$ Since $|A\cap B|\ge s$ for every $B\in F_{S}$ and $S\not \subseteq A\cap B,$ the intersection has an element not in $S,$ this element is in $A,$ so it has finitely many choices, then by Pegionhole Principle, we can pick such an $a\in A$ that is contained in infinitely many sets of $F_{S},$ so the subfamily $F_{S\cup \{a\}}$ is infinite, contradicting the maximality of $S.$ Hence, $F_{S}=F,$ in particular, $S\subseteq A\;\forall \;A\in F,$ so we simply add elements to $S$ until we achieve a set $T$ of size $r-1$, this set shares at least $k\ge s$ elements with each set in $F,$ concluding the proof. $Remark.$ Notice that we proved a stronger result, that there is a set of size $\ge s$ contained in all sets of $F.$