Let $S$ be a [set](https://artofproblemsolving.com/wiki/index.php/Set) with six [elements](https://artofproblemsolving.com/wiki/index.php/Element). Let $\mathcal{P}$ be the set of all [subsets](https://artofproblemsolving.com/wiki/index.php/Subset) of $S.$ Subsets $A$ and $B$ of $S$, not necessarily distinct, are chosen independently and at random from $\mathcal{P}$. The [probability](https://artofproblemsolving.com/wiki/index.php/Probability) that $B$ is contained in one of $A$ or $S-A$ is $\frac{m}{n^{r}},$ where $m$, $n$, and $r$ are [positive](https://artofproblemsolving.com/wiki/index.php/Positive) [integers](https://artofproblemsolving.com/wiki/index.php/Integer), $n$ is [prime](https://artofproblemsolving.com/wiki/index.php/Prime), and $m$ and $n$ are [relatively prime](https://artofproblemsolving.com/wiki/index.php/Relatively_prime). Find $m+n+r.$ (The set $S-A$ is the set of all elements of $S$ which are not in $A.$)
Use [casework](https://artofproblemsolving.com/wiki/index.php/Casework):

$B$ has 6 elements:
Probability: $\frac{1}{2^6} = \frac{1}{64}$
$A$ must have either 0 or 6 elements, probability: $\frac{2}{2^6} = \frac{2}{64}$.
$B$ has 5 elements:
Probability: ${6\choose5}/64 = \frac{6}{64}$
$A$ must have either 0, 6, or 1, 5 elements. The total probability is $\frac{2}{64} + \frac{2}{64} = \frac{4}{64}$.
$B$ has 4 elements:
Probability: ${6\choose4}/64 = \frac{15}{64}$
$A$ must have either 0, 6; 1, 5; or 2,4 elements. If there are 1 or 5 elements, the set which contains 5 elements must have four emcompassing $B$ and a fifth element out of the remaining $2$ numbers. The total probability is $\frac{2}{64}\left({2\choose0} + {2\choose1} + {2\choose2}\right) = \frac{2}{64} + \frac{4}{64} + \frac{2}{64} = \frac{8}{64}$.
We could just continue our casework. In general, the probability of picking B with $n$ elements is $\frac{{6\choose n}}{64}$. Since the sum of the elements in the $k$th row of [Pascal's Triangle](https://artofproblemsolving.com/wiki/index.php/Pascal%27s_Triangle) is $2^k$, the probability of obtaining $A$ or $S-A$ which encompasses $B$ is $\frac{2^{7-n}}{64}$. In addition, we must count for when $B$ is the empty set (probability: $\frac{1}{64}$), of which all sets of $A$ will work (probability: $1$).
Thus, the solution we are looking for is $\left(\sum_{i=1}^6 \frac{{6\choose i}}{64} \cdot \frac{2^{7-i}}{64}\right) + \frac{1}{64} \cdot \frac{64}{64}$
$=\frac{(1)(64)+(6)(64)+(15)(32)+(20)(16)+(15)(8)+(6)(4)+(1)(2)}{(64)(64)}$
$=\frac{1394}{2^{12}}$
$=\frac{697}{2^{11}}$.
The answer is $697 + 2 + 11 = 710$.