Maths Olympiad Prep

Track / Stage 5 / 284 of 400 #1364 of 2444

Problem 1364

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
AiAi+1>n2n1Ai+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+1A1A_{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 AiAi+1=BiA_{i} \cap A_{i+1} = B_{i}, i=1,2,,ni=1,2, \ldots, n. Since AnBn1BnA_{n} \supset B_{n-1} \cup B_{n}, then
AnBn1Bn=Bn1+BnBn1Bn>n2n1An+n2n1A1Bn1Bn \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
Bn1Bn>n2n1A11n1Ann3n1A1 \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., An1AnA1>n3n1A1\left|A_{n-1} \cap A_{n} \cap A_{1}\right| > \frac{n-3}{n-1}\left|A_{1}\right|. Further, if C=An1AnA1C = A_{n-1} \cap A_{n} \cap A_{1}, then An1CBn2A_{n-1} \supset C \cup B_{n-2} and
An1Bn2C=Bn2+CBn2C>n2n1An1+n3n1A1Bn2C \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 Bn2C>n3n1A11n1An1n4n1A1\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.
An2An1AnA1>n4n1A1 \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
AnkAnk+1An1AnA1>nk2n1A1 \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,,n2k=1,2, \ldots, n-2. In particular, A2A3An1AnA1>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.