Maths Olympiad Prep

Library / /448 of 860

Combinatorics Difficulty 5.2 AIME, harder Find the answer

An ordered pair of sets (A,B)(A, B) is good if AA is not a subset of BB and BB is not a subset of AA. How many ordered pairs of subsets of {1,2,,2017}\{1,2, \ldots, 2017\} are good?

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

Solution

Firstly, there are 420174^{2017} possible pairs of subsets, as each of the 2017 elements can be in neither subset, in AA only, in BB only, or in both. Now let us count the number of pairs of subsets for which AA is a subset of BB. Under these conditions, each of the 2017 elements could be in neither subset, in BB only, or in both AA and BB. So there are 320173^{2017} such pairs. By symmetry, there are also 320173^{2017} pairs of subsets where BB is a subset of AA. But this overcounts the pairs in which AA is a subset of BB and BB is a subset of AA, i.e. A=BA=B. There are 220172^{2017} such subsets. Thus, in total, there are 42017232017+220174^{2017}-2 \cdot 3^{2017}+2^{2017} 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.

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