Maths Olympiad Prep

Library / /494 of 520

Combinatorics Difficulty 4.4 AIME Find the answer

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

A number or a short expression. Spacing and $ signs are ignored.

Solution

Call the two subsets mm and n.n. For each of the elements in S,S, we can assign it to either m,n,m,n, or both. This gives us 363^6 possible methods of selection. However, because the order of the subsets does not matter, each possible selection is double counted, except the case where both mm and nn contain all 66 elements of S.S. So our final answer is then 3612+1=365.\frac {3^6 - 1}{2} + 1 = \boxed{365}.
Note: because we can order selections AA and BB in two ways, but since order does not matter in the problem, we should only count them once, ie we need to divide by two. We first need to subtract one for the count 3613^6-1 because there is one case in which AA and BB are identical and so while the rest of the “different” cases are counted twice, this one was only counted once so we should subtract one from the total count, divide by two, and add back that distinct one case. Or we could just add one, making all of the problem’s different cases counted twice, and divide it all by two, which is 36+12=365.\frac{3^6+1}{2}=365.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.