Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2016 AIME I Problems/Problem 13"

(→‎See also)
m
 
(11 intermediate revisions by 7 users not shown)
Line 1: Line 1:
−
 
+
==Problem==
 +
Freddy the frog is jumping around the coordinate plane searching for a river, which lies on the horizontal line <math>y = 24</math>. A fence is located at the horizontal line <math>y = 0</math>. On each jump Freddy randomly chooses a direction parallel to one of the coordinate axes and moves one unit in that direction. When he is at a point where <math>y=0</math>, with equal likelihoods he chooses one of three directions where he either jumps parallel to the fence or jumps away from the fence, but he never chooses the direction that would have him cross over the fence to where <math>y < 0</math>. Freddy starts his search at the point <math>(0, 21)</math> and will stop once he reaches a point on the river. Find the expected number of jumps it will take Freddy to reach the river.
 
==Solution==
 
==Solution==
−
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 at a <math>y</math> coordinate of <math>y</math> until he reaches the line <math>y = 24</math>. So therefore we want to find <math>f(21)</math>.  
+
Clearly Freddy's <math>x</math>-coordinate is irrelevant, so we let <math>E(y)</math> be the expected value of the number of jumps it will take him to reach the river from a given <math>y</math>-coordinate. Observe that <math>E(24)=0</math>, and <cmath>E(y)=1+\frac{E(y+1)+E(y-1)+2E(y)}{4}</cmath> for all <math>y</math> such that <math>1\le y\le 23</math>. Also note that <math>E(0)=1+\frac{2E(0)+E(1)}{3}</math>. This gives <math>E(0)=E(1)+3</math>. Plugging this into the equation for <math>E(1)</math> gives that <cmath>E(1)=1+\frac{E(2)+3E(1)+3}{4},</cmath> or <math>E(1)=E(2)+7</math>. Iteratively plugging this in gives that <math>E(n)=E(n+1)+4n+3</math>. Thus <math>E(23)=E(24)+95</math>, <math>E(22)=E(23)+91=E(24)+186</math>, and <math>E(21)=E(22)+87=E(24)+273=\boxed{273}</math>.
  
−
So we have <math>f(24) = 0</math>. Suppose Freddy is at <math>y = n</math>. He has a <math>\frac{1}{2}</math> probability of moving horizontally, <math>\frac{1}{4}</math> chance of moving up and <math>\frac{1}{4}</math> chance of moving down. So we have
+
==Video Solution==
−
<cmath>f(n) = 1 + \frac{1}{2} f(n) + \frac{1}{4} f(n-1) + \frac{1}{4} f(n+1)</cmath>
+
https://youtu.be/T5F4e8NxfG0
−
So we get the recursion <math>2f(n) - f(n-1) - f(n+1) = 4</math>. Rearranging we see <math>f(n) - f(n-1) = f(n+1) - f(n) + 4</math>. That means the difference between consecutive terms goes down by <math>4</math> each time. So for convenience let's let <math>z = f(0)</math> and <math>d = f(1) - f(0)</math>. So that means
 
−
<cmath>f(k) = z + d + (d-4) + (d-8) + \cdots + (d - 4(k-1)) = z + kd - 2k(k-1)</cmath>
 
−
Yes, this is a quadratic. Now, notice that since there is a boundary, we have to give special care to <math>f(0)</math>. We have <math>f(0) = 1 + \frac{2}{3}f(0) + \frac{1}{3} f(1)</math> so this turns into <math>\frac{1}{3}z = 1 + \frac{1}{3}(z+d)</math> and this results in <math>d = -3</math>. So now we know
 
−
<cmath>f(k) = z - k - 2k^2 </cmath>
 
−
Now, we also have that <math>f(24) = 0</math> so that gives us <math>f(24) = z - 24 - 2 \cdot 576 = 0</math> so <math>z = 1176</math>. So now we know <math>f(k) = 1176 - k - 2k^2</math> so plugging in <math>k = 21</math> we get <math>f(21) = 1176 - 21 - 882 = \boxed{273}</math>
 
  
 +
==Video Solution==
 +
For those who want more explanation, here is a video explaining the solution: https://www.youtube.com/watch?v=jQCGkOGMlFQ
 
== See also ==
 
== See also ==
−
{{AIME box|year=2016|n=I|before=12|num-a=14}}
+
{{AIME box|year=2016|n=I|num-b=12|num-a=14}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 19:41, 14 May 2022

Problem

Freddy the frog is jumping around the coordinate plane searching for a river, which lies on the horizontal line $y = 24$. A fence is located at the horizontal line $y = 0$. On each jump Freddy randomly chooses a direction parallel to one of the coordinate axes and moves one unit in that direction. When he is at a point where $y=0$, with equal likelihoods he chooses one of three directions where he either jumps parallel to the fence or jumps away from the fence, but he never chooses the direction that would have him cross over the fence to where $y < 0$. Freddy starts his search at the point $(0, 21)$ and will stop once he reaches a point on the river. Find the expected number of jumps it will take Freddy to reach the river.

Solution

Clearly Freddy's $x$-coordinate is irrelevant, so we let $E(y)$ be the expected value of the number of jumps it will take him to reach the river from a given $y$-coordinate. Observe that $E(24)=0$, and \[E(y)=1+\frac{E(y+1)+E(y-1)+2E(y)}{4}\] for all $y$ such that $1\le y\le 23$. Also note that $E(0)=1+\frac{2E(0)+E(1)}{3}$. This gives $E(0)=E(1)+3$. Plugging this into the equation for $E(1)$ gives that \[E(1)=1+\frac{E(2)+3E(1)+3}{4},\] or $E(1)=E(2)+7$. Iteratively plugging this in gives that $E(n)=E(n+1)+4n+3$. Thus $E(23)=E(24)+95$, $E(22)=E(23)+91=E(24)+186$, and $E(21)=E(22)+87=E(24)+273=\boxed{273}$.

Video Solution

https://youtu.be/T5F4e8NxfG0

Video Solution

For those who want more explanation, here is a video explaining the solution: https://www.youtube.com/watch?v=jQCGkOGMlFQ

See also

2016 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 12 		Followed by
Problem 14
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2016_AIME_I_Problems/Problem_13&oldid=173945"