Maths Olympiad Prep

Library / /631 of 740

Algebra Difficulty 5.4 AIME, harder Prove it United States

Problem:

Gary plays the following game with a fair nn-sided die whose faces are labeled with the positive integers between 11 and nn, inclusive: if n=1n=1, he stops; otherwise he rolls the die, and starts over with a kk-sided die, where kk is the number his nn-sided die lands on. (In particular, if he gets k=1k=1, he will stop rolling the die.) If he starts out with a 66-sided die, what is the expected number of rolls he makes?

Solution

Solution:

Let ana_n be the expected number of rolls starting with an nn-sided die. We see immediately that a1=0a_1 = 0, and an=1+1ni=1naia_n = 1 + \frac{1}{n} \sum_{i=1}^{n} a_i for n>1n > 1. Thus a2=2a_2 = 2, and for n3n \geq 3, an=1+1nan+n1n(an11)a_n = 1 + \frac{1}{n} a_n + \frac{n-1}{n}(a_{n-1} - 1), or an=an1+1n1a_n = a_{n-1} + \frac{1}{n-1}. Thus an=1+i=1n11ia_n = 1 + \sum_{i=1}^{n-1} \frac{1}{i} for n2n \geq 2, so a6=1+60+30+20+15+1260=19760a_6 = 1 + \frac{60 + 30 + 20 + 15 + 12}{60} = \frac{197}{60}.

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.