Maths Olympiad Prep

Library / /175 of 397

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 Ai2|A_i| \ge 2 for all ii. Suppose that for any two-element subset SSS' \subseteq S, there exists a unique ii such that SAiS' \subseteq A_i. Prove that: AiAjA_i \cap A_j \ne \emptyset for any 1i<jn1 \le i < j \le n.

Solution

By the given conditions we obtain
i=1n(Ai2)=(n2).(1) \sum_{i=1}^{n} \binom{|A_i|}{2} = \binom{n}{2}. \qquad (1)
Let di={kiAk}d_i = |\{k \mid i \in A_k\}|. Clearly,
i=1ndi=k=1nAk.(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)=1i<jnAiAj. \sum_{i=1}^{n} \binom{d_i}{2} = \sum_{1 \le i < j \le n} |A_i \cap A_j|.
Also, AiAj1|A_i \cap A_j| \le 1 (otherwise the "uniqueness" property of the problem would be violated). To prove AiAjA_i \cap A_j \ne \emptyset is equivalent to proving AiAj=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)=(x2x)/2\binom{x}{2} = (x^2 - x)/2, the above equality is in turn equivalent to
i=1ndi2=k=1nAk2.(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 iAki \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 diAkd_i \ge |A_k|, and we also have
dindiAknAk. \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=1nkiAkdindii=1nkiAkAknAk=k=1niiAkAknAk=k=1nAk. \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=Akd_i = |A_k| when iAki \notin A_k. Next, consider the equality
i=1n(ndi)di=i=1nkiAkdi=i=1nkiAkAk=k=1niiAkAk=k=1n(nAk)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,000 problems in a working order, from AMC 10 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.