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