Probabilidad de que la suma sea divisible por $n$ después de un $n+1$ se tira un dado de una cara $m$ tiempos.

Question

$\text{Introduction}$

Recientemente me he encontrado con este bonito problema:

Dejemos que $p\in\mathbb{P}$ . Tenemos un $(p+1)-$ dado de una cara, con números $1,2,...,p+1$ en él. Halla la probabilidad de que, después de lanzarla $n$ veces, sumando los números obtenidos en cada tirada, obtenemos un número divisible por $p$ .

Permítanme resumir el $2$ soluciones que tengo para esto.

---

$\text{Solution 1:}$

Haz una repetición. Deja que $a_i^k$ el número de casos en los que la suma que obtenemos después de $k$ rollos es $\equiv i\pmod{p}$ .

Al hacer esto, obtenemos $a_i^{k+1}=a^k_0+a^k_1+...+a^k_{p-1}+a^k_{i-1}$ (por qué tenemos ese segundo $a^k_{i-1}$ ? Bueno, porque podemos rodar un $1$ pero también un $p+1\equiv 1\pmod{p}$ )

Ahora, utilizando esta fórmula, podemos deducir por inducción lo que $a_0^k,a_1^k,...,a_{p-1}^k$ son.

(Y lo dividimos por el número total de casos, que es $(p+1)^n$ y obtenemos la probabilidad)

---

$\text{Solution 2:}$

Dejemos que $\epsilon=\cos{\frac{2\pi}{p}}+i\sin{\frac{2\pi}{p}}$ . No necesitamos una recurrencia, por lo que basta con dejar que $a_i$ sea el número de casos en los que la suma es $\equiv i\pmod{p}$ . Entonces, considera el siguiente polinomio:

$$\sum_{k=0}^{p-1}a_k\epsilon^k$$

y observar que es igual a

$$\sum_{1\leq x_1,x_2,...,x_n\leq p+1}\epsilon^{x_1+x_2+...+x_n}=(1+\epsilon+...+\epsilon^{p+1})^n=\epsilon^n$$

Así que desde aquí, usando este bonito lema:

Si $\epsilon=\cos{\frac{2\pi}{p}}+i\sin{\frac{2\pi}{p}}$ entonces $\sum_{k=0}^{p-1}x_k\epsilon^k=0$ $\Leftrightarrow$ $x_0=x_1=...=x_{p-1}$

Podemos encontrar $a_0,a_1,...,a_{p-1}$

(Una vez más, lo siento, estas dos son hermosas pruebas que he sacrificado aquí, pero sólo quería mostrar las ideas)

Para dar un poco más de contexto, la respuesta real a este problema es:

Si $n$ es disible por $p$ la probabilidad es $$\frac{(p+1)^n+p-1}{p}$$ si $n$ no es divisible por $p$ Es decir, es $$\frac{(p+1)^n-1}{p}$$

---

$\text{My issue:}$

Mira este problema:

Dejemos que $n\in\mathbb{N}$ . Tenemos un $(n+1)-$ dado de una cara, con números $1,2,...,n+1$ en él. Halla la probabilidad de que, después de lanzarla $m$ veces, sumando los números obtenidos en cada tirada, obtenemos un número divisible por $n$ .

Es algo similar, excepto que esta vez $n$ no es un primo.

Ahora, por supuesto, la prueba $2$ est $100\%$ basado en el hecho de que $p\in\mathbb{P}$ y la prueba $1$ sería bastante feo.

Quiero preguntarle, ¿cómo podemos resolver el problema anterior? (Me interesan más las respuestas abstractas, no las de tipo recurrente)

Gracias por leer.

---

Answer 1

Acérquese a $1$ funciona igual de bien para cualquier $n$ .

La solución general es que $a^k_0, a^k_1, \dots, a^k_{n-1}$ son todos casi iguales: hay algunos $s$ tal que $$ a^k_i = \begin{cases} s+1 & i \equiv k \pmod n \\ s & \text{otherwise}. \end{cases} $$ Podemos demostrarlo por inducción. Tenemos $$a^k_i = (a^{k-1}_0 + a^{k-1}_1 + \dots + a^{k-1}_{n-1}) + a^{k-1}_{i-1}$$ por cada $i$ , excepto cuando $i=0$ tenemos $a^{k-1}_{n-1}$ en lugar de $a^{k-1}_{i-1}$ . La primera parte de la suma es la misma para todos los $i$ así que podemos ignorarla. La segunda parte de la suma es la misma para casi todos los $i$ pero es $1$ más grande cuando $i-1 \equiv k-1 \pmod n$ que corresponde al caso en que $i \equiv k \pmod n$ .

No me molesté en computar $s$ pero, por supuesto, es fácil de encontrar con sólo saber que $a^k_0 + \dots + a^k_{n-1} = (n+1)^k$ . Al final, la probabilidad de obtener una suma divisible por $n$ después de $k$ rollos es $$ \frac{(n+1)^k-1}{n(n+1)^k} = \frac{\lfloor (n+1)^k/n\rfloor}{(n+1)^k} $$ cuando $k$ no es divisible por $n$ y $$ \frac{(n+1)^k+n-1}{n(n+1)^k}= \frac{\lceil (n+1)^k/n\rceil}{(n+1)^k} $$ cuando $k$ es divisible por $n$ .