Northeastern WOOTers Mock AIME I Problems/Problem 6

Problem 6

Let $\mathcal{S}=\{1,...,10\}$. Two subsets, $A$ and $B$, of $S$ are chosen randomly with replacement, with $B$ chosen after $A$. The probability that $A$ is a subset of $B$ can be written as $\frac {p^a}{q^b}$, for some primes $p$ and $q$. Find $ab+p+q$.


Solution

Claim: The number of pairs $A$ and $B$ such that $A \subseteq B$ is $3^{10}$.

Method 1: If $B$ has $k$ elements, then there are $2^k$ choices for $A$. Since $B$ has $k$ elements $\binom{10}{k}$ times as $B$ ranges over all possible subsets of $\mathcal{S}$, the desired quantity is \[\sum_{k = 1}^{10} \binom{10}{k} \cdot 2^k = (2^1 + 1)^{10} = 3^{10}.\]

Method 2: Each element of $\mathcal{S}$ has $3$ options: be in neither $A$ nor $B$, be in just $B$, or be in both $A$ and $B$. All elements assort independently, so there are $3^{10}$ valid pairs of subsets.

Then the answer is $\frac{3^{10}}{2^{20}} \Rightarrow \boxed{205}.$