An ordered pair of sets is good if is not a subset of and is not a subset of . How many ordered pairs of subsets of are good?
Solution
Firstly, there are possible pairs of subsets, as each of the 2017 elements can be in neither subset, in only, in only, or in both. Now let us count the number of pairs of subsets for which is a subset of . Under these conditions, each of the 2017 elements could be in neither subset, in only, or in both and . So there are such pairs. By symmetry, there are also pairs of subsets where is a subset of . But this overcounts the pairs in which is a subset of and is a subset of , i.e. . There are such subsets. Thus, in total, there are good pairs of subsets.
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.