uniolympiads English

IMC 1999, Ημέρα 2, Θέμα 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?

Πρωτότυπο από το επίσημο 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)

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

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}.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 1–2. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;