Problem:
Let N be the number of ordered pairs of nonempty sets A and B that have the following properties:
- A∪B={1,2,3,4,5,6,7,8,9,10,11,12},
- A∩B=∅,
- The number of elements of A is not an element of A,
- The number of elements of B is not an element of B. Find N.
Solution:
Let ∣M∣ represent the number of elements in the set M.
Let ∣A∣=k. Then the first two properties imply that ∣B∣=12−k, and because A and B are nonempty, it follows that kî€ =0 and kî€ =12. The last two properties imply that k∈/A and 12−k∈/B. Thus the first property implies that k∈B and 12−k∈A. Furthermore, k cannot equal 6, because otherwise, ∣A∣=∣B∣=6. Thus 6∈A∩B, which violates the second property. After assigning k to B and 12−k to A, the remaining k−1 elements of A can be chosen in (k−110​) ways, and the remaining 11−k elements must belong to set B.
Thus
N=(k=1∑11​(k−110​))−(k−110​)=210−252=772
and the answer is 772​ .
The problems on this page are the property of the MAA's American Mathematics Competitions