2025 SSMO Accuracy Round Problems/Problem 6

Problem

Andy the ant starts at the square labeled $1$ . On each move Andy moves to any orthogonal square (a square with which his current square shares a side). What is the expected number of moves before Andy is in the square labeled $2$ ? $[asy] unitsize(1cm); int[][] grid = { {0, 0, 0}, {0, 0, 0}, {0, 0, 0} }; grid[0][0] = 1; grid[2][2] = 2; for (int i = 0; i <= 3; ++i) { draw((0,i)--(3,i),black); draw((i,0)--(i,3),black); } for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { if (grid[i][j] != 0) { } } } label("$1$",(0.5,0.5)); label("$2$",(2.5,2.5)); [/asy]$

Solution

$[asy] unitsize(1cm); int[][] grid = { {0, 0, 0}, {0, 0, 0}, {0, 0, 0} }; grid[0][0] = 1; grid[2][2] = 2; for (int i = 0; i <= 3; ++i) { draw((0,i)--(3,i),black); draw((i,0)--(i,3),black); } for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { if (grid[i][j] != 0) { } } } label("$1$",(0.5,0.5)); label("$2$",(2.5,2.5)); label("$3$",(1.5,0.5)); label("$4$",(2.5,0.5)); label("$5$",(0.5,1.5)); label("$6$",(1.5,1.5)); label("$7$",(2.5,1.5)); label("$8$",(0.5,2.5)); label("$9$",(1.5,2.5)); [/asy]$

Label each cell of the grid as shown. We proceed via states; for each integer $1\le i \le 9$ , let $e_i$ denote the expected number of moves Andy makes starting from cell $i$ before reaching cell $2$ . The value we seek is $e_1$ .

Trivially, $e_2 = 0$ . By symmetry, note that $e_3 = e_5$ , $e_4 = e_8$ , and $e_7 = e_9$ . To set up our states equations, we consider all the possible ways Andy can move up to symmetry:

If Andy is currently in cell $1$ , he moves with probability $\tfrac{1}{2}$ to each one of cells $3$ and $5$ ;
If Andy is currently in cell $3$ , he moves with probability $\tfrac{1}{3}$ to each one of cells $1$ , $4$ , and $6$ ;
If Andy is currently in cell $4$ , he moves with probability $\tfrac{1}{2}$ to each one of cells $3$ and $7$ ;
If Andy is currently in cell $6$ , he moves with probability $\tfrac{1}{4}$ to each one of cells $3$ , $5$ , $7$ , and $9$ ;
If Andy is currently in cell $7$ , he moves with probability $\tfrac{1}{3}$ to each one of cells $4$ , $6$ , and $2$ .

Therefore, we have the following five equations: \begin{align*} e_1 &= e_3 + 1 \\ e_3 &= \tfrac{1}{3}e_1 + \tfrac{1}{3}e_4 + \tfrac{1}{3}e_6 + 1 \\ e_4 &= \tfrac{1}{2}e_3 + \tfrac{1}{2}e_7 + 1 \\ e_6 &= \tfrac{1}{2}e_3 + \tfrac{1}{2}e_7 + 1 \\ e_7 &= \tfrac{1}{3}e_4 + \tfrac{1}{3}e_6 + 1. \end{align*} Note that $e_6 = e_4$ . Substituting this as well as $e_1 = e_3+1$ into the second and fifth equations lets us solve for both $e_3$ and $e_7$ in terms of $e_4$ . After simplification, we obtain \begin{align*} e_3 &= e_4+2\\ e_7 &= \tfrac{2}{3}e_4 + 1. \end{align*} Plugging in these expressions for $e_3$ and $e_7$ into the third equation of our system, we obtain a linear equation in $e_4$ , which we can solve to find that $e_4 = 15$ . Thus, $e_1 = e_3 + 1 = (e_4 + 2) + 1 = \boxed{18}$ .

~Sedro

Page

Toolbox

Search

2025 SSMO Accuracy Round Problems/Problem 6

Problem

Solution