Maths Olympiad Prep

Library / HMMT February /519 of 1302

HMMT February

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. Fractions can be typed as 3/2, and spacing doesn't matter.

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 42017−2⋅32017+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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.