Problem:
Let S be the set {1,2,3,…,10}. Let n be the number of sets of two non-empty disjoint subsets of S. (Disjoint sets are defined as sets that have no common elements.) Find the remainder obtained when n is divided by 1000.
Solution:
Let k be the number of elements of S, and let A and B be two empty jars into which elements of S will be placed to create two disjoint subsets. For each element x in S, there are three possibilities: place x in A, place x in B, or place x in neither A nor B. Thus the number of ordered pairs of disjoint subsets (A,B) is 3k. However, this counts the pairs where A or B is empty. Note that for A to be empty, there are two possibilities for each element x in S: place x in B, or do not place x in B. The number of pairs for which A or B is empty is thus 2k+2k−1=2k+1−1. Since interchanging A and B does not yield a different set of subsets, there are 21(3k−2k+1+1)=21(3k+1)−2k sets. When k=10,n=2310+1−210=28501, and the desired remainder is 501.
OR
For each non-empty subset X of S with k elements, k=1,2,3,…,9, there are 210−k−1 non-empty subsets of S that are disjoint with X. Let N be the total number of ordered pairs of non-empty disjoint subsets of S. Then
N=k=1∑9(k10)(210−k−1)=k=1∑9(k10)(2k−1)=k=1∑9(k10)2k−k=1∑9(k10)
Note that
k=0∑10(k10)=210
and, from the Binomial Expansion,
310=(1+2)10=k=0∑10(k10)2k
Thus N=[310−(1+210)]−[210−(1+1)]=310−211+1, and the number of sets of two non-empty disjoint subsets of S is 21(310−211+1)=28501.
The problems on this page are the property of the MAA's American Mathematics Competitions