Question

Let $S$ be a set with six elements. In how many different ways can one select two not necessarily distinct subsets of $S$ so that the union of the two subsets is $S?$ The order of selection does not matter; for example, the pair of subsets $\{a,c\},$ $\{b,c,d,e,f\}$ represents the same selection as the pair $\{b,c,d,e,f\},$ $\{a,c\}.$

Answer

Answer: 365

Concepts:Burnside’s Lemma multiplication principle subsets

Difficulty rating: 1930

Small Hint:

For an ordered pair, each element can lie in the first subset only, the second only, or both

Big Hint:

When the two subsets are swapped, identify the one ordered pair that remains fixed

Solution:

For an ordered pair $(A,B)$ with $A\cup B=S,$ each element has three possible memberships: $A$ only, $B$ only, or both. This gives $3^6=729$ ordered pairs. Swapping $A$ and $B$ fixes only the pair $A=B=S.$ Therefore the number of unordered pairs is $\frac{729+1}{2}=365.$

1993 AIME Problem 8

Answer: 365

Difficulty rating: 1930

Small Hint:

Big Hint:

Solution:

Problem 8 in Other Years