Maths Olympiad Prep

Library / /46 of 104

Combinatorics Difficulty 5.7 AIME, harder Prove it Bulgaria

Problem:
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.

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.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.