2016 AIME I Problems/Problem 13

Solution

Notice that we don't really care about what the $x$ -coordinate of the frog is. So let's let $f(y)$ denote the expected number of times Freddy will jump at a $y$ coordinate of $y$ until he reaches the line $y = 24$ . So therefore we want to find $f(21)$ .

So we have $f(24) = 0$ . Suppose Freddy is at $y = n$ . He has a $\frac{1}{2}$ probability of moving horizontally, $\frac{1}{4}$ chance of moving up and $\frac{1}{4}$ chance of moving down. So we have $f(n) = 1 + \frac{1}{2} f(n) + \frac{1}{4} f(n-1) + \frac{1}{4} f(n+1)$ So we get the recursion $2f(n) - f(n-1) - f(n+1) = 4$ . Rearranging we see $f(n) - f(n-1) = f(n+1) - f(n) + 4$ . That means the difference between consecutive terms goes down by $4$ each time. So for convenience let's let $z = f(0)$ and $d = f(1) - f(0)$ . So that means $f(k) = z + d + (d-4) + (d-8) + \cdots + (d - 4(k-1)) = z + kd - 2k(k-1)$ Yes, this is a quadratic. Now, notice that since there is a boundary, we have to give special care to $f(0)$ . We have $f(0) = 1 + \frac{2}{3}f(0) + \frac{1}{3} f(1)$ so this turns into $\frac{1}{3}z = 1 + \frac{1}{3}(z+d)$ and this results in $d = -3$ . So now we know $f(k) = z - k - 2k^2$ Now, we also have that $f(24) = 0$ so that gives us $f(24) = z - 24 - 2 \cdot 576 = 0$ so $z = 1176$ . So now we know $f(k) = 1176 - k - 2k^2$ so plugging in $k = 21$ we get $f(21) = 1176 - 21 - 882 = \boxed{273}$

2016 AIME I (Problems • Answer Key • Resources)
Preceded by [[2016 AIME I Problems/Problem {{{num-b}}}\|Problem {{{num-b}}}]]	Followed by Problem 14
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search

2016 AIME I Problems/Problem 13

Solution

See also