Programación de acertijos: Te dan n dados cada uno con caras numeradas del 1 al m. Lanzas los n dados y anotas la suma de los números en los n dados. Te dan un número x. Considérelo una ganancia si la suma obtenida es mayor que x. Encuentre la probabilidad de ganar dado n, m y x.

Utiliza programación dinámica. El objetivo es obtener la probabilidad de que la suma de dados sea exactamente X después de observar N tiradas de dados como C (X, N). La idea clave es que puede escribir C (X, N) como una función simple de C (X-1, N – 1), C (X – 2, N – 1),…, C (X – M, N – 1). Además, solo hay tantos pares de X y N, por lo que puede hacer este cálculo rápidamente. Luego puede resumir las opciones ganadoras para obtener la respuesta final.

Robert Neuhaus ha dado una respuesta correcta y eficiente. Mark Gordon ha dado un enfoque combinatorio para resolver el problema. Daré un enfoque combinatorio ligeramente diferente.

La probabilidad requerida es simplemente [matemática] \ frac {Número de casos favorables} {Número total de resultados} [/ matemática]

El número total de resultados es [matemática] M ^ {N} [/ matemática]
Los resultados favorables son los lanzamientos de N dados con [math] x \ le sum \ le m * n [/ math] donde [math] m * n [/ math] denota la suma máxima posible.

Considere el siguiente producto polinomial
[matemática] \ left (1 + yt + yt ^ {2} + yt ^ {3} + \ dots + yt ^ {n} \ right) [/ math]
[matemática] \ left (1 + yt ^ {2} + yt ^ {4} + yt ^ {6} + \ dots + yt ^ {2n} \ right) [/ math]
[matemática] \ left (1 + yt ^ 3 + yt ^ 6 + yt ^ {9} + \ dots + yt ^ {3n} \ right) [/ math]
[matemáticas] \ vdots [/ matemáticas]
[matemática] \ left (1 + yt ^ m + yt ^ {2m} + yt ^ {3m} + \ dots + yt ^ {mn} \ right) [/ math]

Como Mark Gordon mencionó, el exponente de t en el producto aquí contará la suma total de todas las caras de los dados. Además, el exponente de y contará el número de lanzamientos de dados. Como estamos sumando todos los dados, solo nos interesarán los términos donde el exponente de y es n.

Entonces, para resolver el problema, calcule
[matemáticas]
\ prod_ {i = 1} ^ {m} \ left (\ sum_ {j = 0} ^ n \ left (yt ^ {ij} \ right) \ right)
[/matemáticas]

y sume los coeficientes de los términos de la forma [matemática] y ^ {n} t ^ {i} [/ matemática] donde [matemática] x \ le i [/ matemática] para obtener el número total de resultados favorables. Calcule la probabilidad como se mencionó anteriormente.

EDITAR: Después de pensar un poco más, se me ocurrió una solución combinatoria más simple. El polinomio [matemático] \ left (t + t ^ 2 + t ^ 3 + \ dots + t ^ m \ right) [/ math] representa la función generadora para un solo lanzamiento de un solo dado. Dado que el lanzamiento de n dados es independiente el uno del otro, la función generadora para el evento combinado sería simplemente la función generadora para un solo lanzamiento elevado a la potencia de n, a saber. [matemáticas] \ izquierda (t + t ^ 2 + t ^ 3 + \ puntos + t ^ m \ derecha) ^ n [/ matemáticas]. Calcule el producto polinomial y resuma los coeficientes de todos los términos de la forma [matemática] t ^ i, x \ le i [/ matemática]. Esto no genera términos innecesarios.

La probabilidad se puede encontrar por (no de casos favorables) / (no total de casos).

No total de casos = m * n.

Los casos favorables se pueden encontrar utilizando la programación dinámica. Su estado sería (dados actuales, suma actual). Llamemos a este estado dp (dados, suma). Explicaré esto usando la recursividad:

Inicialmente, comienzas desde dp (dados = 0, suma = 0).
Desde el estado actual dp (dados, suma), puede ir a dp (dados + 1, suma + 1), dp (dados + 1, suma + 2) … hasta dp (dados + 1, suma + m).

dp (dados, suma) = dp (dados + 1, suma + 1) + dp (dados + 1, suma + 2) +… + dp (dados + 1, suma + m).

La condición básica es verificar si sum> X, cuando dice = n.

  if (dado == n) {
   si (suma> X) devuelve 1;
   de lo contrario, devuelve 0;
 }