uniolympiads Ελληνικά

IMC 1999, Day 2, Problem 2

We throw a dice (which selects one of the numbers 1,2,…,61, 2, \dots, 6 with equal probability) nn times. What is the probability that the sum of the values is divisible by 55?

Original from the official PDF2. We throw a dice (which selects one of the numbers 1, 2, . . . , 6 with equal probability) n times. What is the probability that the sum of the values is divisible by 5? (20 points)

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

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

Moreover, for any n>0n>0 we have

pn(r)=∑i=1616pn−1(r−i).(1)p_n^{(r)}=\sum_{i=1}^{6}\frac16p_{n-1}^{(r-i)}.\tag{1}
From this recursion we can compute the probabilities for small values of nn and can conjecture that pn(r)=15+45⋅6np_n^{(r)}=\frac15+\frac{4}{5\cdot6^n} if n≡r(mod  )5n\equiv r\quad(\mathrm{mod}\ \ )5 and pn(r)=15−15⋅6np_n^{(r)}=\frac15-\frac{1}{5\cdot6^n} otherwise. From (1), this conjecture can be proved by induction.

Solution 2. Let SS be the set of all sequences consisting of digits 1,…,61,\dots,6 of length nn. We create collections of these sequences.

Let a collection contain sequences of the form

66…6⏟kXY1…Yn−k−1,\underbrace{66\ldots6}_{k}XY_1\ldots Y_{n-k-1},
where X∈{1,2,3,4,5}X\in\{1,2,3,4,5\} and kk and the digits Y1,…,Yn−k−1Y_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…666\ldots6, 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 15(6n−1)+1\frac15(6^n-1)+1 if nn is divisible by 5, otherwise 15(6n−1)\frac15(6^n-1).

Thus, the probability is 15+45⋅6n\frac15+\frac{4}{5\cdot6^n} if nn is divisible by 5, otherwise it is 15−15⋅6n\frac15-\frac{1}{5\cdot6^n}.

Solution 3. For arbitrary positive integer kk denote by pkp_k the probability that the sum of values is kk. Define the generating function

f(x)=∑k=1∞pkxk=(x+x2+x3+x4+x5+x66)n.f(x)=\sum_{k=1}^{\infty}p_kx^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 ∑k=1∞p5k\sum\limits_{k=1}^{\infty}p_{5k}. Let ε=cos⁡2π5+isin⁡2π5\varepsilon=\cos\frac{2\pi}{5}+i\sin\frac{2\pi}{5} be the first 5th root of unity. Then

∑k=1∞p5k=f(1)+f(ε)+f(ε2)+f(ε3)+f(ε4)5.\sum_{k=1}^{\infty}p_{5k}=\frac{f(1)+f(\varepsilon)+f(\varepsilon^2)+f(\varepsilon^3)+f(\varepsilon^4)}{5}.

Obviously f(1)=1f(1)=1, and f(εj)=εjn6nf(\varepsilon^j)=\frac{\varepsilon^{jn}}{6^n} for j=1,2,3,4j=1,2,3,4. This implies that f(ε)+f(ε2)+f(ε3)+f(ε4)f(\varepsilon)+f(\varepsilon^2)+f(\varepsilon^3)+f(\varepsilon^4) is 46n\frac{4}{6^n} if nn is divisible by 5, otherwise it is −16n\frac{-1}{6^n}. Thus, ∑k=1∞p5k\sum\limits_{k=1}^{\infty}p_{5k} is 15+45⋅6n\frac15+\frac{4}{5\cdot6^n} if nn is divisible by 5, otherwise it is 15−15⋅6n\frac15-\frac{1}{5\cdot6^n}.

Transcribed from the official solutions, pages 1–2. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?