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 "2021 WSMO Team Round Problems/Problem 7"

(Created page with "==Problem== A frog makes one hop every minute on the first quadrant of the coordinate plane (this means that the frog's <math>x</math> and <math>y</math> coordinates are posit...")
 
 
Line 5: Line 5:
  
 
==Solution==
 
==Solution==
 +
Let <math>E_{(x,y)}</math> be the expected time it takes to get from <math>(x,y)</math> to <math>x+y=5.</math> By symmetry, we have <math>E_{(1,2)} = E_{(2,1)}</math> and <math>E_{(1,3)}=E_{(3,1)}</math>. Now, note that for all points satisfying <math>x+y=5,</math> we have <math>E_{(x,y)}=0.</math> Notably, <math>E_{(1,4)}=E_{(2,3)}=E_{(3,2)}=E_{(4,1)}=0.</math> Now, we apply probabilistic states.
 +
For <math>(1,1)</math>, we have
 +
\begin{align*}
 +
E_{(1,1)} &= \frac{1}{3}E_{(1,1)}+\frac{1}{3}E_{(1,2)}+\frac{1}{3}E_{(2,1)}+1 \implies\\
 +
\frac{2}{3}E_{(1,1)} &= \frac{2}{3}E_{(1,2)}+1 \implies\\
 +
E_{(1,2)} &= E_{(1,1)}-\frac{3}{2}.
 +
\end{align*}
 +
For <math>(1,2)</math>, we have,
 +
\begin{align*}
 +
E_{(1,2)} &= \frac{1}{4}E_{(1,2)}+\frac{1}{4}E_{(1,1)}+\frac{1}{4}E_{(2,2)}+\frac{1}{4}E_{(1,3)}+1 \implies\\
 +
\frac{3}{4}E_{(1,2)} &= \frac{1}{4}E_{(1,1)}+\frac{1}{4}E_{(2,2)}+\frac{1}{4}E_{(1,3)}+1 \implies\\
 +
E_{(1,2)} &= \frac{1}{3}E_{(1,1)}+\frac{1}{3}E_{(2,2)}+\frac{1}{3}E_{(1,3)}+\frac{4}{3}\tag{1}\\
 +
\end{align*}
 +
For <math>(1,3)</math>, we have,
 +
\begin{align*}
 +
E_{(1,3)} &= \frac{1}{4}E_{(1,3)}+\frac{1}{4}E_{(1,2)}+\frac{1}{4}E_{(3,2)}+\frac{1}{4}E_{(1,4)}+1 \implies\\
 +
\frac{3}{4}E_{(1,3)} &= \frac{1}{4}E_{(1,2)}+\frac{1}{4}\cdot0+\frac{1}{4}\cdot0+1\implies\\
 +
E_{(1,3)} &= \frac{1}{3}E_{(1,2)}+\frac{4}{3} \\
 +
&= \frac{1}{3}\left(E_{(1,1)}-\frac{3}{2}\right)+\frac{4}{3} \implies\\
 +
&= \frac{1}{3}E_{(1,1)}+\frac{5}{6}.
 +
\end{align*}
 +
For <math>(2,2)</math>, we have,
 +
\begin{align*}
 +
E_{(2,2)} &= \frac{1}{5}E_{(2,2)}+\frac{1}{5}E_{(1,2)}+\frac{1}{5}E_{(2,1)}+\frac{1}{5}E_{(2,3)}+\frac{1}{5}E_{(3,2)}+1. \implies\\
 +
\frac{4}{5}E_{(2,2)} &= \frac{1}{5}E_{(1,2)}+\frac{1}{5}E_{(1,2)}+\frac{1}{5}\cdot0+\frac{1}{5}\cdot0+1 \implies\\
 +
\frac{4}{5}E_{(2,2)} &= \frac{2}{5}E_{(1,2)}+1 \implies\\
 +
E_{(2,2)} &= \frac{1}{2}E_{(1,2)}+\frac{5}{4} \\
 +
&= \frac{1}{2}\left(E_{(1,1)}-\frac{3}{2}\right)+\frac{5}{4} \\
 +
&= \frac{1}{2}E_{(1,1)}+\frac{1}{2}.
 +
\end{align*}
 +
Subtituting the values of <math>E_{(1,2)},E_{(1,3)},</math> and <math>E_{(2,2)}</math> into equation (1), we have
 +
\begin{align*}
 +
E_{(1,1)}-\frac{3}{2}&=\frac{1}{3}E_{(1,1)}+\frac{1}{3}\left(\frac{1}{2}E_{(1,1)}+\frac{1}{2}\right)+\frac{1}{3}\left(\frac{1}{3}E_{(1,1)}+\frac{5}{6}\right)+\frac{4}{3} \\
 +
E_{(1,1)}-\frac{3}{2} &= \frac{11}{18}E_{(1,1)}+\frac{16}{9} \implies\\
 +
\frac{7}{18}E_{(1,1)} &= \frac{59}{18} \implies\\
 +
E_{(1,1)} &= \frac{56}{7} \implies 59+7 = \boxed{66}.
 +
\end{align*}
 +
~pinkpig

Latest revision as of 14:00, 9 September 2025

Problem

A frog makes one hop every minute on the first quadrant of the coordinate plane (this means that the frog's $x$ and $y$ coordinates are positive). The frog can hop up one unit, right one unit, left one unit, down one unit, or it can stay in place, and will always randomly choose a valid hop from these 5 directions (a valid hop is a hop that does not place the frog outside the first quadrant). Given that the frog starts at $(1,1)$, the expected number of minutes until the frog reaches the line $x+y=5$ can be expressed as $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m+n$.

Proposed by asdf334

Solution

Let $E_{(x,y)}$ be the expected time it takes to get from $(x,y)$ to $x+y=5.$ By symmetry, we have $E_{(1,2)} = E_{(2,1)}$ and $E_{(1,3)}=E_{(3,1)}$. Now, note that for all points satisfying $x+y=5,$ we have $E_{(x,y)}=0.$ Notably, $E_{(1,4)}=E_{(2,3)}=E_{(3,2)}=E_{(4,1)}=0.$ Now, we apply probabilistic states. For $(1,1)$, we have \begin{align*} E_{(1,1)} &= \frac{1}{3}E_{(1,1)}+\frac{1}{3}E_{(1,2)}+\frac{1}{3}E_{(2,1)}+1 \implies\\ \frac{2}{3}E_{(1,1)} &= \frac{2}{3}E_{(1,2)}+1 \implies\\ E_{(1,2)} &= E_{(1,1)}-\frac{3}{2}. \end{align*} For $(1,2)$, we have, \begin{align*} E_{(1,2)} &= \frac{1}{4}E_{(1,2)}+\frac{1}{4}E_{(1,1)}+\frac{1}{4}E_{(2,2)}+\frac{1}{4}E_{(1,3)}+1 \implies\\ \frac{3}{4}E_{(1,2)} &= \frac{1}{4}E_{(1,1)}+\frac{1}{4}E_{(2,2)}+\frac{1}{4}E_{(1,3)}+1 \implies\\ E_{(1,2)} &= \frac{1}{3}E_{(1,1)}+\frac{1}{3}E_{(2,2)}+\frac{1}{3}E_{(1,3)}+\frac{4}{3}\tag{1}\\ \end{align*} For $(1,3)$, we have, \begin{align*} E_{(1,3)} &= \frac{1}{4}E_{(1,3)}+\frac{1}{4}E_{(1,2)}+\frac{1}{4}E_{(3,2)}+\frac{1}{4}E_{(1,4)}+1 \implies\\ \frac{3}{4}E_{(1,3)} &= \frac{1}{4}E_{(1,2)}+\frac{1}{4}\cdot0+\frac{1}{4}\cdot0+1\implies\\ E_{(1,3)} &= \frac{1}{3}E_{(1,2)}+\frac{4}{3} \\ &= \frac{1}{3}\left(E_{(1,1)}-\frac{3}{2}\right)+\frac{4}{3} \implies\\ &= \frac{1}{3}E_{(1,1)}+\frac{5}{6}. \end{align*} For $(2,2)$, we have, \begin{align*} E_{(2,2)} &= \frac{1}{5}E_{(2,2)}+\frac{1}{5}E_{(1,2)}+\frac{1}{5}E_{(2,1)}+\frac{1}{5}E_{(2,3)}+\frac{1}{5}E_{(3,2)}+1. \implies\\ \frac{4}{5}E_{(2,2)} &= \frac{1}{5}E_{(1,2)}+\frac{1}{5}E_{(1,2)}+\frac{1}{5}\cdot0+\frac{1}{5}\cdot0+1 \implies\\ \frac{4}{5}E_{(2,2)} &= \frac{2}{5}E_{(1,2)}+1 \implies\\ E_{(2,2)} &= \frac{1}{2}E_{(1,2)}+\frac{5}{4} \\ &= \frac{1}{2}\left(E_{(1,1)}-\frac{3}{2}\right)+\frac{5}{4} \\ &= \frac{1}{2}E_{(1,1)}+\frac{1}{2}. \end{align*} Subtituting the values of $E_{(1,2)},E_{(1,3)},$ and $E_{(2,2)}$ into equation (1), we have \begin{align*} E_{(1,1)}-\frac{3}{2}&=\frac{1}{3}E_{(1,1)}+\frac{1}{3}\left(\frac{1}{2}E_{(1,1)}+\frac{1}{2}\right)+\frac{1}{3}\left(\frac{1}{3}E_{(1,1)}+\frac{5}{6}\right)+\frac{4}{3} \\ E_{(1,1)}-\frac{3}{2} &= \frac{11}{18}E_{(1,1)}+\frac{16}{9} \implies\\ \frac{7}{18}E_{(1,1)} &= \frac{59}{18} \implies\\ E_{(1,1)} &= \frac{56}{7} \implies 59+7 = \boxed{66}. \end{align*} ~pinkpig

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_WSMO_Team_Round_Problems/Problem_7&oldid=260118"