Question

Let $S$ be a set with six elements. Let $\mathcal{P}$ be the set of all subsets of $S.$ Subsets $A$ and $B$ of $S,$ not necessarily distinct, are chosen independently and at random from $\mathcal{P}.$ The probability that $B$ is contained in at least one of $A$ or $S - A$ is $\frac{m}{n^r},$ where $m,$ $n,$ and $r$ are positive integers, $n$ is prime, and $m$ and $n$ are relatively prime. Find $m + n + r.$ (The set $S - A$ is the set of all elements of $S$ which are not in $A.$ )

答案

Solution:

Fix $A$ with $|A| = k.$ There are $2^k$ subsets $B \subseteq A$ and $2^{6-k}$ subsets $B \subseteq S - A,$ and only the empty set is counted twice, so $2^k + 2^{6-k} - 1$ choices of $B$ succeed. Since there are $\binom{6}{k}$ sets $A$ of size $k$ and $2^6$ choices for each of $A$ and $B,$ the probability is $\frac{1}{2^{12}}\sum_{k=0}^{6} \binom{6}{k}\left(2^k + 2^{6-k} - 1\right) = \frac{2 \cdot 3^6 - 2^6}{2^{12}},$ using $\sum_k \binom{6}{k} 2^k = \sum_k \binom{6}{k} 2^{6-k} = (1+2)^6 = 3^6.$

This simplifies to $\frac{3^6 - 2^5}{2^{11}} = \frac{697}{2^{11}}.$ Since $697 = 17 \cdot 41$ is odd, we take $m = 697,$ $n = 2,$ $r = 11,$ and $m + n + r = 710.$

2007 AIME II Problem 10

Solution:

Problem 10 in Other Years