HMMT February

Combinatorics Difficulty 5.1 AIME, harder Find the answer

For each positive integer $n$ let $S_{n}$ denote the set $\{1,2,3, \ldots, n\}$ . Compute the number of triples of subsets $A, B, C$ of $S_{2006}$ (not necessarily nonempty or proper) such that $A$ is a subset of $B$ and $S_{2006}-A$ is a subset of $C$ .

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let $A_{o}, B_{o}, C_{o}$ be sets satisfying the said conditions. Note that $1 \in A_{o}$ implies that $1 \in B_{o}$ and $1 \notin S_{2006}-A_{o}$ so that 1 may or may not be in $C_{o}$ . Also, $1 \notin A_{o}$ implies that $1 \in S_{2006}-A_{o} \subset C_{o}$ while 1 may or may not be in $B_{o}$ . Thus there are four possibilities for the distribution of 1, and since the same argument holds independently for $2,3, \ldots, 2006$ , the answer is $4^{2006}$ or $2^{4012}$ .

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.