De los subconjuntos de 3 elementos de $\{1, 2, 3, \ldots , 100\}$ (el conjunto de los 100 primeros enteros positivos), un subconjunto $(x, y, z)$ se elige al azar. ¿Cuál es la probabilidad de que $x + y + z$ es divisible por 3?
Este es un problema de la Olimpiada de Matemáticas. Agradecería una buena solución.
$$p=2*\frac{33}{100}\frac{32}{99}\frac{31}{98}+\frac{34}{100}\frac{33}{99}\frac{32}{98}+6*\frac{34}{100}\frac{33}{99}\frac{33}{98}$$
La probabilidad anterior muestra tres partes claras que son las formas de sumar 3 números y dar un número divisible por 3:
Tenga en cuenta que el $\frac{97!}{100!}$ que aparece con frecuencia es el número de formas de elegir los 3 números de 100. Me sale: $$p=\frac{817}{2450}$$ .
Obsérvese que nuestro conjunto tiene $34$ miembros equivalentes a $1$ modulo $3$ (es decir, con resto $1$ al dividir por $3$ ), $33$ equivalente a $2$ y $33$ equivalente a $0$ .
Supongamos que extraemos tres números al azar para crear nuestro subconjunto. Para obtener una suma divisible por $3$ podríamos dibujar cualquiera de los siguientes conjuntos de restos: $$ 2,2,2\\ 1,1,1\\ 0,0,0\\ 0,1,2 \text{ (In each of }3! \text{ arrangements)} $$ Por lo tanto, el número de dibujos posibles que darán un múltiplo de $3$ (el orden importa aquí) es $$ (34\times 33\times 32)+ (33\times 32\times 31)\times 2+(33\times 34 \times 33)\times (3\times 2 \times 1) $$ Hay $100\times 99\times 98$ formas posibles de sacar tres números, nuestra probabilidad es $$ \frac{(34\times 33\times 32)+ (33\times 32\times 31)\times 2+(33\times 34 \times 33)\times (3\times 2 \times 1)}{100\times 99 \times 98} $$ Lo que, simplificando, arroja una respuesta de $\frac{817}{2450}$ .
También es posible abordar esto con combinaciones en lugar de permutaciones. Es decir, teniendo en cuenta que debemos tener todos en una categoría o uno de cada categoría, nuestro número total de posibilidades es $$ \binom{33}{3} + \binom{33}{3} + \binom{34}{3} + 33\times 34 \times 33 $$ produciendo una probabilidad de $$ \frac{\binom{33}{3} + \binom{33}{3} + \binom{34}{3} + 33\times 34 \times 33}{\binom{100}{3}} $$
Utilizando el Teorema de Enumeración de Polya y suponiendo que elegimos el subconjunto de tres elementos de $\{1,n\}$ vemos que tenemos la siguiente clase combinatoria (no etiquetada): $$\mathcal{Q} = \mathfrak{P}_3(\mathcal{Z}+\mathcal{Z}^2+\cdots+\mathcal{Z}^n).$$ Ahora el índice de ciclo para la construcción del conjunto viene dado por $$Z(A_n)-Z(S_n) = Z(S_n)_{a_k=(-1)^{k-1} a_k}.$$ Para $n=3$ obtenemos el índice de ciclo $$ Z = \frac{1}{6} a_1^3 - \frac{1}{2} a_1 a_2 + \frac{1}{3} a_3.$$ La función generadora que sustituimos en $Z$ es $$z+z^2+\cdots+z^n = z(1+z+\cdots+z^{n-1}) = z \frac{1-z^n}{1-z}.$$ Por tanto, la función generadora de todos los subconjuntos por tamaño total (no sólo de aquellos cuya suma es divisible por tres) es $$f(z) = \frac{1}{6} \left(z \frac{1-z^n}{1-z}\right)^3 - \frac{1}{2} z \frac{1-z^n}{1-z} z^2 \frac{1-z^{2n}}{1-z^2} + \frac{1}{3} z^3 \frac{1-z^{3n}}{1-z^3}.$$ Necesitamos el valor en $z=1$ de esta función generadora (excluyendo las potencias no divisibles por tres). Configurando $w=e^{2\pi i/3}$ vemos que el recuento total de los subconjuntos con suma divisible por tres es $$\left.\frac{1}{3}(f(wz)+f(w^2z)+f(w^3z))\right|_{z=1}.$$ Supongamos ahora que $$n\equiv r\bmod 3$$ donde $r\in(1,2,3).$ Entonces tenemos que $$f(wz)_{z=1} = \frac{1}{6} \left(\sum_{q=1}^r w^q\right)^3 -\frac{1}{2} \left(\sum_{q=1}^r w^q\right) \left(\sum_{q=1}^r w^{2q}\right) +\frac{1}{3}n$$ y que $$f(w^2z)_{z=1} = \frac{1}{6} \left(\sum_{q=1}^r w^{2q}\right)^3 -\frac{1}{2} \left(\sum_{q=1}^r w^{2q}\right) \left(\sum_{q=1}^r w^{4q}\right) +\frac{1}{3}n$$ y $$f(w^3z)_{z=1} = \frac{1}{6}n^3-\frac{1}{2}n^2+\frac{1}{3}n = {n\choose 3}.$$ Haciendo la aritmética encontramos que $$f(wz)_{z=1} + f(w^2z)_{z=1} = \frac{1}{3} \frac{w^{2r}-w^r}{w^2-w} - \left( \frac{w^{2r}-w^r}{w^2-w}\right)^2 +\frac{2}{3} n.$$ Esto da para el recuento total el valor $$\frac{1}{9} \frac{w^{2r}-w^r}{w^2-w} - \frac{1}{3} \left( \frac{w^{2r}-w^r}{w^2-w}\right)^2 + \frac{2}{9} n +\frac{1}{3} {n\choose 3}$$ que puede simplificarse aún más en $$\frac{1}{9} (r-3)(3r-2) + \frac{2}{9} n +\frac{1}{3} {n\choose 3}$$ que produce la secuencia $$0, 0, 1, 2, 4, 8, 13, 20, 30, 42, 57, 76, 98, 124, 155, 190, 230, 276, 327, 384,\ldots$$ que es A061866 de la OEIS. Así, obtenemos la siguiente fórmula para la probabilidad $$\frac{1}{3} +{n\choose 3}^{-1} \left(\frac{1}{9} (r-3)(3r-2) + \frac{2}{9} n\right).$$ Sustituyendo $n=100$ en lo anterior obtenemos el resultado final, $$\frac{817}{2450}.$$
Bueno, ya que hay dos respuestas teóricas que compiten entre sí (ahora resueltas), pensé que podría ser divertido ofrecer una rápida comprobación computacional, aquí usando Mathematica :
Count[Map[Total, Subsets[Range[100],{3}]]/3, _Integer] / Binomial[100,3]817/2450
La evaluación tarda unos 0,2 segundos.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
