Problem:
For any finite set , let denote the number of elements in . Find the number of ordered pairs such that and are (not necessarily distinct) subsets of that satisfy
Solution:
Answer (454):
For any finite sets and , the Inclusion-Exclusion Principle states that . If and also satisfy , then the two numbers and have the same sum and the same product as the two numbers and . Because knowing the sum and product of a pair of numbers determines the pair of numbers, the given condition is satisfied exactly when . This occurs exactly when either or .\
First find the number of pairs with . Such a pair can be chosen by considering each element of , and either putting that element in both and , putting the element in only, or putting the element in neither nor . Because there are 3 choices for each of the 5 elements, there are pairs of and with . Similarly, there are pairs with . There are pairs with . Therefore the requested number of ordered pairs is .
The problems and solutions on this page are the property of the MAA's American Mathematics Competitions