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 Fall AMC 12B Problems/Problem 17"

(Created page with "==Problem== A bug starts at a vertex of a grid made of equilateral triangles of side length <math>1</math>. At each step the bug moves in one of the <math>6</math> possible d...")
 
Line 6: Line 6:
 
\frac{4}{27} \qquad\textbf{(E)}\ \frac{1}{16}</math>
 
\frac{4}{27} \qquad\textbf{(E)}\ \frac{1}{16}</math>
  
−
==Solution==
+
==Solution 1==
 
Let <math>S(n)</math> be the number of paths of <math>n</math> moves such that the bug never will have been more than <math>1</math> unit away from the starting position. Clearly, by symmetry, there are two possible states here, the bug being on the center and the bug being on one of the vertices of the unit hexagon around the center. Let <math>C(n)</math> be the number of paths with the aforementioned restriction that end on the center. Let <math>V(n)</math> be the number of paths with the aforementioned restriction that end on a vertex of the surrounding unit hexagon. We have <math>S(n) = 6C(n-1) + 3V(n-1),</math> since from the center, there are <math>6</math> possible points to land to and from a vertex there are <math>3</math> possible points to land to (the two adjacent vertices and the center). We also have <math>C(n) = V(n-1)</math>, since to get to the center the bug must have come from a vertex, and <math>V(n) = 2V(n-1) + 6C(n-1),</math> since from a vertex there are two vertices to move to, and from the center there are <math>6</math> vertices to move to. We can construct a recursion table using the base cases <math>V(1) = 6</math> and <math>C(1) = 0</math> and our recursive rules for <math>C(n)</math> and <math>V(n)</math> as follows:  
 
Let <math>S(n)</math> be the number of paths of <math>n</math> moves such that the bug never will have been more than <math>1</math> unit away from the starting position. Clearly, by symmetry, there are two possible states here, the bug being on the center and the bug being on one of the vertices of the unit hexagon around the center. Let <math>C(n)</math> be the number of paths with the aforementioned restriction that end on the center. Let <math>V(n)</math> be the number of paths with the aforementioned restriction that end on a vertex of the surrounding unit hexagon. We have <math>S(n) = 6C(n-1) + 3V(n-1),</math> since from the center, there are <math>6</math> possible points to land to and from a vertex there are <math>3</math> possible points to land to (the two adjacent vertices and the center). We also have <math>C(n) = V(n-1)</math>, since to get to the center the bug must have come from a vertex, and <math>V(n) = 2V(n-1) + 6C(n-1),</math> since from a vertex there are two vertices to move to, and from the center there are <math>6</math> vertices to move to. We can construct a recursion table using the base cases <math>V(1) = 6</math> and <math>C(1) = 0</math> and our recursive rules for <math>C(n)</math> and <math>V(n)</math> as follows:  
 
<cmath>\begin{tabular}{c|c|c} n & V(n) & C(n) \\ \hline
 
<cmath>\begin{tabular}{c|c|c} n & V(n) & C(n) \\ \hline
Line 17: Line 17:
  
 
-fidgetboss_4000
 
-fidgetboss_4000
 +
 +
== Solution 2 ==
 +
We use <math>\left( n , t \right)</math> to denote the bug's current state.
 +
 +
The first argument <math>n</math> denotes the bug's current position.
 +
We use <math>n = 0</math> to denote the bug's starting point.
 +
We use <math>n = 1</math> to denote any point whose distance to the bug's starting point is 1.
 +
 +
The second argument <math>t</math> denotes the remaining number of moves the bug has.
 +
 +
For <math>n = 0</math> and <math>t \geq 1</math>,
 +
<cmath>
 +
\begin{align*}
 +
P \left( 0 , t \right) & = P \left( 1 , t - 1 \right) .
 +
\end{align*}
 +
</cmath>
 +
 +
For <math>n = 1</math> and <math>t \geq 1</math>,
 +
<cmath>
 +
\begin{align*}
 +
P \left( 1 , t \right) & = \frac{1}{6} P \left( 0 ,  t - 1 \right)
 +
+ \frac{1}{3} P \left( 1 , t - 1 \right)  .
 +
\end{align*}
 +
</cmath>
 +
 +
For <math>n \in \left\{ 0 , 1 \right\}</math> and <math>t = 0</math>,
 +
<cmath>
 +
\begin{align*}
 +
P \left( n , 0 \right) & = 1 .
 +
\end{align*}
 +
</cmath>
 +
 +
We solve this recursive equation by using backward induction.
 +
 +
We get
 +
<cmath>
 +
\[
 +
P \left( 0 , 1 \right) = 1 , \hspace{1cm}
 +
P \left( 1 , 1 \right) = \frac{1}{2}
 +
\]
 +
</cmath>
 +
and
 +
<cmath>
 +
\[
 +
P \left( 0 , 2 \right) = \frac{1}{2} , \hspace{1cm}
 +
P \left( 1 , 2 \right) = \frac{1}{3}
 +
\]
 +
</cmath>
 +
and
 +
<cmath>
 +
\[
 +
P \left( 0 , 3 \right) = \frac{1}{3} , \hspace{1cm}
 +
P \left( 1 , 3 \right) = \frac{7}{36}
 +
\]
 +
</cmath>
 +
and
 +
<cmath>
 +
\[
 +
P \left( 1 , 4 \right) = \frac{13}{108}
 +
\]
 +
</cmath>
 +
and
 +
<cmath>
 +
\[
 +
P \left( 0 , 5 \right) = \frac{13}{108} .
 +
\]
 +
</cmath>
 +
 +
Therefore, the answer is <math>\boxed{\textbf{(A) }\frac{13}{108}}</math>.
 +
 +
~Steven Chen (www.professorchenedu.com)

Revision as of 00:17, 26 November 2021

Problem

A bug starts at a vertex of a grid made of equilateral triangles of side length $1$. At each step the bug moves in one of the $6$ possible directions along the grid lines randomly and independently with equal probability. What is the probability that after $5$ moves the bug never will have been more than $1$ unit away from the starting position?

$\textbf{(A)}\ \frac{13}{108} \qquad\textbf{(B)}\ \frac{7}{54} \qquad\textbf{(C)}\ \frac{29}{216} \qquad\textbf{(D)}\ \frac{4}{27} \qquad\textbf{(E)}\ \frac{1}{16}$

Solution 1

Let $S(n)$ be the number of paths of $n$ moves such that the bug never will have been more than $1$ unit away from the starting position. Clearly, by symmetry, there are two possible states here, the bug being on the center and the bug being on one of the vertices of the unit hexagon around the center. Let $C(n)$ be the number of paths with the aforementioned restriction that end on the center. Let $V(n)$ be the number of paths with the aforementioned restriction that end on a vertex of the surrounding unit hexagon. We have $S(n) = 6C(n-1) + 3V(n-1),$ since from the center, there are $6$ possible points to land to and from a vertex there are $3$ possible points to land to (the two adjacent vertices and the center). We also have $C(n) = V(n-1)$, since to get to the center the bug must have come from a vertex, and $V(n) = 2V(n-1) + 6C(n-1),$ since from a vertex there are two vertices to move to, and from the center there are $6$ vertices to move to. We can construct a recursion table using the base cases $V(1) = 6$ and $C(1) = 0$ and our recursive rules for $C(n)$ and $V(n)$ as follows: \[\begin{tabular}{c|c|c} n & V(n) & C(n) \\ \hline 1 & 6 & 0 \\ 2 & 12 & 6 \\ 3 & 60 & 12 \\ 4 & 192 & 60 \\ \end{tabular}\] Then, $S(5) = 6C(4) + 3V(4) = 6 \cdot 60 + 3 \cdot 192 = 936,$ and the desired probability is thus $\frac{936}{6^5} = \boxed{\frac{13}{108}}.$

-fidgetboss_4000

Solution 2

We use $\left( n , t \right)$ to denote the bug's current state.

The first argument $n$ denotes the bug's current position. We use $n = 0$ to denote the bug's starting point. We use $n = 1$ to denote any point whose distance to the bug's starting point is 1.

The second argument $t$ denotes the remaining number of moves the bug has.

For $n = 0$ and $t \geq 1$, \begin{align*} P \left( 0 , t \right) & = P \left( 1 , t - 1 \right) . \end{align*}

For $n = 1$ and $t \geq 1$, \begin{align*} P \left( 1 , t \right) & = \frac{1}{6} P \left( 0 , t - 1 \right) + \frac{1}{3} P \left( 1 , t - 1 \right) . \end{align*}

For $n \in \left\{ 0 , 1 \right\}$ and $t = 0$, \begin{align*} P \left( n , 0 \right) & = 1 . \end{align*}

We solve this recursive equation by using backward induction.

We get \[ P \left( 0 , 1 \right) = 1 , \hspace{1cm} P \left( 1 , 1 \right) = \frac{1}{2} \] and \[ P \left( 0 , 2 \right) = \frac{1}{2} , \hspace{1cm} P \left( 1 , 2 \right) = \frac{1}{3} \] and \[ P \left( 0 , 3 \right) = \frac{1}{3} , \hspace{1cm} P \left( 1 , 3 \right) = \frac{7}{36} \] and \[ P \left( 1 , 4 \right) = \frac{13}{108} \] and \[ P \left( 0 , 5 \right) = \frac{13}{108} . \]

Therefore, the answer is $\boxed{\textbf{(A) }\frac{13}{108}}$.

~Steven Chen (www.professorchenedu.com)

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_Fall_AMC_12B_Problems/Problem_17&oldid=166488"