$\text{Introduction}$
I have recently encountered this nice problem:
Let $p\in\mathbb{P}$. We have a $(p+1)-$sided die, with numbers $1,2,…,p+1$ on it. Find the probability that, after rolling it $n$ times, by adding up the numbers we got at each roll, we get a number divisible by $p$.
Let me summarize the $2$ solutions I have for this.
$\text{Solution 1:}$
Make a recurrence. Let $a_i^k$ the number of cases in which the sum we get after $k$ rolls is $\equiv i\pmod{p}$.
By doing this, we get $a_i^{k+1}=a^k_0+a^k_1+…+a^k_{p-1}+a^k_{i-1}$ (why do we have that second $a^k_{i-1}$? Well because we can roll a $1$ but also a $p+1\equiv 1\pmod{p}$)
Now using this formula, we can deduce by induction what $a_0^k,a_1^k,…,a_{p-1}^k$ are.
(And we divide by the total number of cases, which is $(p+1)^n$ and we get the probability)
$\text{Solution 2:}$
Let $\epsilon=\cos{\frac{2\pi}{p}}+i\sin{\frac{2\pi}{p}}$. We don't need a recurrence, so just let $a_i$ be the number of cases in which the sum is $\equiv i\pmod{p}$. Then, consider the following polynomial:
$$\sum_{k=0}^{p-1}a_k\epsilon^k$$
and observe it is equal to
$$\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$$
So from here, using this nice lemma:
If $\epsilon=\cos{\frac{2\pi}{p}}+i\sin{\frac{2\pi}{p}}$, then $\sum_{k=0}^{p-1}x_k\epsilon^k=0$ $\Leftrightarrow$ $x_0=x_1=…=x_{p-1}$
We can find $a_0,a_1,…,a_{p-1}$
(Again, sorry, these are both beautiful proofs which I slaughtered here, but I just wanted to show you the ideas)
To give a bit more context, the actual answer to this problem is:
If $n$ is disible by $p$, the probability is $$\frac{(p+1)^n+p-1}{p}$$ if $n$ is not divisible by $p$, it is $$\frac{(p+1)^n-1}{p}$$
$\text{My issue:}$
Look at this problem:
Let $n\in\mathbb{N}$. We have a $(n+1)-$sided die, with numbers $1,2,…,n+1$ on it. Find the probability that, after rolling it $m$ times, by adding up the numbers we got at each roll, we get a number divisible by $n$.
It's kinda similar, except this time $n$ is not a prime.
Now of course, proof $2$ is $100\%$ based on the fact that $p\in\mathbb{P}$ and proof $1$ would be quite ugly.
I want to ask you, how can we solve the above problem? (I am more interested in abstract answers, not recurrence-type answers)
Thank you for reading!
Best Answer
Approach $1$ works just as well for any $n$.
The general solution is that $a^k_0, a^k_1, \dots, a^k_{n-1}$ are all nearly equal: there is some $s$ such that $$ a^k_i = \begin{cases} s+1 & i \equiv k \pmod n \\ s & \text{otherwise}. \end{cases} $$ We can prove this by induction. We have $$a^k_i = (a^{k-1}_0 + a^{k-1}_1 + \dots + a^{k-1}_{n-1}) + a^{k-1}_{i-1}$$ for every $i$, except when $i=0$ we have $a^{k-1}_{n-1}$ in place of $a^{k-1}_{i-1}$. The first part of the sum is the same for all $i$, so we can disregard it. The second part of the sum is the same for nearly all $i$, but it is $1$ bigger when $i-1 \equiv k-1 \pmod n$, which corresponds to the case where $i \equiv k \pmod n$.
I didn't bother computing $s$, but of course it is easy to find just knowing that $a^k_0 + \dots + a^k_{n-1} = (n+1)^k$. In the end, the probability of getting a sum divisible by $n$ after $k$ rolls is $$ \frac{(n+1)^k-1}{n(n+1)^k} = \frac{\lfloor (n+1)^k/n\rfloor}{(n+1)^k} $$ when $k$ is not divisible by $n$, and $$ \frac{(n+1)^k+n-1}{n(n+1)^k}= \frac{\lceil (n+1)^k/n\rceil}{(n+1)^k} $$ when $k$ is divisible by $n$.