Maths Olympiad Prep

Library / /150 of 169

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 1i111 \le i \le 11 and AiAj=9|A_i \cap A_j| = 9 for 1i<j111 \le i < j \le 11. Prove that A1A2A11165|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 A1A2A11A_1 \cup A_2 \cup \dots \cup A_{11} in AA; we wish to prove that S60|S| \le 60. For 0\ell \ge 0, define
θ()=(12)(13)=123+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 nAn \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
SnAθ((n)). |S| \le \sum_{n \in A} \theta(\ell(n)).
On the other hand, we have
nAθ((n))=nA(123(n)+13((n)2))=A23iAi+13i<jAiAj. \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
S225231145+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 A1A2A11165|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 AA' 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=AAA = A' \cup A'', and define
Ai={nA:pin}. A_i = \{n \in A' : p_i \mid n\}.
Then Ai=(102)=45|A_i| = \binom{10}{2} = 45, AiAj=(91)=9|A_i \cap A_j| = \binom{9}{1} = 9, and
A1A2A11=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,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.