Track / Stage 5 / 228 of 400 #1308 of 2444

Problem 1308

AIME late

Combinatorics Difficulty 5.5 Prove it Berkeley Math Circle: Monthly Contest 5 · United States

"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?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official 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$ .

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