2016 AIME I Problems/Problem 13

Revision as of 15:35, 4 March 2016 by Fclvbfm934 (talk | contribs) (Created page with "Notice that we don't really care about what the <math>x</math>-coordinate of the frog is. So let's let <math>f(y)</math> denote the expected number of times Freddy will jump a...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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}$