AIME 1985 · 第 12 题

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 ~MRENTHUSIASM

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{aligned} 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{aligned}$$ 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:

$$\begin{aligned} S_1&=A_1+B_1+C_1+D_1 \\ &=0+1+1+1 \\ &=3. \end{aligned}$$ 2. Recursive Case:

$$\begin{aligned} 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{aligned}$$ 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{aligned} 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{aligned}$$ 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{aligned} 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{aligned}$$ 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{aligned} a_7&=3^6-a_6\\ &=3^6-\left(3^5-3^4+3^3-3^2+3-a_1\right)\\ &=546. \end{aligned}$$ Thus, $p=\frac{546}{3^7}=\frac{182}{729}\Longrightarrow n=\boxed{182}$.

~Nafer

Solution 5 (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.

Note that $A(1)=0$ and $B(1)=C(1)=D(1)=\frac13.$ For $n\geq2,$ the probability that the bug land on each vertex after $n$ meters is $\frac13$ the sum of the probability the bug land on other vertices after crawling $n-1$ meters. So, we have

$$\begin{aligned} A(n) &= \frac13 \cdot [B(n-1) + C(n-1) + D(n-1)], \\ B(n) &= \frac13 \cdot [A(n-1) + C(n-1) + D(n-1)], \\ C(n) &= \frac13 \cdot [A(n-1) + B(n-1) + D(n-1)], \\ D(n) &= \frac13 \cdot [A(n-1) + B(n-1) + C(n-1)]. \end{aligned}$$ It follows that $A(n) = B(n-1) = C(n-1) = D(n-1).$

We construct the following table:

Therefore, the answer is $n = \boxed{182}.$

~isabelchen

Solution 6 (Generating Functions and Roots of Unity Filter / Casework)

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$. Here we have two ways to proceed:

1. 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

2. Casework

We can factor $(x+x^2+x^3)^7$ as $x^7(1+x+x^2)^7.$ The $x^{4n}$ coefficients of $(x+x^2+x^3)^7$ will be the same as the $x^{4n+1}$ coefficients of $(1+x+x^2)^7.$ The possible values for $4n+1$ would then be $1,$ $5,$ $9,$ and $13.$ Because $1+13=5+9=14,$ the coefficients of $x^1$ and $x^{13}$ are equal and so are the coefficients of $x^5$ and $x^9.$ To make an $x$ term, we need $6$ "$1$" terms and one "$x$" term multiplied together. There are $7$ ways to arrange these numbers. The coefficient of the $x^5$ term will be the sum of the number of the possible arrangements for these numbers:

$$\begin{aligned} 0000122&=105\text{ arrangements}, \\ 0001112&=140\text{ arrangements}, \\ 0011111&=21\text{ arrangements}. \end{aligned}$$ Thus, the coefficient of the $x^5$ term is $105+140+21=266.$ From here, the desired probability is $\frac{2(7+266)}{2187}=\frac{546}{2187}=\frac{182}{729}.$ Thus, our answer is $\boxed{182}.$

~BS2012

Solution 7 (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 8 (Sequences)

Note that this problem is basically equivalent to the following: How many distinct sequences of $8$ integers $a_1, a_2, a_3, \ldots, a_8$ are there such that $a_1 = a_8 = 1,$ $a_i \in \{1, 2, 3, 4\}$ for all $2 \leq i\leq 8,$ and $a_i \neq a_{i+1}$ for all $1 \leq i \leq 7$?

Now consider the $8$ integers modulo $4.$ Let $b_1, b_2, b_3, \ldots, b_7$ be a new sequence of integers such that $b_i = a_{i+1} - a_i \mod 4$ for all $1 \leq i \leq 7.$

Note that the condition is equivalent to that $b_i \in \{1, 2, 3\}$ for all $1 \leq i \leq 7,$ and since $a_1 \mod 4 = a_8 \mod 4,$ $b_1 + b_2 + \cdots + b_7$ must be a multiple of $4.$

Thus, our desired number of paths is equivalent to the number of ordered septuples of positive integers $(b_1, b_2, \ldots, b_7)$ such that $b_i \in \{1, 2, 3\}$ for all $1 \leq i \leq 7$ and $b_1 + b_2 + \cdots + b_7$ is congruent to $0 \mod 4.$

We will now proceed with casework on the number of $2$s in the septuple.

One $2$: There are $\dbinom{7}{1} = 7$ ways to arrange the $2$, and $\dbinom{6}{0} + \dbinom{6}{2} + \dbinom{6}{4} + \dbinom{6}{6} = 2^5$ valid ways (the proof of this combinatorial identity is left as an exercise to the reader) to arrange the $1$s and $3$s.

Three $2$s: There are $\dbinom{7}{3} = 35$ ways to arrange the $2$s, and $\dbinom{4}{1} + \dbinom{4}{3} = 2^3$ valid ways to arrange the $1$s and $3$s.

Five $2$s: There are $\dbinom{7}{5} = 21$ ways to arrange the $2$s, and $\dbinom{2}{0} + \dbinom{2}{2} = 2$ valid ways to arrange the $1$s and $3$s.

Adding up our cases, we obtain $7 \cdot 32 + 35 \cdot 8 + 21 \cdot 2 = 546$ valid sequences. Dividing by the total number of paths without restrictions, $3^7 = 2187,$ our desired probability is $\frac{546}{2187} = \frac{182}{729},$ giving an answer of $\boxed{182}.$

~fidgetboss_4000

Solution 9

We instead find the probability that the bug is NOT at vertex $A$ after crawling $n$ meters (equivalent to moving $n$ times). Call $A_n$ the probability that the bug IS at vertex $A$ after $n$ moves; call $O_n$ the probability that the bug is on some other vertex. We have the following recurrence relations.

$$A_n = \frac{1}{3}O_{n-1}$$ $$O_n = A_{n-1} + \frac{2}{3}O_{n-1}$$ However, we can calculate $A_{n-1}$ in terms of $O_n$; take $n = k-1$, and we have

$$A_{k-1} = \frac{1}{3}O_{k-2}$$ . Substituting this into our equation for $O$, we have that

$$O_n = \frac{1}{3}O_{n-2} + \frac{2}{3}O_{n-1}$$ . We also have the conditions that $O_0 = 0$ (the bug will not be at vertex other than $A$ on the "0th" move) and $O_1 = 1$ (the bug will be at a vertex other than $A$ after the $1st$ move). Iteratively calculating $O_7$, we find that it is equal to $\frac{547}{729}$ (I will not do this calculation here; you can do it manually if you wish to check). However, this is the probability that the ant is NOT at vertex $A$ after $7$ moves; then its complement, $\frac{182}{729}$ is the probability that the ant IS at vertex $A$ after $7$ moves, so our answer is $\boxed{182}$.

~ cxsmi

Solution 10 (Linear Algebra)

Think of the problem as a state machine with a transition matrix. State 1 is if the bug is at A, State 2 is if the bug is not at A. In vector form we can represent state 1 as $\begin{bmatrix} 1 \\ 0 \end{bmatrix}$ and state 2 as $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$. Our transition matrix $T =\begin{pmatrix} 0 & \frac{1}{3} \\ 1 & \frac{2}{3} \end{pmatrix}$. Thus the probability of being in each state after k moves is $T^{k}\begin{bmatrix} 1 \\ 0 \end{bmatrix}=\begin{pmatrix} 0 & \frac{1}{3} \\ 1 & \frac{2}{3} \end{pmatrix}^{k}\begin{bmatrix} 1 \\ 0 \end{bmatrix}$. Those familiar with linear algebra will recognize the need to diagonalize the transition matrix through eigendecomposition. In short, the eigenvalues of the transition matrix are $-\frac{1}{3}$ and 1, with corresponding eigenvector basis of $\begin{pmatrix} 1 \\ -1 \end{pmatrix}, \begin{pmatrix} \frac{1}{3} \\ 1 \end{pmatrix}$. Thus $T = Q \Lambda Q^{-1} = \begin{pmatrix} 1 & \frac{1}{3} \\ -1 & 1 \end{pmatrix}\begin{pmatrix} -\frac{1}{3} & 0\\ 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & \frac{1}{3}\\ -1 & 1 \end{pmatrix}^{-1} = \begin{pmatrix} 1 & \frac{1}{3} \\ -1 & 1 \end{pmatrix}\begin{pmatrix} -\frac{1}{3} & 0\\ 0 & 1 \end{pmatrix}\begin{pmatrix} \frac{3}{4} & -\frac{1}{4}\\ \frac{3}{4} & \frac{3}{4} \end{pmatrix}$

Thus $T^{k}\begin{bmatrix} 1 \\ 0 \end{bmatrix}= \begin{pmatrix} 1 & \frac{1}{3} \\ -1 & 1 \end{pmatrix}\begin{pmatrix} (-\frac{1}{3})^{k} & 0\\ 0 & 1^{k} \end{pmatrix}\begin{pmatrix} \frac{3}{4} & -\frac{1}{4}\\ \frac{3}{4} & \frac{3}{4} \end{pmatrix}\begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{pmatrix} \frac{3}{4}(-\frac{1}{3})^{k}+\frac{1}{4} & -\frac{1}{4}(-\frac{1}{3})^{k}+\frac{1}{4}\\ -\frac{3}{4}(-\frac{1}{3})^{k}+\frac{3}{4} & \frac{1}{4}(-\frac{1}{3})^{k}+\frac{3}{4} \end{pmatrix}\begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} \frac{3}{4}(-\frac{1}{3})^{k}+\frac{1}{4} \\ -\frac{3}{4}(-\frac{1}{3})^{k}+\frac{3}{4} \end{bmatrix}$.

The probability we seek is the top entry of this vector for k = 7, or $\frac{182}{729}$.

Solution 11 (Regular Casework)

Perhaps you are not very good at recursion. Let $A$ denote the vertex $A,$ and let $N$ denote a vertex other than $A.$ Now the moves of the bug must look something like this:

$$N - - - - - A.$$ Note that the bug cannot travel to $A$ twice in a row, meaning it can't have an $A$ following an $A,$ so there must be at least one $N$ in between. Therefore, the bug can only move to $A$ a maximum of $3$ times (including the last one). Therefore, we will do casework based on how many times the bug moves to vertex $A.$ $\newline$ $\newline$ Case $1: \text{3 As}$

There are three ways for the bug to move in this case:

$$\text{N A N A N N A},$$ $$\text{N A N N A N A},$$ $$\text{N N A N A N A}.$$ $\newline$

Let $P(XY)$ denote the probability that the bug moves from vertex $X$ to vertex $Y.$ $\newline$ $P(NA) = \frac{1}{3},$ because from a vertex $N$ there are three ways to go, with only one of them being $A.$ $\newline$ $P(AN) = 1,$ self explanatory. $\newline$ $P(NN) = \frac{2}{3},$ also self explanatory. $\newline$ Now, using this (by multiplying the probabilities for each pair of consecutive letters), we find that each configuration has the same probability: $(P(NN))(P(NA))^3 = \frac{2}{81}.$ Since each of these three configurations has this probability, we only need to multiply by $3,$ giving $\frac{2(3)}{81} = \frac{2}{27}$ so far. $\newline$ $\newline$ Case $2: \text{2 As}$

This is a little simpler. The configuration:

$$N N N N A N A,$$ where $A$ can occupy any space from the second to the fifth. Note that each occupation gives the same probability once again, so we have $(5-(2-1))\times (P(NN))^3(P(NA))^2 = 4\times \left(\frac{2}{3}\right)^3\left(\frac{1}{3}\right)^2 = \frac{32}{243}.$ $\newline$ $\newline$ Case $3:\text{1 A}$ Configuration:

$$N N N N N N A$$ The probability of this is simply $(P(NN))^5(P(NA)) = \frac{2^5}{3^6} = \frac{32}{729}.$

Adding this all up, we have

$$\frac{2}{27} + \frac{32}{243} + \frac{32}{729} = \frac{54+96+32}{729} = \frac{182}{729} \Longrightarrow \boxed{182}.$$ ~ martianrunner

Remark

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

There is another similar problem from the AMC8: 2022 AMC 8 Problems/Problem 25, where we have the same question, just with less steps