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 "1985 AIME Problems/Problem 12"
(→‎Solution 7 (Dynamic Programming))
Line 160: Line 160:
  
 
==Solution 7 (Dynamic Programming)==
 
==Solution 7 (Dynamic Programming)==
 +
 +
Let <math>A(n)</math> be the probability the bug lands on vertex A after crawling <math>n</math> meters, <math>B(n)</math> be the probability the bug lands on vertex B after crawling <math>n</math> meters and etc.
 +
 +
<math>A(n) = \frac13 B(n-1) + \frac13 C(n-1) + \frac13 D(n-1)</math>, <math>B(n) = C(n) = D(n)</math>, <math>A(n) = B(n-1)</math>
 +
 +
<math>B(n) = \frac{A(n-1) + C(n-1) + D(n-1)}{3}</math>
 +
 +
<math>C(n) = \frac{A(n-1) + B(n-1) + D(n-1)}{3}</math>
 +
 +
<math>D(n) = \frac{A(n-1) + B(n-1) + C(n-1)}{3}</math>
  
 
<cmath>\[ \begin{array}[b]{ccccc}
 
<cmath>\[ \begin{array}[b]{ccccc}
 
n & A(n) & B(n) & C(n) & D(n) \\
 
n & A(n) & B(n) & C(n) & D(n) \\
 
  &  &  &  & \\
 
  &  &  &  & \\
−
1 & & & & \\
+
1 & 0 & \frac13 & \frac13 & \frac13 \\
 
  &  &  &  & \\
 
  &  &  &  & \\
−
2 & & & & \\
+
2 & \frac13 & \frac29 & \frac29 & \frac29 \\
 
  &  &  &  & \\
 
  &  &  &  & \\
−
3 & & & & \\
+
3 & \frac29 & \frac{7}{27} & \frac{7}{27} & \frac{7}{27} \\
 
  &  &  &  & \\
 
  &  &  &  & \\
−
4 & & & & \\
+
4 & \frac{7}{27} & \frac{20}{81} & \frac{20}{81} & \frac{20}{81}\\
 +
&  &  &  & \\
 +
5 & \frac{20}{81} & \frac{61}{243} & \frac{61}{243} & \frac{61}{243} \\
 +
&  &  & & \\
 +
6 & \frac{61}{243} & \frac{182}{729} & \frac{182}{729} & \frac{182}{729} \\
 +
&  &  &  & \\
 +
7 & \frac{182}{729} & \frac{547}{2187} & \frac{547}{2187} & \frac{547}{2187}
 
\end{array} \]</cmath>
 
\end{array} \]</cmath>
  

Revision as of 09:00, 20 February 2022

Problem

Let $A$, $B$, $C$ and $D$ be the vertices of a regular tetrahedron, each of whose edges measures $1$ meter. A bug, starting from vertex $A$, observes the following rule: at each vertex it chooses one of the three edges meeting at that vertex, each edge being equally likely to be chosen, and crawls along that edge to the vertex at its opposite end. Let $p = \frac{n}{729}$ be the probability that the bug is at vertex $A$ when it has crawled exactly $7$ meters. Find the value of $n$.

Solution 1 (Single Variable Recursion)

For all nonnegative integers $k,$ let $P(k)$ be the probability that the bug is at vertex $A$ when it has crawled exactly $k$ meters. We wish to find $p=P(7).$

Clearly, we have $P(0)=1.$ For all $k\geq1,$ note that after $k-1$ crawls:

  1. The probability that the bug is at vertex $A$ is $P(k-1),$ and the probability that it crawls to vertex $A$ on the next move is $0.$

  2. The probability that the bug is not at vertex $A$ is $1-P(k-1),$ and the probability that it crawls to vertex $A$ on the next move is $\frac13.$

Together, the recursive formula for $P(k)$ is \[P(k) = \begin{cases} 1 & \mathrm{if} \ k=0 \\ \frac13(1-P(k-1)) & \mathrm{if} \ k\geq1 \end{cases}.\] Two solutions follow from here:

Solution 1.1 (Recursive Formula)

We evaluate $P(7)$ recursively: \begin{alignat*}{6} P(0)&=1, \\ P(1)&=\frac13(1-P(0))&&=0, \\ P(2)&=\frac13(1-P(1))&&=\frac13, \\ P(3)&=\frac13(1-P(2))&&=\frac29, \\ P(4)&=\frac13(1-P(3))&&=\frac{7}{27}, \\ P(5)&=\frac13(1-P(4))&&=\frac{20}{81}, \\ P(6)&=\frac13(1-P(5))&&=\frac{61}{243},\\ P(7)&=\frac13(1-P(6))&&=\frac{182}{729}. \end{alignat*} Therefore, the answer is $n=\boxed{182}.$

~Azjps (Fundamental Logic)

~MRENTHUSIASM (Reconstruction)

Solution 1.2 (Explicit Formula)

Let $P(k)=Q(k)+c$ for some function $Q(k)$ and constant $c.$ For all $k\geq1,$ the recursive formula for $P(k)$ becomes \[Q(k)+c=\frac13(1-(Q(k-1)+c))=\frac13-\frac13Q(k-1)-\frac13c.\] Solving for $Q(k),$ we get \[Q(k)=\frac13-\frac13Q(k-1)-\frac43c.\] For simplicity purposes, we set $c=\frac14,$ which gives \[Q(k)=-\frac13Q(k-1).\] Clearly, $Q(0),Q(1),Q(2),\ldots$ is a geometric sequence with the common ratio $\frac{Q(k)}{Q(k-1)}=-\frac13.$ Substituting $P(0)=1$ and $c=\frac14$ into $P(0)=Q(0)+c$ produces $Q(0)=\frac34,$ the first term of the geometric sequence.

For all nonnegative integers $k,$ the explicit formula for $Q(k)$ is \[Q(k)=\frac34\left(-\frac13\right)^k,\] and the explicit formula for $P(k)$ is \[P(k)=\frac34\left(-\frac13\right)^k+\frac14.\] Finally, the requested probability is $p=P(7)=\frac{182}{729},$ from which $n=\boxed{182}.$

~MRENTHUSIASM

Solution 2 (Multivariable Recursion by Algebra)

Denominator

There are $3^7$ ways for the bug to make $7$ independent crawls without restrictions.

Numerator

Let $V_k$ denote the number of ways for the bug to crawl exactly $k$ meters starting from vertex $V$ and ending at vertex $A,$ where $V\in\{A,B,C,D\}$ and $k$ is a positive integer. We wish to find $A_7.$

Since the bug must crawl to vertex $B,C,$ or $D$ on the first move, we have \begin{align*} A_7&=B_6+C_6+D_6 \\ &=(A_5+C_5+D_5)+(A_5+B_5+D_5)+(A_5+B_5+C_5) \\ &=A_5+2(A_5+B_5+C_5+D_5) \\ &=A_5+2S_5, \end{align*} where $S_k=A_k+B_k+C_k+D_k.$

More generally, we get \[A_{k+2}=A_k+2S_k. \qquad\qquad (\spadesuit)\] For $S_k,$ note that

  1. Base Case:

    2. \begin{align*} S_1&=A_1+B_1+C_1+D_1 \\ &=0+1+1+1 \\ &=3. \end{align*}

  2. Recursive Case:

    3. \begin{align*} S_{k+1}&=A_{k+1}+B_{k+1}+C_{k+1}+D_{k+1} \\ &=(B_k+C_k+D_k)+(A_k+C_k+D_k)+(A_k+B_k+D_k)+(A_k+B_k+C_k) \\ &=3(A_k+B_k+C_k+D_k) \\ &=3S_k. \end{align*}

Clearly, $S_1,S_2,S_3,\ldots$ is a geometric sequence with the first term $S_1=3$ and the common ratio $\frac{S_{k+1}}{S_k}=3.$ Therefore, its explicit formula is \[S_k=3^k. \qquad\qquad (\clubsuit)\] Recall that $A_1=0.$ By $(\spadesuit)$ and $(\clubsuit),$ we rewrite $A_7$ recursively: \begin{align*} A_7 &= A_5+2S_5 \\ &=\left(A_3+2S_3\right)+2S_5 \\ &=\left(\left(A_1+2S_1\right)+2S_3\right)+2S_5 \\ &=2S_1+2S_3+2S_5 \\ &=2(3)+2\left(3^3\right)+2\left(3^5\right). \end{align*} Answer

The requested probability is \[p=\frac{A_7}{3^7}=\frac{2(3)+2\left(3^3\right)+2\left(3^5\right)}{3^7}=\frac{2(1)+2\left(3^2\right)+2\left(3^4\right)}{3^6}=\frac{182}{729},\] from which $n=\boxed{182}.$

~MRENTHUSIASM

Solution 3 (Multivariable Recursion by Table)

Define notation $V_k$ as Solution 2 does.

In fact, we can generalize the following relationships for all nonnegative integers $k:$ \begin{align*} A_0&=1, \\ B_0&=0, \\ C_0&=0, \\ D_0&=0, \\ A_{k+1}&=B_k+C_k+D_k, \\ B_{k+1}&=A_k+C_k+D_k, \\ C_{k+1}&=A_k+B_k+D_k, \\ D_{k+1}&=A_k+B_k+C_k. \\ \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{6mm}&\hspace{6mm}&\hspace{6mm}&\hspace{6mm}&\hspace{6mm}&\hspace{6mm}&& \\ [-2.5ex] \boldsymbol{k} & \boldsymbol{0} & \boldsymbol{1} & \boldsymbol{2} & \boldsymbol{3} & \boldsymbol{4} & \boldsymbol{5} & \boldsymbol{6} & \boldsymbol{7} \\ \hline \hline &&&&&&&& \\ [-2.25ex] \boldsymbol{A_k} &1&0&3&6&21&60&183&546 \\ \hline &&&&&&&& \\ [-2.25ex] \boldsymbol{B_k} &0&1&2&7&20&61&182&547 \\ \hline &&&&&&&& \\ [-2.25ex] \boldsymbol{C_k} &0&1&2&7&20&61&182&547 \\ \hline &&&&&&&& \\ [-2.25ex] \boldsymbol{D_k} &0&1&2&7&20&61&182&547 \\ \end{array}\] Note that the paths from $V$ to $A$ and the paths from $A$ to $V$ have one-to-one correspondence. So, we must get \[A_k+B_k+C_k+D_k=3^k\] for all values of $k.$

The requested probability is \[p=\frac{A_7}{3^7}=\frac{546}{2187}=\frac{182}{729},\] from which $n=\boxed{182}.$

~MRENTHUSIASM

Solution 4 (Single Variable Version of Solution 2)

Let $a_n$ denotes the number of ways that the bug arrives at $A$ after crawling $n$ meters, then we have $a_1=0$.

Notice that there is respectively $1$ way to arrive at $A$ for each of the different routes after the previous $n-1$ crawls, excluding the possibility that the bug ends up at $A$ after the $(n-1)$th crawl (as it will be forced to move somewhere else.). Thus, we get the recurrence relation \[a_n=3^{n-1}-a_{n-1}.\] Quick calculations yield \begin{align*} a_7&=3^6-a_6\\ &=3^6-\left(3^5-3^4+3^3-3^2+3-a_1\right)\\ &=546. \end{align*} Thus, $p=\frac{546}{3^7}=\frac{182}{729}\Longrightarrow n=\boxed{182}$.

~Nafer

Solution 5 (Generating Functions and Roots of Unity Filter)

The generating function for a problem with this general form ($4$ states, $n$ steps) is $(x+x^2+x^3)^n$, so the generating function of interest for this problem is $(x+x^2+x^3)^7$. Our goal is to find the coefficients of every $x^{4n}$ and add them up before dividing by $3^7$. We can do this by applying a roots of unity filter.

Let $\omega = e^{i\pi / 2}$. We have that if $G(x) = (x+x^2+x^3)^7$, then \[\frac{G(1) + G(\omega) + G(\omega^2) + G(\omega^3)}{4} = \frac{2187-1-1-1}{4} = 546.\] From here, the desired probability is $\frac{546}{2187} = \frac{182}{729}$. Therefore, the answer is $n=\boxed{182}$.

~RedFlame2112

Solution 6 (Partitions)

We can find the number of different times the bug reaches vertex $A$ before the $7$th move, and use these smaller cycles to calculate the number of different ways the bug can end up back at $A.$

Define $f(x)$ to be the number of paths of length $x$ which start and end at $A$ but do not pass through $A$ otherwise. Obviously $f(1) = 0.$ In general for $f(x),$ the bug has three initial edges to pick from. From there, since the bug cannot return to $A$ by definition, the bug has exactly two choices. This continues from the $2$nd move up to the $(x-1)$th move. The last move must be a return to $A,$ so this move is determined. So $f(x) = 2^{x-2}3.$

Now we need to find the number of cycles by which the bug can reach $A$ at the end. Since $f(1) = 0,$ we know that $f(6)$ cannot be used, as on the $7$th move the bug cannot move from $A$ to $A.$ So we need to find the number of partitions of $7$ using only $2,3,4,5,$ and $7.$ These are $f(2)f(2)f(3),f(2)f(5),f(3)f(4),$ and $f(7).$ We can calculate these and sum them up using our formula. Also, order matters, so we need to find the number of ways to arrange each partition: \[{3\choose1}f(2)f(2)f(3) + {2\choose1}f(2)f(5) + {2\choose1}f(3)f(4) + f(7) = 3(3)(3)(2\cdot3) + 2(3)(2^33) + 2(2\cdot3)(2^23) + (2^53) = 546.\] Finally, this is a probability question, so we divide by $3^7,$ or $\frac{546}{3^7} = \frac{182}{3^6}.$ The answer is $n=\boxed{182}.$


Solution 7 (Dynamic Programming)

Let $A(n)$ be the probability the bug lands on vertex A after crawling $n$ meters, $B(n)$ be the probability the bug lands on vertex B after crawling $n$ meters and etc.

$A(n) = \frac13 B(n-1) + \frac13 C(n-1) + \frac13 D(n-1)$, $B(n) = C(n) = D(n)$, $A(n) = B(n-1)$

$B(n) = \frac{A(n-1) + C(n-1) + D(n-1)}{3}$

$C(n) = \frac{A(n-1) + B(n-1) + D(n-1)}{3}$

$D(n) = \frac{A(n-1) + B(n-1) + C(n-1)}{3}$

\[ \begin{array}[b]{ccccc} n & A(n) & B(n) & C(n) & D(n) \\ & & & & \\ 1 & 0 & \frac13 & \frac13 & \frac13 \\ & & & & \\ 2 & \frac13 & \frac29 & \frac29 & \frac29 \\ & & & & \\ 3 & \frac29 & \frac{7}{27} & \frac{7}{27} & \frac{7}{27} \\ & & & & \\ 4 & \frac{7}{27} & \frac{20}{81} & \frac{20}{81} & \frac{20}{81}\\ & & & & \\ 5 & \frac{20}{81} & \frac{61}{243} & \frac{61}{243} & \frac{61}{243} \\ & & & & \\ 6 & \frac{61}{243} & \frac{182}{729} & \frac{182}{729} & \frac{182}{729} \\ & & & & \\ 7 & \frac{182}{729} & \frac{547}{2187} & \frac{547}{2187} & \frac{547}{2187} \end{array} \]

To be continued......

~isabelchen

Remark

Here is a similar problem from another AIME test: 2003 AIME II Problem 13, in which we have an equilateral triangle instead.

See also

1985 AIME (Problems • Answer Key • Resources)
Preceded by
Problem 11 		Followed by
Problem 13
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1985_AIME_Problems/Problem_12&oldid=171678"