Problem:
Let be a set with six elements. In how many different ways can one select two not necessarily distinct subsets of so that the union of the two subsets is ? The order of selection does not matter; for example, the pair of subsets represents the same selection as the pair .
Solution:
In order that , for each element of exactly one of the following three statements is true:
Hence if has elements, there are ways to choose the sets and . Except for pairs with , this total counts each pair of sets twice. Since with occurs if and only if , the number of pairs of subsets of whose union is is
which is when .
Let be the set with elements and and be two subsets whose union is . If , then must contain the elements of not in . There are such sets . Each of the elements in may or may not be in , so for each set there are sets that can be paired with . Note that
counts each pair of sets twice, except the pair , which occurs once. Hence the number of pairs of subsets whose union is is . When , this gives .
The problems on this page are the property of the MAA's American Mathematics Competitions