Competition problem — Combinatorics

Library / /360 of 860

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. Spacing and $ signs are ignored.

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,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.