Problema de la suma de dados

Avatar de Usuario
Tiziano Brunelli

OFO - Medalla de Plata-OFO 2023 FOFO 13 años - Medalla-FOFO 13 años OFO - Mención-OFO 2024
Mensajes: 96
Registrado: Dom 21 Ago, 2022 1:24 pm
Medallas: 3
Nivel: Exolímpico
Ubicación: Al lado de Alta Córdoba, Córdoba capital, Córdoba

Problema de la suma de dados

Mensaje sin leer por Tiziano Brunelli »

Toto tiene $n$ dados ($n\geq 1$), todos con $m$ caras ($m\geq 2$) enumeradas del $1$ hasta $m$. Toto tira los $n$ dados y suma sus resultados, y como resultado de esta suma obtiene $x$. Sea $D^n_m(x)$ la probabilidad de que se obtenga el número $x$ tras sumar los $n$ dados de $m$ caras (y suponiendo que, en todos los dados, todas las caras tienen la misma probabilidad de salir). Determinar el valor de $D^n_m(x)$ en función de $n$,$m$ y $x$.
"cada vez que uses xor, piensa en mí, estaré usando vectores módulo 2"- un cordobés a otro. :D
Avatar de Usuario
Tiziano Brunelli

OFO - Medalla de Plata-OFO 2023 FOFO 13 años - Medalla-FOFO 13 años OFO - Mención-OFO 2024
Mensajes: 96
Registrado: Dom 21 Ago, 2022 1:24 pm
Medallas: 3
Nivel: Exolímpico
Ubicación: Al lado de Alta Córdoba, Córdoba capital, Córdoba

Re: Problema de la suma de dados

Mensaje sin leer por Tiziano Brunelli »

Este problema se me ocurrió tras ver la particular forma en la que se "distribuyen" las probabilidades al sumar los dos dados en el monopoly
1  
"cada vez que uses xor, piensa en mí, estaré usando vectores módulo 2"- un cordobés a otro. :D
Avatar de Usuario
Tiziano Brunelli

OFO - Medalla de Plata-OFO 2023 FOFO 13 años - Medalla-FOFO 13 años OFO - Mención-OFO 2024
Mensajes: 96
Registrado: Dom 21 Ago, 2022 1:24 pm
Medallas: 3
Nivel: Exolímpico
Ubicación: Al lado de Alta Córdoba, Córdoba capital, Córdoba

Re: Problema de la suma de dados

Mensaje sin leer por Tiziano Brunelli »

Antes que nada hacer una aclaración para todos los casos:
Spoiler: mostrar
1.)$n\leq x\leq mn$
debido a que lo mínimo que se puede sumar es $n$ con $n$ cantidad de $unos$ y lo máximo que se puede sumar es $nm$ con $n$ cantidad de $m$-s
2.)$D^n_m(n+k)$=$D^n_m(nm-k)$; $0\geq k \geq n(m-1)$
Spoiler: mostrar
Esto porque la probabilidad de que salga $n+k$ se puede ver como cuantas posibilidades tenemos de que una cadena de $n$ números, algunos $unos$ sumando otros números, pero la suma de las diferencias de esos números con $1$ tienen que ser igual a $k$,se puede pensar como que se tenía una cadena original de $n$ $unos$ y a algunos $unos$ se los cambió por esos otros números, y a cada uno ($1$) no se puede cambiar por otro número cuya diferencia con él ($1$) sea mayor a $m-1$ (porque sino habría un número mayor que $m$ sumando) dividido por $m^n$ que serían las posibilidades totales de combinaciones de sumandos. Pasa que para calcular la posibilidad de $nm-k$ se utiliza un argumento análogo solo que ahora es una cadena de $n$ $m$-s y se les intercambia con números menores tal que la diferencia (valor absoluto) entre un $m$ y el número que se le cambió no sea mayor a $m-1$, entonces la probabilidad sería las posibilidades de lograr eso y q la suma de todas las diferencias sea igual a $k$ dividido por $m^n$.
3.)$D^1_m(x)=\frac{1}{m}$
es simplemente la probabilidad de que te salga un número en un dado
4.)
[*]$D^2_m(2+k)=\frac{2+k-1}{m^2}$ si $0\leq k\leq m-1$
[*]$D^2_m(2m-k)=\frac{2+k-1}{m^2}$ si $0\leq k\leq m-1$
esto porque, supongamos que $a_x$ es la cantidad de posibilidades de sumar $x$ con los dos dados de $m$ caras, tenemos que $a_{2+k}=a_{2m-k}$. Notemos que $\forall i, 2\leq i\leq m+1: a_i=i-1$
Spoiler: mostrar
porque suponiendo esta cota de $i$ se tiene que $a_i$ es lit la cantidad de sumar $i$ usando dos enteros postivos, porque el mayor número que se puede usar para sumar $i$ con otro entero es $i-1$ lo cual es claramente menor o igual, pero nunca será mayor, que $m$, como sí importa el orden, hay $i-1$ formas de sumar $i$, una por cada entero postivo menor que $i$
Entonces queda ya demostrada la propiedad
Solución de los casos $D^n_2(x)$:
Spoiler: mostrar
Si hay $n$ dados de $2$ caras cada uno, el menor número que se puede obtener sumando es $n$ ($n$ cantidad de $unos$) y el mayor es $2n$ ($n$ cantidad de $2$), por lo que cualquier $x$ fuera de este rango tiene un valor igual a 0.De aquí hay que notar que si se quiere saber cómo sumar un número $x_0$ dentro del intervalo se deduce que se sumarán $x_0-n$ cantidad de 2 y $2n-x_0$ cantidad de $unos$, esto porque $n$ se suma con $n$ unos y por cada unidad que avanzamos "intercambiamos" un 1 por un 2. Por lo que la probabilidad de que salga un $x$ es las distintas posibilidades de ordenar la cantidad $x-n$ de 2 sumando divido por las posibilidades totales, osea:
$D^n_2(x)=\frac{\binom{n}{x-n}}{2^n}$
Solución de los casos $D^n_3(x)$:
Spoiler: mostrar
próximamente si encuentro la hoja en la que lo hice o se me ocurre denuevo cómo hacerlo ;v
Spoiler: mostrar
Imagen
1  
"cada vez que uses xor, piensa en mí, estaré usando vectores módulo 2"- un cordobés a otro. :D
Fedex

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021 OFO - Jurado-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 269
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 11
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Re: Problema de la suma de dados

Mensaje sin leer por Fedex »

Spoiler: mostrar
Ordenamos los dados del $1$ al $n$. Cada tupla de números tiene $\frac{1}{m^n}$ chances de salir por lo que nuestra respuesta es de la forma $\frac{s}{m^n}$ donde $s$ es la cantidad de maneras de elegir los $n$ valores entre $1$ y $m$ de manera que sumen $x$. Ahora por cajitas y bolitas son $\binom{x-1}{n-1}$ las maneras de repartir los valores de modo que cada dado aporte al menos $1$ unidad. Entonces $s = \binom{x-1}{n-1} - r$ donde $r$ son las maneras de que sumen $x$ con algún dado con valor de al menos $m+1$. Si definimos $A_i$ al conjunto de las disposiciones con el dado $i$-ésimo aportando al menos $m+1$ por principio de inclusión exclusión:
$$r = |A_1 \cup A_2 \cup \cdots \cup A_n| = \sum |A_i| - \sum |A_i \cap A_j| + \cdots + (-1)^{n+1} |A_1 \cap A_2 \cap \cdots \cap A_n|$$
Donde vamos a sumando las intersecciones impares y restando las pares. El cardinal de la intersección de $k$ conjuntos viene dado por repartir $x - n - mk$ bolitas (bolitas libres) en $n$ cajitas lo que es $\binom{x-mk-1}{n-1}$.
Entonces:
$$r =\sum_{k=1}^n (-1)^{k+1} \binom{n}{k}\binom{x-mk-1}{n-1}$$
Y finalmente:
$$D_m^n(x) = \frac{\binom{x-1}{n-1} - \sum_{k=1}^n (-1)^{k+1}\binom{n}{k}\binom{x-mk-1}{n-1}} {m^n}$$
Expresión que solo tiene sentido para $n \leq x \leq mn$, para el resto de casos $D_m^n(x) = 0$.
2  
This homie really did 1 at P6 and dipped.
Responder