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

2021 AIME II Problems/Problem 8

Revision as of 19:23, 28 January 2022 by MRENTHUSIASM (talk | contribs) (→‎Solution 2 (Casework))

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,\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 (Fundamental Logic)

~MRENTHUSIASM (Reconstruction)

Solution 3 (Faster Recursion)

Define $n_i$ to be the probability that after $i$ moves, the ant ends up on the level it started on (assuming the first move is a normal move where the ant can stay or move to the opposite level with half chance each). Note $n_0 = 1$ and $n_1 = \frac{1}{2}$.

Consider when the ant has $i$ moves left. 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 and $i - 2$ moves left (it must spend another move as it cannot travel back immediately). We then have the recurrence \[n_i = \frac{1}{2}n_{i - 1} + \frac{1}{2}(1 - n_{i - 2})\]

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 one on the top as it can not return immediately). So the requested probability is $P = \frac{2}{3}(1 - n_7) + \frac{1}{3}n_6$.

Computing $n_i$ we get $n_6 = \frac{33}{64}$ and $n_7 = \frac{59}{128}$, resulting in $P = \frac{17}{32} \iff \boxed{049}$.

~IAmLegend (1e9end.github.io)

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