Maths Olympiad Prep

Library / Saudi Arabian Mathematical Competitions /226 of 395

Saudi Arabian Mathematical Competitions

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 r−1r-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) r−1r-1 exists. (Each S∈FS \in \mathscr{F} s-meets F\mathscr{F} by the problem hypothesis.)

Let TT be a maximal set such that T⊆ST \subseteq S for infinitely many S∈FS \in \mathscr{F}, which form F′⊆F\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 U∈FU \in \mathscr{F} with ∣U∩T∣≤s−1|U \cap T| \leq s-1.

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

Remark. Let XX be an infinite set, and a1,a2,…,a2r−2−sa_1, a_2, \ldots, a_{2r-2-s} elements not in XX. Then the set
F={B∪{x}:B⊆{a1,a2,…,a2r−2−s},∣B∣=r−1,x∈X} \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 r−1r-1 with any smaller number.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.