Maths Olympiad Prep

Track / Stage 5 / 284 of 400 #1524 of 2604

Problem 1524

AIME late
Combinatorics Difficulty 5.7 Prove it Bulgarian Mathematical Competitions · Bulgaria

Let A1,A2,…,AnA_{1}, A_{2}, \ldots, A_{n} be finite sets such that
∣Ai∩Ai+1∣>n−2n−1∣Ai+1∣ \left|A_{i} \cap A_{i+1}\right|>\frac{n-2}{n-1}\left|A_{i+1}\right|
for any i=1,2,…,ni=1,2, \ldots, n (An+1≡A1A_{n+1} \equiv A_{1}). Prove that their intersection is a nonempty set.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

Solution:
We may assume the set A1A_{1} has maximal cardinality. Denote Ai∩Ai+1=BiA_{i} \cap A_{i+1} = B_{i}, i=1,2,…,ni=1,2, \ldots, n. Since An⊃Bn−1∪BnA_{n} \supset B_{n-1} \cup B_{n}, then
∣An∣≥∣Bn−1∪Bn∣=∣Bn−1∣+∣Bn∣−∣Bn−1∩Bn∣>n−2n−1∣An∣+n−2n−1∣A1∣−∣Bn−1∩Bn∣ \begin{aligned} \left|A_{n}\right| & \geq \left|B_{n-1} \cup B_{n}\right| = \left|B_{n-1}\right| + \left|B_{n}\right| - \left|B_{n-1} \cap B_{n}\right| \\ & > \frac{n-2}{n-1}\left|A_{n}\right| + \frac{n-2}{n-1}\left|A_{1}\right| - \left|B_{n-1} \cap B_{n}\right| \end{aligned}
Hence
∣Bn−1∩Bn∣>n−2n−1∣A1∣−1n−1∣An∣≥n−3n−1∣A1∣ \left|B_{n-1} \cap B_{n}\right| > \frac{n-2}{n-1}\left|A_{1}\right| - \frac{1}{n-1}\left|A_{n}\right| \geq \frac{n-3}{n-1}\left|A_{1}\right|
i.e., ∣An−1∩An∩A1∣>n−3n−1∣A1∣\left|A_{n-1} \cap A_{n} \cap A_{1}\right| > \frac{n-3}{n-1}\left|A_{1}\right|. Further, if C=An−1∩An∩A1C = A_{n-1} \cap A_{n} \cap A_{1}, then An−1⊃C∪Bn−2A_{n-1} \supset C \cup B_{n-2} and
∣An−1∣≥∣Bn−2∪C∣=∣Bn−2∣+∣C∣−∣Bn−2∩C∣>n−2n−1∣An−1∣+n−3n−1∣A1∣−∣Bn−2∩C∣ \begin{aligned} \left|A_{n-1}\right| & \geq \left|B_{n-2} \cup C\right| = \left|B_{n-2}\right| + |C| - \left|B_{n-2} \cap C\right| \\ & > \frac{n-2}{n-1}\left|A_{n-1}\right| + \frac{n-3}{n-1}\left|A_{1}\right| - \left|B_{n-2} \cap C\right| \end{aligned}
So ∣Bn−2∩C∣>n−3n−1∣A1∣−1n−1∣An−1∣≥n−4n−1∣A1∣\left|B_{n-2} \cap C\right| > \frac{n-3}{n-1}\left|A_{1}\right| - \frac{1}{n-1}\left|A_{n-1}\right| \geq \frac{n-4}{n-1}\left|A_{1}\right|, i.e.
∣An−2∩An−1∩An∩A1∣>n−4n−1∣A1∣ \left|A_{n-2} \cap A_{n-1} \cap A_{n} \cap A_{1}\right| > \frac{n-4}{n-1}\left|A_{1}\right|
We get by induction that
∣An−k∩An−k+1∩⋯∩An−1∩An∩A1∣>n−k−2n−1∣A1∣ \left|A_{n-k} \cap A_{n-k+1} \cap \cdots \cap A_{n-1} \cap A_{n} \cap A_{1}\right| > \frac{n-k-2}{n-1}\left|A_{1}\right|
for k=1,2,…,n−2k=1,2, \ldots, n-2. In particular, ∣A2∩A3∩⋯∩An−1∩An∩A1∣>0\left|A_{2} \cap A_{3} \cap \cdots \cap A_{n-1} \cap A_{n} \cap A_{1}\right| > 0.

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