Question

Sea $S$ un conjunto con seis elementos. Sea $\mathcal{P}$ el conjunto de todos los subconjuntos de $S.$ Los subconjuntos $A$ y $B$ de $S,$ no necesariamente distintos, se eligen de forma independiente y al azar de $\mathcal{P}.$ La probabilidad de que $B$ esté contenido en al menos uno de $A$ o $S - A$ es $\frac{m}{n^r},$ donde $m,$ $n,$ y $r$ son enteros positivos, $n$ es primo, y $m$ y $n$ son primos entre sí. ¿Cuánto vale $m + n + r$ ? (El conjunto $S - A$ es el conjunto de todos los elementos de $S$ que no están en $A.$ )

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

Respuesta

Solución:

Fija $A$ con $|A| = k.$ Hay $2^k$ subconjuntos $B \subseteq A$ y $2^{6-k}$ subconjuntos $B \subseteq S - A,$ y solo el conjunto vacío se cuenta dos veces, así que $2^k + 2^{6-k} - 1$ elecciones de $B$ tienen éxito. Como hay $\binom{6}{k}$ conjuntos $A$ de tamaño $k$ y $2^6$ elecciones para cada uno de $A$ y $B,$ la probabilidad es $\begin{aligned} &\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}}, \end{aligned}$ usando $\sum_k \binom{6}{k} 2^k = \sum_k \binom{6}{k} 2^{6-k}$ $= (1+2)^6 = 3^6.$

Esto se simplifica a $\frac{3^6 - 2^5}{2^{11}} = \frac{697}{2^{11}}.$ Como $697 = 17 \cdot 41$ es impar, tomamos $m = 697,$ $n = 2,$ $r = 11,$ y $m + n + r = 710.$

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 $\begin{aligned} &\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}}, \end{aligned}$ 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 Problema 10

Solución:

El Problema 10 en otros años