Problem:
For any set S, let ∣S∣ denote the number of elements in S, and let n(S) be the number of subsets of S, including the empty set and the set S itself. If A,B and C are sets for which
n(A)+n(B)+n(C)=n(A∪B∪C) and ∣A∣=∣B∣=100,
then what is the minimum possible value of ∣A∩B∩C∣?
Answer Choices:
A. 96
B. 97
C. 98
D. 99
E. 100
Solution:
If a set has k elements, then it has 2k subsets. Thus we are given
2100+2100+2∣C∣=2∣A∪B∪C∣, or 1+2∣C∣−101=2∣A∪B∪C∣−101
Since 1+2∣C∣−101 is larger than 1 and equal to an integral power of 2,∣C∣=101. Thus ∣A∪B∪C∣=102. The inclusion-exclusion formula for three sets is
∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣.
Fill in known quantities, use ∣X∩Y∣=∣X∣+∣Y∣−∣X∪Y∣ (obtained from the inclusion-exclusion formula for any two sets X and Y), and then again fill in known quantities to find
∣A∩B∩C∣=∣A∩B∣+∣A∩C∣+∣B∩C∣−199=(∣A∣+∣B∣−∣A∪B∣)+(∣A∣+∣C∣−∣A∪C∣)+(∣B∣+∣C∣−∣B∪C∣)−199=403−∣A∪B∣−∣A∪C∣−∣B∪C∣.
Since A∪B,A∪C,B∪C⊆A∪B∪C, we have ∣A∪B∣,∣A∪C∣,∣B∪C∣≤102. Thus
∣A∩B∩C∣=403−∣A∪B∣−∣A∪C∣−∣B∪C∣≥403−3⋅102=97.
The example
A={1,2,…,100},B={3,4,…,102},C={1,2,4,5,6,…,101,102} shows that ∣A∩B∩C∣=∣{4,5,6,…,100}∣=97 is possible.