2021 WSMO Team Round Problems/Problem 7
Problem
A frog makes one hop every minute on the first quadrant of the coordinate plane (this means that the frog's 
and 
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 
, the expected number of minutes until the frog reaches the line 
can be expressed as 
, where 
and 
are relatively prime positive integers. Find 
.
Proposed by asdf334
Solution
Let 
be the expected time it takes to get from 
to 
By symmetry, we have 
and 
. Now, note that for all points satisfying 
we have 
Notably, 
Now, we apply probabilistic states.
For , 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 
, 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 
, 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 
, 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 
and 
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
