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"

m (→‎Solution 1 (Recursion))
m
 
(74 intermediate revisions by 7 users not shown)
Line 1: Line 1:
 
==Problem==
 
==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 <math>\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m + n.</math>
+
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 <math>8</math> moves that ant is at a vertex of the top face on the cube is <math>\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m + n.</math>
  
−
==Solution 1 (Recursion)==
+
==Solution 1 (Four-Variable Recursion)==
−
For all positive integers <math>k:</math>
+
For all positive integers <math>k,</math> let
  
−
* Let <math>N(k,\text{BB})</math> be the number of ways to make a sequence of exactly <math>k</math> moves, where the last move is from the bottom face to the bottom face.
+
* <math>N(k,\mathrm{BB})</math> be the number of ways to make a sequence of exactly <math>k</math> moves, where the last move is from the bottom face to the bottom face.
  
−
* Let <math>N(k,\text{BT})</math> be the number of ways to make a sequence of exactly <math>k</math> moves, where the last move is from the bottom face to the top face.
+
* <math>N(k,\mathrm{BT})</math> be the number of ways to make a sequence of exactly <math>k</math> moves, where the last move is from the bottom face to the top face.
  
−
* Let <math>N(k,\text{TB})</math> be the number of ways to make a sequence of exactly <math>k</math> moves, where the last move is from the top face to the bottom face.
+
* <math>N(k,\mathrm{TB})</math> be the number of ways to make a sequence of exactly <math>k</math> moves, where the last move is from the top face to the bottom face.
  
−
* Let <math>N(k,\text{TT})</math> be the number of ways to make a sequence of exactly <math>k</math> moves, where the last move is from the top face to the top face.
+
* <math>N(k,\mathrm{TT})</math> be the number of ways to make a sequence of exactly <math>k</math> moves, where the last move is from the top face to the top face.
  
−
The base cases are <math>N(1,\text{BB})=2</math> and <math>N(1,\text{BT})=1.</math>  
+
The base case occurs at <math>k=1,</math> from which <math>\left(N(1,\mathrm{BB}),N(1,\mathrm{BT}),N(1,\mathrm{TB}),N(1,\mathrm{TT})\right)=(2,1,0,0).</math>  
  
−
Suppose the ant made exactly <math>k</math> moves. We will perform casework on its last move:
+
Suppose the ant makes exactly <math>k</math> moves for some <math>k\geq2.</math> We perform casework on its last move:
 
<ol style="margin-left: 1.5em;">
 
<ol style="margin-left: 1.5em;">
−
   <li>If the ant's last move is from the bottom face to the bottom face, then its next move has</li><p>
+
   <li>If its last move is from the bottom face to the bottom face, then its next move has</li><p>
−
<ul style="margin-left: 1.5em; circle">
+
<ul style="margin-left: 1.5em; list-style-type: circle">
 
   <li><math>1</math> way to move from the bottom face to the bottom face.</li><p>
 
   <li><math>1</math> way to move from the bottom face to the bottom face.</li><p>
 
   <li><math>1</math> way to move from the bottom face to the top face.</li><p>
 
   <li><math>1</math> way to move from the bottom face to the top face.</li><p>
 
</ul>
 
</ul>
−
   <li>If the ant's last move is from the bottom face to the top face, then its next move has <math>2</math> ways to move from the top face to the top face.</li><p>
+
   <li>If its last move is from the bottom face to the top face, then its next move has <math>2</math> ways to move from the top face to the top face.</li><p>
−
   <li>If the ant's last move is from the top face to the bottom face, then its next move has <math>2</math> ways to move from the bottom face to the bottom face.</li><p>
+
   <li>If its last move is from the top face to the bottom face, then its next move has <math>2</math> ways to move from the bottom face to the bottom face.</li><p>
−
   <li>If the ant's last move is from the top face to the top face, then its next move has<p>
+
   <li>If its last move is from the top face to the top face, then its next move has<p>
−
<ul style="margin-left: 1.5em; circle">
+
<ul style="margin-left: 1.5em; list-style-type: circle">
 
   <li><math>1</math> way to move from the top face to the bottom face.</li><p>
 
   <li><math>1</math> way to move from the top face to the bottom face.</li><p>
 
   <li><math>1</math> way to move from the top face to the top face.</li><p>
 
   <li><math>1</math> way to move from the top face to the top face.</li><p>
 
</ul>
 
</ul>
 
</ol>
 
</ol>
−
Alternatively, this recursion argument is shown in the illustration below, where each red arrow indicates <math>1</math> way, and each blue arrow indicates <math>2</math> ways:
+
Alternatively, this recursion argument is illustrated below, where each dashed arrow indicates <math>1</math> way, and each solid arrow indicates <math>2</math> ways:
 
<asy>
 
<asy>
−
/* by MRENTHUSIASM */
+
/* Made by MRENTHUSIASM */  
−
size(7cm);
+
size(9cm);  
−
pair A, B, C, D, E, F, G, H;
+
pair A, B, C, D, E, F, G, H, X, Y;  
−
A=(0,6);
+
A=(0,6);  
−
B=(0,4);
+
B=(0,4);  
−
C=(0,2);
+
C=(0,2);  
−
D=(0,0);
+
D=(0,0);  
−
E=(4,6);
+
E=(10,6);  
−
F=(4,4);
+
F=(10,4);  
−
G=(4,2);
+
G=(10,2);  
−
H=(4,0);
+
H=(10,0);
−
label("$N(k, $BB" + "$)$", A, (-2,0));
+
X=(-1,8);
−
label("$N(k, $BT" + "$)$", B, (-2,0));
+
Y=(11,8);  
−
label("$N(k, $TB" + "$)$", C, (-2,0));
+
label("BB", A, (-2,0));  
−
label("$N(k, $TT" + "$)$", D, (-2,0));
+
label("BT", B, (-2,0));  
−
label("$N(k+1, $BB" + "$)$", E, (2,0));
+
label("TB", C, (-2,0));  
−
label("$N(k+1, $BT" + "$)$", F, (2,0));
+
label("TT", D, (-2,0));  
−
label("$N(k+1, $TB" + "$)$", G, (2,0));
+
label("BB", E, (2,0));  
−
label("$N(k+1, $TT" + "$)$", H, (2,0));
+
label("BT", F, (2,0));
−
draw(A--E,0.8+red,EndArrow);
+
label("TB", G, (2,0));
−
draw(A--F,0.8+red,EndArrow);
+
label("TT", H, (2,0));  
−
draw(B--H,0.8+blue,EndArrow);
+
label("\textbf{The \boldmath{$k$}th Move}", shift(0.3,0)*X);  
−
draw(C--E,0.8+blue,EndArrow);
+
label("\textbf{The \boldmath{$(k+1)$}th Move}", shift(-0.3,-0.085)*Y);  
−
draw(D--G,0.8+red,EndArrow);
+
draw(A--E,0.8+black+dashed,EndArrow);  
−
draw(D--H,0.8+red,EndArrow);
+
draw(A--F,0.8+black+dashed,EndArrow);  
 +
draw(B--H,0.8+black,EndArrow);  
 +
draw(C--E,0.8+black,EndArrow);  
 +
draw(D--G,0.8+black+dashed,EndArrow);  
 +
draw(D--H,0.8+black+dashed,EndArrow);  
 
dot(A^^B^^C^^D^^E^^F^^G^^H, 5+black);
 
dot(A^^B^^C^^D^^E^^F^^G^^H, 5+black);
 
</asy>
 
</asy>
 
Therefore, we have the following relationships:
 
Therefore, we have the following relationships:
 
<cmath>\begin{align*}
 
<cmath>\begin{align*}
−
N(1,\text{BB})&=2, \\  
+
N(1,\mathrm{BB})&=2, \\  
−
N(1,\text{BT})&=1, \\
+
N(1,\mathrm{BT})&=1, \\
−
N(k+1,\text{BB})&=N(k,\text{BB})+2\cdot N(k,\text{TB}), \\
+
N(1,\mathrm{TB})&=0, \\
−
N(k+1,\text{BT})&=N(k,\text{BB}), \\
+
N(1,\mathrm{TT})&=0, \\
−
N(k+1,\text{TB})&=N(k,\text{TT}), \\
+
N(k+1,\mathrm{BB})&=N(k,\mathrm{BB})+2\cdot N(k,\mathrm{TB}), \\
−
N(k+1,\text{TT})&=N(k,\text{TT})+2\cdot N(k,\text{BT}).
+
N(k+1,\mathrm{BT})&=N(k,\mathrm{BB}), \\
 +
N(k+1,\mathrm{TB})&=N(k,\mathrm{TT}), \\
 +
N(k+1,\mathrm{TT})&=N(k,\mathrm{TT})+2\cdot N(k,\mathrm{BT}).
 
\end{align*}</cmath>
 
\end{align*}</cmath>
 
Using these equations, we recursively fill out the table below:
 
Using these equations, we recursively fill out the table below:
 
<cmath>\begin{array}{c||c|c|c|c|c|c|c|c}   
 
<cmath>\begin{array}{c||c|c|c|c|c|c|c|c}   
−
&&&&&&&& \\ [-2.5ex]
+
\hspace{7mm}&\hspace{6.5mm}&\hspace{6.5mm}&\hspace{6.75mm}&\hspace{6.75mm}&\hspace{6.75mm}&\hspace{6.75mm}&& \\ [-2.5ex]
 
\boldsymbol{k} & \boldsymbol{1} & \boldsymbol{2} & \boldsymbol{3} & \boldsymbol{4} & \boldsymbol{5} & \boldsymbol{6} & \boldsymbol{7} & \boldsymbol{8} \\  
 
\boldsymbol{k} & \boldsymbol{1} & \boldsymbol{2} & \boldsymbol{3} & \boldsymbol{4} & \boldsymbol{5} & \boldsymbol{6} & \boldsymbol{7} & \boldsymbol{8} \\  
 
\hline \hline
 
\hline \hline
 
&&&&&&&& \\ [-2.25ex]
 
&&&&&&&& \\ [-2.25ex]
−
\boldsymbol{N(k,\textbf{BB})} &2&2&2&6&18&38&66&118 \\ \hline   
+
\boldsymbol{N(k,\mathrm{BB})} &2&2&2&6&18&38&66&118 \\ \hline   
 
&&&&&&&& \\ [-2.25ex]
 
&&&&&&&& \\ [-2.25ex]
−
\boldsymbol{N(k,\textbf{BT})} &1&2&2&2&6&18&38&66 \\ \hline  
+
\boldsymbol{N(k,\mathrm{BT})} &1&2&2&2&6&18&38&66 \\ \hline  
 
&&&&&&&& \\ [-2.25ex]
 
&&&&&&&& \\ [-2.25ex]
−
\boldsymbol{N(k,\textbf{TB})} &0&0&2&6&10&14&26&62 \\ \hline   
+
\boldsymbol{N(k,\mathrm{TB})} &0&0&2&6&10&14&26&62 \\ \hline   
 
&&&&&&&& \\ [-2.25ex]
 
&&&&&&&& \\ [-2.25ex]
−
\boldsymbol{N(k,\textbf{TT})} &0&2&6&10&14&26&62&138 \\
+
\boldsymbol{N(k,\mathrm{TT})} &0&2&6&10&14&26&62&138 \\
 
\hline \hline
 
\hline \hline
 
&&&&&&&& \\ [-2.25ex]
 
&&&&&&&& \\ [-2.25ex]
 
\textbf{Total}&\boldsymbol{3}&\boldsymbol{6}&\boldsymbol{12}&\boldsymbol{24}&\boldsymbol{48}&\boldsymbol{96}&\boldsymbol{192}&\boldsymbol{384}
 
\textbf{Total}&\boldsymbol{3}&\boldsymbol{6}&\boldsymbol{12}&\boldsymbol{24}&\boldsymbol{48}&\boldsymbol{96}&\boldsymbol{192}&\boldsymbol{384}
 
\end{array}</cmath>
 
\end{array}</cmath>
−
Clearly, there are <math>3\cdot2^{k-1}</math> ways to make <math>k</math> moves. To guarantee correctness, note that for each value of <math>k,</math> the four counts in that column must total up to <math>3\cdot2^{k-1}.</math>
+
By the Multiplication Principle, there are <math>3\cdot2^{k-1}</math> ways to make exactly <math>k</math> moves. So, we must get <cmath>N(k,\mathrm{BB})+N(k,\mathrm{BT})+N(k,\mathrm{TB})+N(k,\mathrm{TT})=3\cdot2^{k-1}</cmath> for all values of <math>k.</math>
  
−
Finally, the requested probability is <cmath>\frac{N(8,\text{BT})+N(8,\text{TT})}{N(8,\text{BB})+N(8,\text{BT})+N(8,\text{TB})+N(8,\text{TT})}=\frac{66+138}{118+66+62+138}=\frac{204}{384}=\frac{17}{32},</cmath> from which the answer is <math>17+32=\boxed{049}.</math>
+
Finally, the requested probability is <cmath>\frac{N(8,\mathrm{BT})+N(8,\mathrm{TT})}{N(8,\mathrm{BB})+N(8,\mathrm{BT})+N(8,\mathrm{TB})+N(8,\mathrm{TT})}=\frac{66+138}{118+66+62+138}=\frac{204}{384}=\frac{17}{32},</cmath> from which the answer is <math>17+32=\boxed{049}.</math>
  
−
~Arcticturn (Fundamental Logic)
+
~Arcticturn ~MRENTHUSIASM
  
−
~MRENTHUSIASM (Remodeling)
+
==Solution 2 (Markov Chain and Dynamic Programming)==
  
−
==Solution 2 (Casework)==
+
Let the state from bottom to top be <math>B2T,</math> from top to top be <math>T2T,</math> from top to bottom be <math>T2B,</math> and from bottom to bottom be <math>B2B.</math> We can draw the following State Transition Diagram with [https://en.wikipedia.org/wiki/Markov_chain Markov Chain]. The numbers on the transition arc are the transition probabilities.
 +
[[File:Markov-Chain-AIME.png | 300px | center]]
 +
The probabilities of being in a state after <math>n</math> steps and after <math>n-1</math> steps has the following relationships:
 +
<cmath>\begin{align*}
 +
B2T(n) &= B2B(n-1) \cdot \frac12\\
 +
T2T(n) &= B2T(n-1) + T2T(n-1) \cdot \frac12\\
 +
T2B(n) &= T2T(n-1) \cdot \frac12\\
 +
B2B(n) &= T2B(n-1) + B2B(n-1) \cdot \frac12
 +
\end{align*}</cmath>
 +
Those probabilities are calculated by [https://en.wikipedia.org/wiki/Dynamic_programming Dynamic Programming] in the following table:
 +
<cmath>\begin{array}{c|cccc}
 +
&  &  &  & \\ [-2ex]
 +
n & B2T(n) & T2T(n) & T2B(n) & B2B(n) \\ [1ex]
 +
\hline
 +
&  &  &  & \\ [-1ex]
 +
1 & \frac13 & 0 & 0 & \frac23\\
 +
&  &  &  & \\
 +
2 & \frac23 \cdot \frac12 = \frac13 & \frac13 & 0 & \frac23 \cdot \frac12 = \frac13 \\
 +
&  &  &  & \\
 +
3 & \frac13 \cdot \frac12 = \frac16 & \frac13 + \frac13 \cdot \frac12 = \frac12 & \frac13 \cdot \frac12 = \frac16 & \frac13 \cdot \frac12 = \frac16 \\
 +
&  &  &  & \\
 +
4 & \frac16 \cdot \frac12 = \frac{1}{12} & \frac16 + \frac12 \cdot \frac12 = \frac{5}{12} & \frac12 \cdot \frac12 = \frac14 & \frac16 + \frac16 \cdot \frac12 = \frac14 \\
 +
&  &  &  & \\
 +
5 & \frac14 \cdot \frac12 = \frac18 & \frac{1}{12} + \frac{5}{12} \cdot \frac{1}{2} = \frac{7}{24} & \frac{5}{12} \cdot \frac12 = \frac{5}{24} & \frac14 + \frac14 \cdot \frac12 = \frac38 \\
 +
&  &  &  & \\
 +
6 & \frac38 \cdot \frac12 = \frac{3}{16} & \frac18 + \frac{7}{24} \cdot \frac12 = \frac{13}{48} & \frac{7}{24} \cdot \frac12 = \frac{7}{48} & \frac{5}{24} + \frac38 \cdot \frac12 = \frac{19}{48} \\
 +
&  &  &  & \\
 +
7 & \frac{19}{48} \cdot \frac12 = \frac{19}{96}&  \frac{3}{16} + \frac{13}{48} \cdot \frac{1}{2} = \frac{31}{96}& \frac{13}{48} \cdot \frac{1}{2} = \frac{13}{96} & \frac{7}{48} + \frac{19}{48} \cdot \frac12 = \frac{11}{32}\\
 +
&  &  &  & \\
 +
8 & \frac{11}{32} \cdot \frac{1}{2} = \frac{11}{64} & \frac{19}{96} + \frac{31}{96} \cdot \frac12 = \frac{23}{64} & \frac{31}{96} \cdot \frac12 = \frac{31}{192} & \frac{13}{96} + \frac{11}{32} \cdot \frac12 = \frac{59}{192} \\ [1ex]
 +
\end{array}</cmath>
 +
Finally, the requested probability is <math>\frac{11}{64} + \frac{23}{64} = \frac{17}{32},</math> from which the answer is <math>17 + 32 = \boxed{049}.</math>
 +
 
 +
~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen#AIME isabelchen]
 +
 
 +
==Solution 3 (One-Variable Recursion)==
 +
Note that we don't care which exact vertex the ant is located at, just which level (either top face or bottom face).
 +
Consider the ant to be on any of the two levels and having moved at least one move. Define <math>p_i</math> to be the probability that after <math>i</math> moves, the ant ends up on the level it started on.
 +
 
 +
On the first move, the ant can stay on the bottom level with <math>\frac{2}{3}</math> chance and <math>7</math> moves left. Or, it can move to the top level with <math>\frac{1}{3}</math> chance and <math>6</math> moves left (it has to spend another on the top as it can not return immediately). So the requested probability is <math>P = \frac{2}{3}(1 - p_7) + \frac{1}{3}p_6</math>.
 +
 
 +
Consider when the ant has <math>i</math> moves left (and it's not the ant's first move). It can either stay on its current level with <math>\frac{1}{2}</math> chance and <math>i - 1</math> moves left, or travel to the opposite level with <math>\frac{1}{2}</math> chance, then move to another vertex on the opposite level, to have <math>i - 2</math> moves left. Thus we obtain the recurrence
 +
<cmath>p_i = \frac{1}{2}p_{i - 1} + \frac{1}{2}(1 - p_{i - 2})</cmath>
 +
 
 +
Computing <math>p_i</math> with the starting conditions <math>p_0 = 1</math> and <math>p_1 = \frac{1}{2}</math>, we obtain <math>p_6 = \frac{33}{64}</math> and <math>p_7 = \frac{59}{128}</math>. Hence <math>P = \frac{2}{3}(1 - p_7) + \frac{1}{3}p_6= \frac{17}{32}</math> as desired; <math>\boxed{049}</math>.
 +
 
 +
~polarity
 +
 
 +
==Solution 4 (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).  
 
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).  
  
 
# '''Case 1: one switch.''' Our one switch can either happen at the start/end of our moves, or in the middle. There are <math>4 + 24 = 28</math> ways to do this, outlined below.
 
# '''Case 1: one switch.''' Our one switch can either happen at the start/end of our moves, or in the middle. There are <math>4 + 24 = 28</math> ways to do this, outlined below.
−
## '''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 <math>2^2 = 4</math> possibilities.
+
## '''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 <math>2</math> to count for symmetry (last move is a switch) so this case yields <math>2^2 = 4</math> possibilities.
−
## '''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 <math>6 \cdot 2^2 = 24</math> possibilities.
+
## '''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 <math>2</math> ways to choose their direction of travel. This case yields <math>6 \cdot 2^2 = 24</math> possibilities.
 
# '''Case 2: three switches.''' Either two, one, or none of our switches occur at the start/end of our moves. There are <math>16 + 96 + 64 = 176</math> ways to do this, outlined below. (Keep in mind we can't have two switches in a row.)
 
# '''Case 2: three switches.''' Either two, one, or none of our switches occur at the start/end of our moves. There are <math>16 + 96 + 64 = 176</math> ways to do this, outlined below. (Keep in mind we can't have two switches in a row.)
−
## '''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 <math>4 \cdot 2^2 = 16</math> possibilities.
+
## '''Subcase 1: start and end with a switch.''' Since our third switch can't be in moves <math>2</math> or <math>7</math>, there are four ways to place our switch, breaking our sequence into two chains. This case yields <math>4 \cdot 2^2 = 16</math> possibilities.
−
## '''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 <math>2\left(\binom{5}{2} - 4\right) \cdot 2^3 = 96</math> possibilities.
+
## '''Subcase 2: one of our switches is at the start/end.''' WLOG our first move is a switch; moves <math>2</math> and <math>8</math> cannot be switches. We can choose <math>2</math> from any of the remaining <math>5</math> moves to be switches, but we have to subtract the <math>4</math> 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 <math>2\left(\binom{5}{2} - 4\right) \cdot 2^3 = 96</math> possibilities.
−
## '''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 <math>\left(\binom{6}{3} - 5 \cdot 4 + 4\right) \cdot 2^4 = 64</math> possibilities.
+
## '''Subcase 3: all our switches are in the middle.''' We choose <math>3</math> from any of the <math>6</math> 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 <math>2</math> and four places for the third switch; however this overcounts the case where all three are in a row, which has <math>4</math> possibilities. These three switches break our sequence into four chains, so this case yields <math>\left(\binom{6}{3} - 5 \cdot 4 + 4\right) \cdot 2^4 = 64</math> possibilities.
 +
 
 +
Our probability is then <math>\frac{176 + 28}{3 \cdot 2^7} = \frac{17}{32}</math>, so the answer is <math>17+32=\boxed{049}</math>.
 +
 
 +
==Solution 5 (One-Variable Recursion and Casework)==
 +
 
 +
Let <math>p(n)</math> be the probability that we are on the top when you get to the <math>n</math>th move, and <math>p(n-1)</math> and <math>p(n-2)</math> be the probability that you are on the top when you get to the <math>(n-1)</math>th move and <math>(n-2)</math>th move respectively.
 +
 
 +
Now you can do some recursion, splitting up into cases:
 +
 
 +
Case 1: You are not on the top for the <math>(n-1)</math>th move or the <math>(n-2)</math>th move. In this case, it is a <math>1-p(n-1)</math> chance that you were not on the top for the <math>(n-1)</math>th move, and a <math>1-p(n-2)</math> that you are not on the top for the <math>(n-2)</math>th move. This leads you to a <math>\frac{1}{2}\cdot(1-p(n-1))\cdot(1-p(n-2))</math> chance for the first case. (The <math>\frac12</math> is there because of the fact that you can go up and you can also stay on the bottom side, as you cannot return.)
 +
 
 +
Case 2: You are on the top for the <math>(n-1)</math>th move, but not on the top for the <math>(n-2)</math>th move. This leads you to a <math>p(n-1)\cdot(1-p(n-2))</math> probability (no extra components because you cannot return).
  
−
Our probability is then <math>\frac{176 + 28}{3 \cdot 2^7} = \frac{17}{32} \iff \boxed{049}</math>.
+
Case 3: You are on top for both the <math>(n-1)</math>th move and the <math>(n-2)</math>th move. This leads to a probability of <math>\frac{1}{2}\cdot p(n-1)\cdot p(n-2)</math> (adding the extra <math>\frac12</math> because you can either stay on the top or go down.
  
−
==See also==
+
As the 4th case requires you to go down then up, but you cannot retrace, there is no <math>4</math>th case.
 +
 
 +
These cases, added up, lead you to <cmath>p(n)=\frac{1}{2}\cdot(1-p(n-1))(1-p(n-2))+p(n-1)(1-p(n-2))+\frac{1}{2}\cdot p(n-1)p(n-2).</cmath> This can be further simplified down by expanding and combining like terms to <cmath>p(n)=\frac{1+p(n-1)-p(n-2)}{2}.</cmath>
 +
Then we must find <math>p(1)</math> and <math>p(2)</math>. p(1) is trivially <math>\frac{1}{3}</math>. You can find <math>p(2)</math> using basic probability techniques that is left as an exercise to the reader to get <math>\frac{2}{3}</math>. In the end, you plug in to get
 +
<cmath>p(1)=\frac{1}{3},
 +
P(2)=\frac{2}{3},
 +
P(3)=\frac{2}{3},
 +
P(4)=\frac{1}{2},
 +
P(5)=\frac{5}{12},
 +
P(6)=\frac{11}{24},
 +
P(7)=\frac{25}{48},
 +
P(8)=\boxed{\frac{17}{32}}.</cmath>
 +
Therefore, the answer is <math>17+32=\boxed{049}</math>.
 +
 
 +
~dragoon
 +
 
 +
==Remark (Markov Chain)==
 +
 
 +
This problem is similar to the following problems:
 +
 
 +
* [https://artofproblemsolving.com/wiki/index.php/1985_AIME_Problems/Problem_12 1985 AIME Problem 12]
 +
 
 +
* [https://artofproblemsolving.com/wiki/index.php/2003_AIME_II_Problems/Problem_13 2003 AIME II Problem 13]
 +
 
 +
* [https://artofproblemsolving.com/wiki/index.php/2021_AMC_12A_Problems/Problem_23 2021 AMC 12A Problem 23]
 +
 
 +
* [https://artofproblemsolving.com/wiki/index.php/2022_AMC_8_Problems/Problem_25 2022 AMC 8 Problem 25]
 +
 
 +
They can all be solved by [https://en.wikipedia.org/wiki/Markov_chain Markov Chain] and [https://en.wikipedia.org/wiki/Dynamic_programming Dynamic Programming].
 +
 
 +
Let <math>p_{ij} = P(X_{n+1} = j | X_n = i)</math> be the probability that state <math>i</math> transits to state <math>j</math> on the next step, and <math>s_i</math> be the probability of being in state <math>i</math>. It follows that <math>s_j</math> is the sum of the products of <math>s_i</math> and <math>p_{ij}</math> of all the previous state <math>i</math>: <cmath>s_j = \sum_{i} (s_{i} \cdot p_{ij}).</cmath>
 +
This formula can also be applied to solve [https://artofproblemsolving.com/wiki/index.php/2019_AMC_10B_Problems/Problem_22 2019 AMC10B Problem 22].
 +
 
 +
~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen#AIME isabelchen]
 +
 
 +
==Video Solution==
 +
https://youtu.be/dBLEe0oczuA
 +
 
 +
~Interstigation
 +
 
 +
==Video Solution==
 +
https://youtu.be/4UjQhFEa1ms
 +
 
 +
~MathProblemSolvingSkills.com
 +
 
 +
==See Also==
 
{{AIME box|year=2021|n=II|num-b=7|num-a=9}}
 
{{AIME box|year=2021|n=II|num-b=7|num-a=9}}
 
{{MAA Notice}}
 
{{MAA Notice}}
 +
 +
[[Category:Intermediate Combinatorics Problems]]

Latest revision as of 17:32, 23 January 2023

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 (Four-Variable Recursion)

For all positive integers $k,$ let

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

The base case occurs at $k=1,$ from which $\left(N(1,\mathrm{BB}),N(1,\mathrm{BT}),N(1,\mathrm{TB}),N(1,\mathrm{TT})\right)=(2,1,0,0).$

Suppose the ant makes exactly $k$ moves for some $k\geq2.$ We perform casework on its last move:

  1. If its last move is from the bottom face to the bottom face, then its next move has

    • $1$ way to move from the bottom face to the bottom face.

    • $1$ way to move from the bottom face to the top face.

  2. If its last move is from the bottom face to the top face, then its next move has $2$ ways to move from the top face to the top face.

  3. If its last move is from the top face to the bottom face, then its next move has $2$ ways to move from the bottom face to the bottom face.

  4. If its last move is from the top face to the top face, then its next move has

    • $1$ way to move from the top face to the bottom face.

    • $1$ way to move from the top face to the top face.

Alternatively, this recursion argument is illustrated below, where each dashed arrow indicates $1$ way, and each solid arrow indicates $2$ ways: [asy] /* Made by MRENTHUSIASM */ size(9cm); pair A, B, C, D, E, F, G, H, X, Y; A=(0,6); B=(0,4); C=(0,2); D=(0,0); E=(10,6); F=(10,4); G=(10,2); H=(10,0); X=(-1,8); Y=(11,8); label("BB", A, (-2,0)); label("BT", B, (-2,0)); label("TB", C, (-2,0)); label("TT", D, (-2,0)); label("BB", E, (2,0)); label("BT", F, (2,0)); label("TB", G, (2,0)); label("TT", H, (2,0)); label("\textbf{The \boldmath{$k$}th Move}", shift(0.3,0)*X); label("\textbf{The \boldmath{$(k+1)$}th Move}", shift(-0.3,-0.085)*Y); draw(A--E,0.8+black+dashed,EndArrow); draw(A--F,0.8+black+dashed,EndArrow); draw(B--H,0.8+black,EndArrow); draw(C--E,0.8+black,EndArrow); draw(D--G,0.8+black+dashed,EndArrow); draw(D--H,0.8+black+dashed,EndArrow); dot(A^^B^^C^^D^^E^^F^^G^^H, 5+black); [/asy] Therefore, we have the following relationships: \begin{align*} N(1,\mathrm{BB})&=2, \\ N(1,\mathrm{BT})&=1, \\ N(1,\mathrm{TB})&=0, \\ N(1,\mathrm{TT})&=0, \\ N(k+1,\mathrm{BB})&=N(k,\mathrm{BB})+2\cdot N(k,\mathrm{TB}), \\ N(k+1,\mathrm{BT})&=N(k,\mathrm{BB}), \\ N(k+1,\mathrm{TB})&=N(k,\mathrm{TT}), \\ N(k+1,\mathrm{TT})&=N(k,\mathrm{TT})+2\cdot N(k,\mathrm{BT}). \end{align*} Using these equations, we recursively fill out the table below: \[\begin{array}{c||c|c|c|c|c|c|c|c} \hspace{7mm}&\hspace{6.5mm}&\hspace{6.5mm}&\hspace{6.75mm}&\hspace{6.75mm}&\hspace{6.75mm}&\hspace{6.75mm}&& \\ [-2.5ex] \boldsymbol{k} & \boldsymbol{1} & \boldsymbol{2} & \boldsymbol{3} & \boldsymbol{4} & \boldsymbol{5} & \boldsymbol{6} & \boldsymbol{7} & \boldsymbol{8} \\ \hline \hline &&&&&&&& \\ [-2.25ex] \boldsymbol{N(k,\mathrm{BB})} &2&2&2&6&18&38&66&118 \\ \hline &&&&&&&& \\ [-2.25ex] \boldsymbol{N(k,\mathrm{BT})} &1&2&2&2&6&18&38&66 \\ \hline &&&&&&&& \\ [-2.25ex] \boldsymbol{N(k,\mathrm{TB})} &0&0&2&6&10&14&26&62 \\ \hline &&&&&&&& \\ [-2.25ex] \boldsymbol{N(k,\mathrm{TT})} &0&2&6&10&14&26&62&138 \\ \hline \hline &&&&&&&& \\ [-2.25ex] \textbf{Total}&\boldsymbol{3}&\boldsymbol{6}&\boldsymbol{12}&\boldsymbol{24}&\boldsymbol{48}&\boldsymbol{96}&\boldsymbol{192}&\boldsymbol{384} \end{array}\] By the Multiplication Principle, there are $3\cdot2^{k-1}$ ways to make exactly $k$ moves. So, we must get \[N(k,\mathrm{BB})+N(k,\mathrm{BT})+N(k,\mathrm{TB})+N(k,\mathrm{TT})=3\cdot2^{k-1}\] for all values of $k.$

Finally, the requested probability is \[\frac{N(8,\mathrm{BT})+N(8,\mathrm{TT})}{N(8,\mathrm{BB})+N(8,\mathrm{BT})+N(8,\mathrm{TB})+N(8,\mathrm{TT})}=\frac{66+138}{118+66+62+138}=\frac{204}{384}=\frac{17}{32},\] from which the answer is $17+32=\boxed{049}.$

~Arcticturn ~MRENTHUSIASM

Solution 2 (Markov Chain and Dynamic Programming)

Let the state from bottom to top be $B2T,$ from top to top be $T2T,$ from top to bottom be $T2B,$ and from bottom to bottom be $B2B.$ We can draw the following State Transition Diagram with Markov Chain. The numbers on the transition arc are the transition probabilities.

Markov-Chain-AIME.png

The probabilities of being in a state after $n$ steps and after $n-1$ steps has the following relationships: \begin{align*} B2T(n) &= B2B(n-1) \cdot \frac12\\ T2T(n) &= B2T(n-1) + T2T(n-1) \cdot \frac12\\ T2B(n) &= T2T(n-1) \cdot \frac12\\ B2B(n) &= T2B(n-1) + B2B(n-1) \cdot \frac12 \end{align*} Those probabilities are calculated by Dynamic Programming in the following table: \[\begin{array}{c|cccc} & & & & \\ [-2ex] n & B2T(n) & T2T(n) & T2B(n) & B2B(n) \\ [1ex] \hline & & & & \\ [-1ex] 1 & \frac13 & 0 & 0 & \frac23\\ & & & & \\ 2 & \frac23 \cdot \frac12 = \frac13 & \frac13 & 0 & \frac23 \cdot \frac12 = \frac13 \\ & & & & \\ 3 & \frac13 \cdot \frac12 = \frac16 & \frac13 + \frac13 \cdot \frac12 = \frac12 & \frac13 \cdot \frac12 = \frac16 & \frac13 \cdot \frac12 = \frac16 \\ & & & & \\ 4 & \frac16 \cdot \frac12 = \frac{1}{12} & \frac16 + \frac12 \cdot \frac12 = \frac{5}{12} & \frac12 \cdot \frac12 = \frac14 & \frac16 + \frac16 \cdot \frac12 = \frac14 \\ & & & & \\ 5 & \frac14 \cdot \frac12 = \frac18 & \frac{1}{12} + \frac{5}{12} \cdot \frac{1}{2} = \frac{7}{24} & \frac{5}{12} \cdot \frac12 = \frac{5}{24} & \frac14 + \frac14 \cdot \frac12 = \frac38 \\ & & & & \\ 6 & \frac38 \cdot \frac12 = \frac{3}{16} & \frac18 + \frac{7}{24} \cdot \frac12 = \frac{13}{48} & \frac{7}{24} \cdot \frac12 = \frac{7}{48} & \frac{5}{24} + \frac38 \cdot \frac12 = \frac{19}{48} \\ & & & & \\ 7 & \frac{19}{48} \cdot \frac12 = \frac{19}{96}& \frac{3}{16} + \frac{13}{48} \cdot \frac{1}{2} = \frac{31}{96}& \frac{13}{48} \cdot \frac{1}{2} = \frac{13}{96} & \frac{7}{48} + \frac{19}{48} \cdot \frac12 = \frac{11}{32}\\ & & & & \\ 8 & \frac{11}{32} \cdot \frac{1}{2} = \frac{11}{64} & \frac{19}{96} + \frac{31}{96} \cdot \frac12 = \frac{23}{64} & \frac{31}{96} \cdot \frac12 = \frac{31}{192} & \frac{13}{96} + \frac{11}{32} \cdot \frac12 = \frac{59}{192} \\ [1ex] \end{array}\] Finally, the requested probability is $\frac{11}{64} + \frac{23}{64} = \frac{17}{32},$ from which the answer is $17 + 32 = \boxed{049}.$

~isabelchen

Solution 3 (One-Variable Recursion)

Note that we don't care which exact vertex the ant is located at, just which level (either top face or bottom face). Consider the ant to be on any of the two levels and having moved at least one move. Define $p_i$ to be the probability that after $i$ moves, the ant ends up on the level it started on.

On the first move, the ant can stay on the bottom level with $\frac{2}{3}$ chance and $7$ moves left. Or, it can move to the top level with $\frac{1}{3}$ chance and $6$ moves left (it has to spend another on the top as it can not return immediately). So the requested probability is $P = \frac{2}{3}(1 - p_7) + \frac{1}{3}p_6$.

Consider when the ant has $i$ moves left (and it's not the ant's first move). It can either stay on its current level with $\frac{1}{2}$ chance and $i - 1$ moves left, or travel to the opposite level with $\frac{1}{2}$ chance, then move to another vertex on the opposite level, to have $i - 2$ moves left. Thus we obtain the recurrence \[p_i = \frac{1}{2}p_{i - 1} + \frac{1}{2}(1 - p_{i - 2})\]

Computing $p_i$ with the starting conditions $p_0 = 1$ and $p_1 = \frac{1}{2}$, we obtain $p_6 = \frac{33}{64}$ and $p_7 = \frac{59}{128}$. Hence $P = \frac{2}{3}(1 - p_7) + \frac{1}{3}p_6= \frac{17}{32}$ as desired; $\boxed{049}$.

~polarity

Solution 4 (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}$, so the answer is $17+32=\boxed{049}$.

Solution 5 (One-Variable Recursion and Casework)

Let $p(n)$ be the probability that we are on the top when you get to the $n$th move, and $p(n-1)$ and $p(n-2)$ be the probability that you are on the top when you get to the $(n-1)$th move and $(n-2)$th move respectively.

Now you can do some recursion, splitting up into cases:

Case 1: You are not on the top for the $(n-1)$th move or the $(n-2)$th move. In this case, it is a $1-p(n-1)$ chance that you were not on the top for the $(n-1)$th move, and a $1-p(n-2)$ that you are not on the top for the $(n-2)$th move. This leads you to a $\frac{1}{2}\cdot(1-p(n-1))\cdot(1-p(n-2))$ chance for the first case. (The $\frac12$ is there because of the fact that you can go up and you can also stay on the bottom side, as you cannot return.)

Case 2: You are on the top for the $(n-1)$th move, but not on the top for the $(n-2)$th move. This leads you to a $p(n-1)\cdot(1-p(n-2))$ probability (no extra components because you cannot return).

Case 3: You are on top for both the $(n-1)$th move and the $(n-2)$th move. This leads to a probability of $\frac{1}{2}\cdot p(n-1)\cdot p(n-2)$ (adding the extra $\frac12$ because you can either stay on the top or go down.

As the 4th case requires you to go down then up, but you cannot retrace, there is no $4$th case.

These cases, added up, lead you to \[p(n)=\frac{1}{2}\cdot(1-p(n-1))(1-p(n-2))+p(n-1)(1-p(n-2))+\frac{1}{2}\cdot p(n-1)p(n-2).\] This can be further simplified down by expanding and combining like terms to \[p(n)=\frac{1+p(n-1)-p(n-2)}{2}.\] Then we must find $p(1)$ and $p(2)$. p(1) is trivially $\frac{1}{3}$. You can find $p(2)$ using basic probability techniques that is left as an exercise to the reader to get $\frac{2}{3}$. In the end, you plug in to get \[p(1)=\frac{1}{3}, P(2)=\frac{2}{3}, P(3)=\frac{2}{3}, P(4)=\frac{1}{2}, P(5)=\frac{5}{12}, P(6)=\frac{11}{24}, P(7)=\frac{25}{48}, P(8)=\boxed{\frac{17}{32}}.\] Therefore, the answer is $17+32=\boxed{049}$.

~dragoon

Remark (Markov Chain)

This problem is similar to the following problems:

They can all be solved by Markov Chain and Dynamic Programming.

Let $p_{ij} = P(X_{n+1} = j | X_n = i)$ be the probability that state $i$ transits to state $j$ on the next step, and $s_i$ be the probability of being in state $i$. It follows that $s_j$ is the sum of the products of $s_i$ and $p_{ij}$ of all the previous state $i$: \[s_j = \sum_{i} (s_{i} \cdot p_{ij}).\] This formula can also be applied to solve 2019 AMC10B Problem 22.

~isabelchen

Video Solution

https://youtu.be/dBLEe0oczuA

~Interstigation

Video Solution

https://youtu.be/4UjQhFEa1ms

~MathProblemSolvingSkills.com

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=187394"