Problem:
Let A be a set with ∣A∣=225, meaning that A has 225 elements. Suppose further that there are eleven subsets A1​,…,A11​ of A such that ∣Ai​∣=45 for 1≤i≤11 and ∣Ai​∩Aj​∣=9 for 1≤i<j≤11. Prove that ∣A1​∪A2​∪⋯∪A11​∣≥165, and give an example for which equality holds.
Solution:
Let S be the complement of A1​∪A2​∪⋯∪A11​ in A; we wish to prove that ∣S∣≤60. For ℓ≥0, define
θ(ℓ)=(1−2ℓ​)(1−3ℓ​)=1−32​ℓ+31​(2ℓ​)
Note that θ(0)=1 and θ(ℓ)≥0 for any integer ℓ>0. Therefore, since S is the intersection of the complements of the Ai​,
∣S∣≤n∈A∑​θ(ℓ(n))
On the other hand,
n∈A∑​θ(ℓ(n))=n∈A∑​(1−32​ℓ(n)+31​(2ℓ(n)​))=∣A∣−32​i∑​∣Ai​∣+31​i<j∑​∣Ai​∩Aj​∣
Consequently,
∣S∣≤225−32​⋅11⋅45+31​⋅(211​)⋅5=60
and therefore ∣A1​∪A2​∪⋯∪A11​∣≥165.
We construct an example to show that this lower bound is best possible. Let p1​,p2​,…,p11​ be a set of 11 distinct primes, and let A′ denote the set of all products of three of these primes. Furthermore, let
A′′={q1​,q2​,q3​,…,q60​}
be a set of 60 distinct positive integers that are all prime to p1​,…,p11​. Set A=A′∪A′′, and define
Ai​={n∈A′:pi​∣n}
Then ∣Ai​∣=(210​)=45,∣Ai​∩Aj​∣=(19​)=9, and
∣A1​∪A2​∪⋯∪A11​∣=∣A′∣=(311​)=165
Finally, ∣A∣=∣A′∣+∣A′′∣=165+60=225.
Remark: To get an upper bound for ∣S∣, one could replace θ(ℓ) by any function of the form
(1−rℓ​)(1−r+1ℓ​)
for any positive integer r. The choice r=2 is optimal for the stated problem. The choice r=1 yields
∣S∣≤∣A∣−i∑​∣Ai​∣+i<j∑​∣Ai​∩Aj​∣
which is a familiar truncated inclusion-exclusion inequality, known in number theory as "Brun's Pure Sieve" and in probability as "Bonferroni's Inequality."
The problems on this page are the property of the MAA's American Mathematics Competitions