Maths Olympiad Prep

Library / USAMO /138 of 156

USAMO

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it United States

Let AA be a set with ∣A∣=225|A| = 225, meaning that AA has 225225 elements. Suppose further that there are eleven subsets A1,…,A11A_1, \dots, A_{11} of AA such that ∣Ai∣=45|A_i| = 45 for 1≤i≤111 \le i \le 11 and ∣Ai∩Aj∣=9|A_i \cap A_j| = 9 for 1≤i<j≤111 \le i < j \le 11. Prove that ∣A1∪A2∪⋯∪A11∣≥165|A_1 \cup A_2 \cup \dots \cup A_{11}| \ge 165, and give an example for which equality holds.

Solution

Let SS be the complement of A1∪A2∪⋯∪A11A_1 \cup A_2 \cup \dots \cup A_{11} in AA; we wish to prove that ∣S∣≤60|S| \le 60. For ℓ≥0\ell \ge 0, define
θ(ℓ)=(1−ℓ2)(1−ℓ3)=1−23ℓ+13(ℓ2). \theta(\ell) = \left(1 - \frac{\ell}{2}\right) \left(1 - \frac{\ell}{3}\right) = 1 - \frac{2}{3}\ell + \frac{1}{3}\binom{\ell}{2}.
Note that θ(0)=1\theta(0) = 1 and θ(ℓ)≥0\theta(\ell) \ge 0 for any integer ℓ>0\ell > 0. For n∈An \in A, let ℓ(n)\ell(n) be the number of sets among A1,…,A11A_1, \dots, A_{11} containing nn. Since SS is the intersection of the complements of the AiA_i, we see that
∣S∣≤∑n∈Aθ(ℓ(n)). |S| \le \sum_{n \in A} \theta(\ell(n)).
On the other hand, we have
∑n∈Aθ(ℓ(n))=∑n∈A(1−23ℓ(n)+13(ℓ(n)2))=∣A∣−23∑i∣Ai∣+13∑i<j∣Ai∩Aj∣. \sum_{n \in A} \theta(\ell(n)) = \sum_{n \in A} \left(1 - \frac{2}{3}\ell(n) + \frac{1}{3}\binom{\ell(n)}{2}\right) = |A| - \frac{2}{3}\sum_i |A_i| + \frac{1}{3}\sum_{i<j} |A_i \cap A_j|.
Putting these two equations together, we obtain
∣S∣≤225−23⋅11⋅45+13⋅(112)⋅9=60, |S| \le 225 - \frac{2}{3} \cdot 11 \cdot 45 + \frac{1}{3} \cdot \binom{11}{2} \cdot 9 = 60,
and therefore ∣A1∪A2∪⋯∪A11∣≥165|A_1 \cup A_2 \cup \dots \cup A_{11}| \ge 165.

It remains to give an example showing that this lower bound is best possible. Let p1,p2,…,p11p_1, p_2, \dots, p_{11} be a set of 1111 distinct primes, and let A′A' denote the set of all products of three of these primes. Let A′′={q1,q2,q3,…,q60}A'' = \{q_1, q_2, q_3, \dots, q_{60}\} be a set of 6060 distinct positive integers that are all coprime to p1,…,p11p_1, \dots, p_{11}. Set A=A′∪A′′A = A' \cup A'', and define
Ai={n∈A′:pi∣n}. A_i = \{n \in A' : p_i \mid n\}.
Then ∣Ai∣=(102)=45|A_i| = \binom{10}{2} = 45, ∣Ai∩Aj∣=(91)=9|A_i \cap A_j| = \binom{9}{1} = 9, and
∣A1∪A2∪⋯∪A11∣=∣A′∣=(113)=165. |A_1 \cup A_2 \cup \dots \cup A_{11}| = |A'| = \binom{11}{3} = 165.
Finally, ∣A∣=∣A′∣+∣A′′∣=165+60=225|A| = |A'| + |A''| = 165 + 60 = 225, so this AA and A1,…,A11A_1, \dots, A_{11} give a valid example.

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