Competition problem — Combinatorics

Library / /19 of 22

Combinatorics Difficulty 5.5 AIME, harder Prove it United States

Problem:

"Very Frustrating Game" has six levels. When a level is attempted, the player goes to the next level if they succeed, but back to the previous level if they fail (or if they are on level 1 they restart).

a) Aerith has a $\frac{1}{2}$ success rate on all levels. How many level attempts on average would it take her to complete the game?

b) Bob has a $\frac{1}{3}$ success rate on all levels. How many level attempts on average would it take him to complete the game?

Solution

Solution:

a.
Let $A(x) = 42 - (x + x^{2})$ . One can check that $A(x) = 1 + \frac{1}{2} A(x+1) + \frac{1}{2} A(x-1)$ , that $A(0) = A(-1)$ , and that $A(6) = 0$ . The answer when starting on level $n+1$ is therefore $A(n)$ . Plugging in $n=0$ gives $42$ .

b.
Let $B(x) = 360 - 3\left(2(2^{x} - 1) - x\right)$ . One can check that $B(x) = 1 + \frac{1}{3} B(x+1) + \frac{2}{3} B(x-1)$ , that $B(0) = B(-1)$ , and that $B(6) = 0$ . The answer when starting on level $n+1$ is therefore $B(n)$ . Plugging in $n=0$ gives $360$ .

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.