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}.$

Page

Toolbox

Search

Northeastern WOOTers Mock AIME I Problems/Problem 6

Problem 6

Solution