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 "2025 SSMO Accuracy Round Problems/Problem 6"

m (→‎Problem)
(→‎Solution)
 
Line 30: Line 30:
  
 
==Solution==
 
==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 <math>1\le i \le 9</math>, let <math>e_i</math> denote the expected number of moves Andy makes starting from cell <math>i</math> before reaching cell <math>2</math>. The value we seek is <math>e_1</math>.
 +
 +
Trivially, <math>e_2 = 0</math>. By symmetry, note that <math>e_3 = e_5</math>, <math>e_4 = e_8</math>, and <math>e_7 = e_9</math>. To set up our states equations, we consider all the possible ways Andy can move up to symmetry:
 +
<UL>
 +
<LI>If Andy is currently in cell <math>1</math>, he moves with probability <math>\tfrac{1}{2}</math> to each one of cells <math>3</math> and <math>5</math>;</LI>
 +
<LI>If Andy is currently in cell <math>3</math>, he moves with probability <math>\tfrac{1}{3}</math> to each one of cells <math>1</math>, <math>4</math>, and <math>6</math>;</LI>
 +
<LI>If Andy is currently in cell <math>4</math>, he moves with probability <math>\tfrac{1}{2}</math> to each one of cells <math>3</math> and <math>7</math>;</LI>
 +
<LI>If Andy is currently in cell <math>6</math>, he moves with probability <math>\tfrac{1}{4}</math> to each one of cells <math>3</math>, <math>5</math>, <math>7</math>, and <math>9</math>;</LI>
 +
<LI>If Andy is currently in cell <math>7</math>, he moves with probability <math>\tfrac{1}{3}</math> to each one of cells <math>4</math>, <math>6</math>, and <math>2</math>.</LI>
 +
</UL>
 +
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 <math>e_6 = e_4</math>. Substituting this as well as <math>e_1 = e_3+1</math> into the second and fifth equations lets us solve for both <math>e_3</math> and <math>e_7</math> in terms of <math>e_4</math>. 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 <math>e_3</math> and <math>e_7</math> into the third equation of our system, we obtain a linear equation in <math>e_4</math>, which we can solve to find that <math>e_4 = 15</math>. Thus, <math>e_1 = e_3 + 1 = (e_4 + 2) + 1 = \boxed{18}</math>.
 +
 +
~Sedro

Latest revision as of 16:37, 15 September 2025

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2025_SSMO_Accuracy_Round_Problems/Problem_6&oldid=260693"