Maths Olympiad Prep

Library / /9 of 13

Combinatorics Difficulty 5.0 AIME, harder Prove it United States

Problem:

Aerith rolls a fair die until she gets a roll that is greater than or equal to her previous roll. Find the expected number of times she will roll the die before stopping.

Solution

Solution:

The number of rolls is always at least 22 and at most 77. For there to be at least kk rolls, the first k1k-1 rolls have to be distinct and in decreasing order. The number of ways this can happen is (6k1)\binom{6}{k-1}, and the total number of ways to have k1k-1 rolls is 6k16^{k-1}. Thus, the expected value is

E(# of rolls )=P(1 roll )+P(2 rolls )++P(7 rolls )=1+(61)6+(62)62+(63)63+(64)64+(65)65+(66)66. \begin{aligned} E(\# \text{ of rolls }) & = P(\geq 1 \text{ roll }) + P(\geq 2 \text{ rolls }) + \cdots + P(\geq 7 \text{ rolls }) \\ & = 1 + \frac{\binom{6}{1}}{6} + \frac{\binom{6}{2}}{6^2} + \frac{\binom{6}{3}}{6^3} + \frac{\binom{6}{4}}{6^4} + \frac{\binom{6}{5}}{6^5} + \frac{\binom{6}{6}}{6^6} . \end{aligned}

By the binomial theorem, this is (1+16)62.52\left(1+\frac{1}{6}\right)^6 \approx 2.52.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.