HMMT-Feb 2017 guts, Problem 7

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

Solution: Firstly, there are $4^{2017}$ possible pairs of subsets, as each of the 2017 elements can be in neither subset, in $A$ only, in $B$ only, or in both. Now let us count the number of pairs of subsets for which $A$ is a subset of $B$. Under these conditions, each of the 2017 elements could be in neither subset, in $B$ only, or in both $A$ and $B$. So there are $3^{2017}$ such pairs. By symmetry, there are also $3^{2017}$ pairs of subsets where $B$ is a subset of $A$. But this overcounts the pairs in which $A$ is a subset of $B$ and $B$ is a subset of $A$, i.e. $A=B$. There are $2^{2017}$ such subsets. Thus, in total, there are $4^{2017}-2 \cdot 3^{2017}+2^{2017}$ good pairs of subsets. $\fbox{4^{2017}-2 \cdot 3^{2017}+2^{2017}}$.

Answer: 4^{2017}-2 \cdot 3^{2017}+2^{2017}