IMC 1999 · Day 2 · P8

For all nonnegative integers $n$ and modulo 5 residue class $r$, denote by $p_n^{(r)}$ the probability that after $n$ throwing the sum of values is congruent to $r$ modulo $n$. It is obvious that $p_0^{(0)} = 1$ and $p_0^{(1)} = p_0^{(2)} = p_0^{(3)} = p_0^{(4)} = 0$.

Moreover, for any $n > 0$ we have $$\tag{1} p_n^{(r)} = \sum_{i=1}^{6} \frac{1}{6}\, p_{n-1}^{(r-i)}.$$ From this recursion we can compute the probabilities for small values of $n$ and can conjecture that $p_n^{(r)} = \frac{1}{5} + \frac{4}{5 \cdot 6^n}$ if $n \equiv r \pmod{5}$ and $p_n^{(r)} = \frac{1}{5} - \frac{1}{5 \cdot 6^n}$ otherwise. From (1), this conjecture can be proved by induction.

Let $S$ be the set of all sequences consisting of digits $1, \dots, 6$ of length $n$. We create collections of these sequences.

Let a collection contain sequences of the form $$\underbrace{66 \dots 6}_{k} X Y_1 \dots Y_{n-k-1},$$ where $X \in \{1, 2, 3, 4, 5\}$ and $k$ and the digits $Y_1, \dots, Y_{n-k-1}$ are fixed. Then each collection consists of 5 sequences, and the sums of the digits of sequences give a whole residue system mod 5.

Except for the sequence $66 \dots 6$, each sequence is the element of one collection. This means that the number of the sequences, which have a sum of digits divisible by 5, is $\frac{1}{5}(6^n - 1) + 1$ if $n$ is divisible by 5, otherwise $\frac{1}{5}(6^n - 1)$.

Thus, the probability is $\frac{1}{5} + \frac{4}{5 \cdot 6^n}$ if $n$ is divisible by 5, otherwise it is $\frac{1}{5} - \frac{1}{5 \cdot 6^n}$.

For arbitrary positive integer $k$ denote by $p_k$ the probability that the sum of values is $k$. Define the generating function $$f(x) = \sum_{k=1}^{\infty} p_k x^k = \left( \frac{x + x^2 + x^3 + x^4 + x^5 + x^6}{6} \right)^n.$$ (The last equality can be easily proved by induction.)

Our goal is to compute the sum $\sum\limits_{k=1}^{\infty} p_{5k}$. Let $\varepsilon = \cos\frac{2\pi}{5} + i \sin\frac{2\pi}{5}$ be the first 5th root of unity. Then $$\sum_{k=1}^{\infty} p_{5k} = \frac{f(1) + f(\varepsilon) + f(\varepsilon^2) + f(\varepsilon^3) + f(\varepsilon^4)}{5}.$$ Obviously $f(1) = 1$, and $f(\varepsilon^j) = \frac{\varepsilon^{jn}}{6^n}$ for $j = 1, 2, 3, 4$. This implies that $f(\varepsilon) + f(\varepsilon^2) + f(\varepsilon^3) + f(\varepsilon^4)$ is $\frac{4}{6^n}$ if $n$ is divisible by 5, otherwise it is $\frac{-1}{6^n}$. Thus, $\sum\limits_{k=1}^{\infty} p_{5k}$ is $\frac{1}{5} + \frac{4}{5 \cdot 6^n}$ if $n$ is divisible by 5, otherwise it is $\frac{1}{5} - \frac{1}{5 \cdot 6^n}$.