Resolver un problema de probabilidad simple
El premio total en metálico del Concurso Global de Matemáticas de Alibaba es de aproximadamente 300.000 dólares estadounidenses. El concurso está abierto a cualquier persona, se permite la programación. A continuación se muestra la primera pregunta de la pista de probabilidad y combinatoria de las finales de 2021.
Pregunta
Un baile comienza con 20 niñas y 22 niños, y hay innumerables niñas y niños esperando afuera. En cada ronda, se selecciona al azar una persona del grupo.
Si se elige una chica, ésta invitará a bailar a uno de los chicos de la fiesta, y ambos se marcharán de la fiesta.
Si eligen al chico, invita a una chica a bailar con un chico esperando afuera, y los tres se quedan en la fiesta.
La fiesta termina cuando solo quedan los (dos) chicos.
P: ¿Cuál es la probabilidad de que la fiesta nunca termine?
Entendiendo el problema
Cuando se selecciona una niña, habrá un hombre y una mujer menos en la fiesta; cuando se selecciona un niño, habrá un hombre y una mujer más en la fiesta. la fiesta.
Este es un ejemplo de "aleatorización". Después de cada ronda del juego, la probabilidad de elegir un niño y una niña del grupo cambia.
Si quedan 2n personas, entonces la probabilidad de seleccionar una niña es Pr(G)=(n ?Pr(B)=(n 1)/(2n)
Esperamos encontrar la probabilidad de que la fiesta "nunca termine", calculada de la siguiente manera:
El desafío es, por tanto, encontrar la probabilidad de que la fiesta termine después de un número finito de rondas.
Cuando comienza, Hay 20 niñas y 22 niños La probabilidad de seleccionar una niña es Pr(G) = 20 / 42
La probabilidad de seleccionar 2 niñas seguidas es: Pr(GG) = (. 20 / 42)Pr (GG) = (20 / 42) × (19 / 40)
La probabilidad de seleccionar 20 chicas seguidas es: Pr (GG...G 20 veces) = ( 20 / 42) × (19 / 40) × ... (2 / 6) × (1 / 4)
Quitando los numeradores y denominadores consecutivos, obtenemos
La probabilidad de seleccionar 20 chicas seguidas es demasiado pequeño (difícilmente posible). La fiesta también podría terminar después de la ronda 21, 30 o 100.
Quiero simplificar este problema y espero encontrar algunos patrones.
Simplificando el problema
Primero, considere el caso más simple. Supongamos que solo hay 1 niña y 3 niños en el grupo. Después de dos rondas, hay tres resultados posibles:
Agregue dos pares de niñas y niños
Elimine dos pares de niñas y niños
Sin cambios en general
Veamos la probabilidad de " sin cambios" comenzando con 2 niñas y 4 niños:
Comenzando con 2 niñas y 4 niños:
Veamos la probabilidad "sin cambios" de comenzar con 2 niñas y 4 niños Niños :
Encontramos que 1/2 no tiene nada que ver con el número de personas que quedan:
Entonces podemos calcular las probabilidades de las otras dos situaciones:
Bien. Ahora usemos estas reglas para resolver un problema simple: Termina un grupo de 2 niñas y 4 niños
Resolviendo un problema simple
Supongamos que comienza el grupo. solo 2 niñas y 4 niños. Entonces solo necesitamos eliminar 2 pares de niños del grupo.
Esta es una serie infinita y supongo que converge (de lo contrario, la probabilidad sería mayor que 1). comience contando los primeros elementos y vea qué sucede
(Como recordatorio, 2n es el número de personas que quedan en el grupo. En este caso, comenzamos con n = 3).
A continuación, agrupo las dos "dos rondas" en un grupo, usando "0" para representar "sin cambios", "-2" para representar "dos pares eliminados"; El partido creció en dos parejas".
El hecho de que Pr(2, ?2)= (1/2)^4 es útil. Puedes verificarlo y simplificarlo usando la fórmula anterior:
En este punto, sabemos:
Parece una serie geométrica. Sigamos:
Donde 3 × Pr(0, 2, ?2, ?2) El 3 en él aumenta la complejidad de la serie infinita.
Encuentra la estructura
A medida que los números aumentan, calcular las permutaciones de "?2" y "2" se vuelve más complejo. Fíjate en contar 4 "?2" y 3 "2":
Pero no olvides que la competencia permite programar, lo que facilita mucho la resolución del problema.
Después de ejecutar el programa, descubrí que el número de pasos que contienen solo "?2" y "2" puede ser el siguiente:
1, 2, 5, 14, 42 , 132, .. ....
Quizás muchos de vosotros no estéis familiarizados con esta secuencia de números, que se conocen como números catalanes. También descubrí que el número catalán tiene una función generadora simple:
donde C_n es el enésimo número catalán.
Estudiando series infinitas
La siguiente es la relación entre series de probabilidad infinitas y números catalanes:
Primero, uso Pr(0) = 1/2 y Pr(2, -2) = (1/2)^4 calcule las probabilidades individuales como se indica arriba.
Ahora extraemos el factor común 1/12 y lo dividimos en una serie infinita:
La serie negra es una serie geométrica infinita:
Rosa, azul y las series naranja tienen todas la misma estructura, similar a la función generadora de los números catalanes, todas convergen a
Ahora, para cada cascada de colores, puedes aplicar la función generadora catalana para los números niya:
La probabilidad de que un grupo formado por 2 niñas y 4 niños termine después de un número finito de rondas es exactamente 1/3.
Resolver este "problema más simple" ha sido un proceso largo. Afortunadamente, ampliar este resultado para resolver el problema original no requiere mucho trabajo.
Respuesta
El siguiente problema que quiero resolver es: comenzando con 20 niñas y 22 niños, la probabilidad de que 2 pares de niños y niñas sean eliminados después de un número limitado de rondas. .
El método de cálculo es el mismo que el anterior, excepto que (1/12) anterior será reemplazado por (19/84), que es la probabilidad de seleccionar 2 niñas cuando n = 21.
Para n = 19 podemos hacer el mismo cálculo:
Luego multiplicamos estas probabilidades hasta 1/3 de arriba. Porque sólo cuando estos acontecimientos suceden uno tras otro puede terminar la fiesta.
Cancela el numerador y el denominador y obtienes
Ahora la respuesta a la pregunta es: "¿Cuál es la probabilidad de que la fiesta nunca termine?"
Respuesta Es 21/1.