Maths Olympiad Prep

Library / /62 of 155

Combinatorics Difficulty 5.8 AIME, harder Prove it Saudi Arabia

Given two positive integers r>sr > s, and let F\mathscr{F} be an infinite family of sets, each of size rr, no two of which share fewer than ss elements. Prove that there exists a set of size r1r-1 that shares at least ss elements with each set in F\mathscr{F}.

Solution

We call a set SS s-meets F\mathscr{F} if it shares at least ss elements with each set in F\mathscr{F}. Suppose no such set of size (at most) r1r-1 exists. (Each SFS \in \mathscr{F} s-meets F\mathscr{F} by the problem hypothesis.)

Let TT be a maximal set such that TST \subseteq S for infinitely many SFS \in \mathscr{F}, which form FF\mathscr{F}' \subseteq \mathscr{F} (such TT exists, since the empty set works).

Clearly T<r|T| < r, so by assumption, TT does not s-meet F\mathscr{F}, and there exists UFU \in \mathscr{F} with UTs1|U \cap T| \leq s-1.

But UU s-meets F\mathscr{F}', so by pigeonhole, there must exist uUTu \in U \setminus T belonging to infinitely many SFS \in \mathscr{F}', contradicting the maximality of TT.

Remark. Let XX be an infinite set, and a1,a2,,a2r2sa_1, a_2, \ldots, a_{2r-2-s} elements not in XX. Then the set
F={B{x}:B{a1,a2,,a2r2s},B=r1,xX} \mathscr{F} = \left\{ B \cup \{x\} : B \subseteq \{a_1, a_2, \ldots, a_{2r-2-s}\}, |B| = r-1, x \in X \right\}
shows we cannot replace r1r-1 with any smaller number.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.