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 AIME II Problems/Problem 8"

(→‎Solution 1 (Recursion))
(→‎Solution 1 (Recursion))
Line 13: Line 13:
 
* Let <math>N(k,\text{TT})</math> be the number of ways to make a sequence of <math>k</math> moves, where the last move is from the top face to the top face.
 
* Let <math>N(k,\text{TT})</math> be the number of ways to make a sequence of <math>k</math> moves, where the last move is from the top face to the top face.
  
−
<b>Paragraph analysis in progress</b>
+
<b>... Paragraph analysis in progress ...</b>
  
−
<b>Graph analysis in progress</b>
+
<b>... Graph analysis in progress ...</b>
  
−
<b>Equation analysis in progress</b>
+
<b>... Equation analysis in progress ...</b>
  
 
<cmath>\begin{array}{c||c|c|c|c|c|c|c|c}   
 
<cmath>\begin{array}{c||c|c|c|c|c|c|c|c}   
−
\textbf{\# of Steps} & \boldsymbol{1} & \boldsymbol{2} & \boldsymbol{3} & \boldsymbol{4} & \boldsymbol{5} & \boldsymbol{6} & \boldsymbol{7} & \boldsymbol{8} \\ \hline \hline
+
&&&&&&&& \\ [-2.25ex]
−
\textbf{BB} &2&&&&&&& \\ \hline
+
\textbf{\# of Steps} & \boldsymbol{1} & \boldsymbol{2} & \boldsymbol{3} & \boldsymbol{4} & \boldsymbol{5} & \boldsymbol{6} & \boldsymbol{7} & \boldsymbol{8} \\ [0.5ex]
−
\textbf{BT} &1&&&&&&& \\ \hline  
+
\hline \hline
−
\textbf{TB} &0&&&&&&& \\ \hline   
+
&&&&&&&& \\ [-2.25ex]
−
\textbf{TT} &0&&&&&&&
+
N(k,\textbf{BB}) &2&&&&&&& \\ \hline  
 +
&&&&&&&& \\ [-2.25ex]
 +
N(k,\textbf{BT}) &1&&&&&&& \\ \hline  
 +
&&&&&&&& \\ [-2.25ex]
 +
N(k,\textbf{TB}) &0&&&&&&& \\ \hline
 +
&&&&&&&& \\ [-2.25ex]    
 +
N(k,\textbf{TT}) &0&&&&&&& \\ [-5ex]
 
\end{array}</cmath>
 
\end{array}</cmath>
  
Line 30: Line 36:
  
 
<cmath>\begin{array}{c||c|c|c|c|c|c|c|c}   
 
<cmath>\begin{array}{c||c|c|c|c|c|c|c|c}   
−
\textbf{\# of Steps} & \boldsymbol{1} & \boldsymbol{2} & \boldsymbol{3} & \boldsymbol{4} & \boldsymbol{5} & \boldsymbol{6} & \boldsymbol{7} & \boldsymbol{8} \\ \hline \hline  
+
&&&&&&&& \\ [-2.25ex]
−
\textbf{BB} &2&2&2&6&18&38&66&118 \\ \hline   
+
\textbf{\# of Steps} & \boldsymbol{1} & \boldsymbol{2} & \boldsymbol{3} & \boldsymbol{4} & \boldsymbol{5} & \boldsymbol{6} & \boldsymbol{7} & \boldsymbol{8} \\ [0.5ex]
−
\textbf{BT} &1&2&2&2&6&18&38&66 \\ \hline  
+
\hline \hline
−
\textbf{TB} &0&0&2&6&10&14&26&62 \\ \hline   
+
&&&&&&&& \\ [-2.25ex]
−
\textbf{TT} &0&2&6&10&14&26&62&138   
+
N(k,\textbf{BB}) &2&2&2&6&18&38&66&118 \\ \hline   
 +
N(k,\textbf{BT}) &1&2&2&2&6&18&38&66 \\ \hline  
 +
N(k,\textbf{TB}) &0&0&2&6&10&14&26&62 \\ \hline   
 +
N(k,\textbf{TT}) &0&2&6&10&14&26&62&138   
 
\end{array}</cmath>
 
\end{array}</cmath>
  

Revision as of 18:52, 29 March 2021

Problem

An ant makes a sequence of moves on a cube where a move consists of walking from one vertex to an adjacent vertex along an edge of the cube. Initially the ant is at a vertex of the bottom face of the cube and chooses one of the three adjacent vertices to move to as its first move. For all moves after the first move, the ant does not return to its previous vertex, but chooses to move to one of the other two adjacent vertices. All choices are selected at random so that each of the possible moves is equally likely. The probability that after exactly 8 moves that ant is at a vertex of the top face on the cube is $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

Solution 1 (Recursion)

For all positive integers $k:$

  • Let $N(k,\text{BB})$ be the number of ways to make a sequence of $k$ moves, where the last move is from the bottom face to the bottom face.
  • Let $N(k,\text{BT})$ be the number of ways to make a sequence of $k$ moves, where the last move is from the bottom face to the top face.
  • Let $N(k,\text{TB})$ be the number of ways to make a sequence of $k$ moves, where the last move is from the top face to the bottom face.
  • Let $N(k,\text{TT})$ be the number of ways to make a sequence of $k$ moves, where the last move is from the top face to the top face.

... Paragraph analysis in progress ...

... Graph analysis in progress ...

... Equation analysis in progress ...

\[\begin{array}{c||c|c|c|c|c|c|c|c} &&&&&&&& \\ [-2.25ex] \textbf{\# of Steps} & \boldsymbol{1} & \boldsymbol{2} & \boldsymbol{3} & \boldsymbol{4} & \boldsymbol{5} & \boldsymbol{6} & \boldsymbol{7} & \boldsymbol{8} \\ [0.5ex] \hline \hline &&&&&&&& \\ [-2.25ex] N(k,\textbf{BB}) &2&&&&&&& \\ \hline &&&&&&&& \\ [-2.25ex] N(k,\textbf{BT}) &1&&&&&&& \\ \hline &&&&&&&& \\ [-2.25ex] N(k,\textbf{TB}) &0&&&&&&& \\ \hline &&&&&&&& \\ [-2.25ex] N(k,\textbf{TT}) &0&&&&&&& \\ [-5ex] \end{array}\]

We can keep doing this process, until the 8th step.

\[\begin{array}{c||c|c|c|c|c|c|c|c} &&&&&&&& \\ [-2.25ex] \textbf{\# of Steps} & \boldsymbol{1} & \boldsymbol{2} & \boldsymbol{3} & \boldsymbol{4} & \boldsymbol{5} & \boldsymbol{6} & \boldsymbol{7} & \boldsymbol{8} \\ [0.5ex] \hline \hline &&&&&&&& \\ [-2.25ex] N(k,\textbf{BB}) &2&2&2&6&18&38&66&118 \\ \hline N(k,\textbf{BT}) &1&2&2&2&6&18&38&66 \\ \hline N(k,\textbf{TB}) &0&0&2&6&10&14&26&62 \\ \hline N(k,\textbf{TT}) &0&2&6&10&14&26&62&138 \end{array}\]

Since we want the fraction when the ant is on top, $\dfrac{204}{384}=\dfrac{17}{32}$. Our answer is $17 + 32 = \boxed{049}.$

~Arcticturn (Primary)

~MRENTHUSIASM (Secondary) EDITING (RENOVATION) IN PROGRESS. A MILLION THANKS FOR LEAVING THIS SOLUTION ALONE.

Solution 2 (Casework)

On each move, we can either stay on the level we previously were (stay on the bottom/top) or switch levels (go from top to bottom and vise versa). Since we start on the bottom, ending on the top means that we will have to switch an odd number of times; since we cannot switch twice in a row, over an eight-move period we can either make one or three switches. Furthermore, once we switch to a level we can choose one of two directions of traveling on that level: clockwise or counterclockwise (since we can't go back to our previous move, our first move on the level after switching determines our direction).

  1. Case 1: one switch. Our one switch can either happen at the start/end of our moves, or in the middle. There are $4 + 24 = 28$ ways to do this, outlined below.
    1. Subcase 1: switch happens at ends. If our first move is a switch, then there are two ways to determine the direction we travel along the top layer. Multiply by 2 to count for symmetry (last move is a switch) so this case yields $2^2 = 4$ possibilities.
    2. Subcase 2: switch happens in the middle. There are six places for the switch to happen; the switch breaks the sequences of moves into two chains, with each having 2 ways to choose their direction of travel. This case yields $6 \cdot 2^2 = 24$ possibilities.
  2. Case 2: three switches. Either two, one, or none of our switches occur at the start/end of our moves. There are $16 + 96 + 64 = 176$ ways to do this, outlined below. (Keep in mind we can't have two switches in a row.)
    1. Subcase 1: start and end with a switch. Since our third switch can't be in moves 2 or 7, there are four ways to place our switch, breaking our sequence into two chains. This case yields $4 \cdot 2^2 = 16$ possibilities.
    2. Subcase 2: one of our switches is at the start/end. WLOG our first move is a switch; moves 2 and 8 cannot be switches. We can choose 2 from any of the remaining 5 moves to be switches, but we have to subtract the 4 illegal cases where the two switches are in a row (3-4, 4-5, 5-6, 6-7). These three switches break our sequence into three chains; accounting for symmetry this case yields $2\left(\binom{5}{2} - 4\right) \cdot 2^3 = 96$ possibilities.
    3. Subcase 3: all our switches are in the middle. We choose 3 from any of the 6 middle moves to be our switches, but have to subtract the cases where at least two of them are in a row. If at least two switches are in a row, there are five places for the group of 2 and four places for the third switch; however this overcounts the case where all three are in a row, which has 4 possibilities. These three switches break our sequence into four chains, so this case yields $\left(\binom{6}{3} - 5 \cdot 4 + 4\right) \cdot 2^4 = 64$ possibilities.

Our probability is then $\frac{176 + 28}{3 \cdot 2^7} = \frac{17}{32} \iff \boxed{049}$.

See also

2021 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 7 		Followed by
Problem 9
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_AIME_II_Problems/Problem_8&oldid=150573"