Maths Olympiad Prep

Library / Taiwan IMO Selection Camp /161 of 359

Taiwan IMO Selection Camp

Combinatorics Difficulty 5.7 AIME, harder Prove it Taiwan

Let nn be some integer greater than 3, and let S={1,2,…,n}S = \{1, 2, \dots, n\}. Let A1,A2,…,AnA_1, A_2, \dots, A_n be subsets of SS, where ∣Ai∣≥2|A_i| \ge 2 for all ii. Suppose that for any two-element subset S′⊆SS' \subseteq S, there exists a unique ii such that S′⊆AiS' \subseteq A_i. Prove that: Ai∩Aj≠∅A_i \cap A_j \ne \emptyset for any 1≤i<j≤n1 \le i < j \le n.

Solution

By the given conditions we obtain
∑i=1n(∣Ai∣2)=(n2).(1) \sum_{i=1}^{n} \binom{|A_i|}{2} = \binom{n}{2}. \qquad (1)
Let di=∣{k∣i∈Ak}∣d_i = |\{k \mid i \in A_k\}|. Clearly,
∑i=1ndi=∑k=1n∣Ak∣.(2) \sum_{i=1}^{n} d_i = \sum_{k=1}^{n} |A_k|. \qquad (2)
From the "existence and uniqueness" property, we obtain
∑i=1n(di2)=∑1≤i<j≤n∣Ai∩Aj∣. \sum_{i=1}^{n} \binom{d_i}{2} = \sum_{1 \le i < j \le n} |A_i \cap A_j|.
Also, ∣Ai∩Aj∣≤1|A_i \cap A_j| \le 1 (otherwise the "uniqueness" property of the problem would be violated). To prove Ai∩Aj≠∅A_i \cap A_j \ne \emptyset is equivalent to proving ∣Ai∩Aj∣=1|A_i \cap A_j| = 1, which is equivalent to
∑i=1n(di2)=(n2). \sum_{i=1}^{n} \binom{d_i}{2} = \binom{n}{2}.
By (1) and (2), together with the definition of the binomial coefficient (x2)=(x2−x)/2\binom{x}{2} = (x^2 - x)/2, the above equality is in turn equivalent to
∑i=1ndi2=∑k=1n∣Ak∣2.(3) \sum_{i=1}^{n} d_i^2 = \sum_{k=1}^{n} |A_k|^2. \qquad (3)
Next, consider ordered pairs (i,k)(i, k) where i∉Aki \notin A_k. Suppose Ak={j1,j2,…,jt}A_k = \{j_1, j_2, \dots, j_t\}, then {i,y1},{i,y2},…,{i,yt}\{i, y_1\}, \{i, y_2\}, \dots, \{i, y_t\} are tt distinct two-element subsets of some AjA_j (since the two-element set {ya,yb}\{y_a, y_b\} is uniquely contained in AkA_k), so di≥∣Ak∣d_i \ge |A_k|, and we also have
din−di≥∣Ak∣n−∣Ak∣. \frac{d_i}{n - d_i} \ge \frac{|A_k|}{n - |A_k|}.

Summing the above inequality over all required (i,k)(i, k), we obtain
∑i=1ndi=∑i=1n∑k∣i∉Akdin−di≥∑i=1n∑k∣i∉Ak∣Ak∣n−∣Ak∣=∑k=1n∑i∣i∉Ak∣Ak∣n−∣Ak∣=∑k=1n∣Ak∣. \begin{aligned} \sum_{i=1}^{n} d_i &= \sum_{i=1}^{n} \sum_{k|i \notin A_k} \frac{d_i}{n - d_i} \\ &\geq \sum_{i=1}^{n} \sum_{k|i \notin A_k} \frac{|A_k|}{n - |A_k|} \\ &= \sum_{k=1}^{n} \sum_{i|i \notin A_k} \frac{|A_k|}{n - |A_k|} \\ &= \sum_{k=1}^{n} |A_k|. \end{aligned}
By equality (2), the above must be an equality, and finally we get di=∣Ak∣d_i = |A_k| when i∉Aki \notin A_k. Next, consider the equality
∑i=1n(n−di)di=∑i=1n∑k∣i∉Akdi=∑i=1n∑k∣i∉Ak∣Ak∣=∑k=1n∑i∣i∉Ak∣Ak∣=∑k=1n(n−∣Ak∣)∣Ak∣. \begin{aligned} \sum_{i=1}^{n} (n - d_i) d_i &= \sum_{i=1}^{n} \sum_{k|i \notin A_k} d_i \\ &= \sum_{i=1}^{n} \sum_{k|i \notin A_k} |A_k| \\ &= \sum_{k=1}^{n} \sum_{i|i \notin A_k} |A_k| \\ &= \sum_{k=1}^{n} (n - |A_k|) |A_k|. \end{aligned}
Combined with equality (2), this yields (3). This completes the proof!

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 translated into English from zh; metadata (topic, difficulty) added by this project.