AIME 2003 II · 第 13 题

Solutions

Solution 1 (Easiest)

Let $P_n$ represent the probability that the bug is at its starting vertex after $n$ moves. If the bug is on its starting vertex after $n$ moves, then it must be not on its starting vertex after $n-1$ moves. At this point it has $\frac{1}{2}$ chance of reaching the starting vertex in the next move. Thus $P_n=\frac{1}{2}(1-P_{n-1})$. $P_0=1$, so now we can build it up:

$P_1=0$, $P_2=\frac{1}{2}$, $P_3=\frac{1}{4}$, $P_4=\frac{3}{8}$, $P_5=\frac{5}{16}$, $P_6=\frac{11}{32}$, $P_7=\frac{21}{64}$, $P_8=\frac{43}{128}$, $P_9=\frac{85}{256}$, $P_{10}=\frac{171}{512}$,

Thus the answer is $171+512=$$\boxed{683}$

Solution 2 (also easiest)

Consider there to be a clockwise and a counterclockwise direction around the triangle. Then, in order for the ant to return to the original vertex, the net number of clockwise steps must be a multiple of 3, i.e., $\#CW - \#CCW \equiv 0 \pmod{3}$. Since $\#CW + \#CCW = 10$, it is only possible that $(\#CW,\, \#CCW) = (5,5), (8,2), (2,8)$.

In the first case, we pick $5$ out of the ant's $10$ steps to be clockwise, for a total of ${10 \choose 5}$ paths. In the second case, we choose $8$ of the steps to be clockwise, and in the third case we choose $2$ to be clockwise. Hence the total number of ways to return to the original vertex is ${10 \choose 5} + {10 \choose 8} + {10 \choose 2} = 252 + 45 + 45 = 342$. Since the ant has two possible steps at each point, there are $2^{10}$ routes the ant can take, and the probability we seek is $\frac{342}{2^{10}} = \frac{171}{512}$, and the answer is $\boxed{683}$.

Solution 3

Label the vertices of the triangle $A,B,C$ with the ant starting at $A$. We will make a table of the number of ways to get to $A,B,C$ in $n$ moves $n\leq10$. The values of the table are calculated from the fact that the number of ways from a vertex say $A$ in $n$ steps equals the number of ways to get to $B$ in $n-1$ steps plus the number of ways to get to $C$ in $n-1$ steps.

$$\begin{array}{|l|ccc|} \multicolumn{4}{c}{\text{Table}}\\\hline \text{Step}&A&B&C \\\hline 1 &0 &1 &1 \\ 2 &2 &1 &1 \\ 3 &2 &3 &3\\ \vdots &\vdots&\vdots&\vdots \\ 10 &342 &341 &341 \\\hline \end{array}$$ Therefore, our answer is $512+171=\boxed{683}.$

Notice the pattern that there are $\left\lceil\frac{2^n}{3}\right\rceil$ way to get to $A$ for even $n$ moves. Thus, there are $\left\lceil\frac{2^{10}}{3}\right\rceil=342$ ways.

Solution 4

Notice that this problem can be converted into a Markov Chain transition matrix.

The transition matrix is { {0,1,1}, {1,0,1} , {1,1,0} } * (1/2) . Then use the exponentiation method of squaring ( A*A---(A^2)*(A^2)---(A^4*A^4)--(A^8*A^2) to get the transition value of 342. Divide by 2^10 for the probability, reduce fractions, for the result of 171+512 = 683.

Solution 4.1 (solution 4 but rigorized and generalized)

As a note, do NOT do this on the exam as it will eat up your time, but feel free to experiment around with this if you have a good enough understanding of linear algebra. This writeup will be extremely lengthy because I am assuming just very basic concepts of linear algebra. The concepts here extend to higher levels of mathematics, so feel free to explore more in depth so that you can end up solving almost any variation of this classic problem.

4.1.1: Conceptual Setup

There are a possible of 3 states for this problem, so we can model the problem as a stochastic process. The resulting process has a transition matrix of:

$$\hat{T} = \begin{bmatrix} 0 & 0.5 & 0.5\\ 0.5 & 0 & 0.5\\ 0.5 & 0.5 & 0 \end{bmatrix}$$ We aim to diagonalize this transition matrix to make it easier to exponentiate by converting it into what's known as it's Jordan Canonical Form.

4.1.2: Eigenvalue/vector bash

In order to do this, we must extract the eigenvalues and eigenvectors of the matrix. The eigenpolynomial for this matrix is obtained by calculating this matrix's determinant with $0-\lambda$ about it's main diagonal like so:

$$\hat{T}_{\lambda} = \begin{bmatrix} 0-\lambda & 0.5 & 0.5\\ 0.5 & 0-\lambda & 0.5\\ 0.5 & 0.5 & 0-\lambda \end{bmatrix}$$ We have the matrix's eigenpolynomial to be $\lambda^3 - \frac{3\lambda}{4} + \frac{1}{4}$, and extracting eigenvalues by setting the polynomial equal to $0$, we have 2 eigenvalues: $\lambda_1 = 1$ of multiplicity 1, and $\lambda_2 = -\frac{1}{2}$ of multiplicity 2. To extract the eigenvectors, we must assess the kernel of this matrix (also known as the null space), or the linear subspace of the domain of $\hat{T}$ where everything gets mapped to the null vector.

We first do this for $\lambda_1$. Taking $-\lambda_1$ across the diagonals to get $\hat{T}_{\lambda_1} = \begin{bmatrix} -1 & 0.5 & 0.5\\ 0.5 & -1 & 0.5\\ 0.5 & 0.5 & -1 \end{bmatrix}$, we first reduce it to reduced row echelon form, which is $\begin{bmatrix} 1 & 0 & -1\\ 0 & 1 & -1\\ 0 & 0 & 0 \end{bmatrix}$. From here, we compute the kernel by setting

$$\begin{bmatrix} 1 & 0 & -1\\ 0 & 1 & -1\\ 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ x_3 \end{bmatrix} = 0$$ . So if we take our free variable $x_3 = 0 = t$, then that means that in the same fashion, $x_1 - x_1 = x_2 - x_2 = 0 = t$, so hence, the kernel of $\hat{T}_{\lambda} = \begin{bmatrix} t\\ t\\ t \end{bmatrix}$, or more simply, $t\begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix}$. $\begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix}$ is the eigenvector corresponding to $\lambda_1$. We do the same computations for our second unique eigenvalue, but I will save the computation to you. There are actually 2 eigenvectors for $\lambda_2$, because the reduced row echelon form for $\hat{T}_{\lambda_2}$ has 2 free variables instead of 1, so our eigenvectors for $\lambda_2$ are $\begin{bmatrix} -1\\ 1\\ 0 \end{bmatrix}, \begin{bmatrix} -1\\ 0\\ 1 \end{bmatrix}$. We are now ready to begin finding the Jordan canonical form

4.1.3 Jordan Canonical Form

In linear algebra, the JCF (which also goes by the name of Jordan Normal Form) is an upper triangular matrix representing a linear transformation over a finite-dimensional complex vector space. Any square matrix that has a Jordan Canonical Form has its field of coefficients extended into a field containing all it's eigenvalues. You can find more information about them on google, as well as exactly how to find them but for now let's get on with the problem. I will skip the computation in this step, largley because this writeup is already gargantuan for a simple AIME problem, and because there are countless resources explaining how to do so.

We aim to decompose $\hat{T}$ into the form $\hat{T} = SJS^{-1}$, where $S$ is a matrix whose columns consist of the eigenvectors of $\hat{T}$, $J$ is the Jordan matrix, and $S^{-1}$ is, well, the inverse of $S$. We have 1 eigenvalue of multiplicity 1, and 1 of multiplicity 2, so based on this info, we set our eigenvalues along the diagonals like so. We have:

$$J = \begin{bmatrix} -\frac{1}{2} & 0 & 0\\ 0 & -\frac{1}{2} & 0\\ 0 & 0 & 1 \end{bmatrix}, S = \begin{bmatrix} -1 & -1 & 1\\ 0 & 1 & 1\\ 1 & 0 & 1 \end{bmatrix}, S^{-1} = \frac{1}{3}\begin{bmatrix} -1 & -1 & 2\\ -1 & 2 & -1\\ 1 & 1 & 1 \end{bmatrix}$$ and so:

$$\hat{T} = \begin{bmatrix} 0 & 0.5 & 0.5\\ 0.5 & 0 & 0.5\\ 0.5 & 0.5 & 0 \end{bmatrix} = SJS^{-1} = \begin{bmatrix} -1 & -1 & 1\\ 0 & 1 & 1\\ 1 & 0 & 1 \end{bmatrix}\begin{bmatrix} -\frac{1}{2} & 0 & 0\\ 0 & -\frac{1}{2} & 0\\ 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} -\frac{1}{3} & -\frac{1}{3} & \frac{2}{3}\\ -\frac{1}{3} & \frac{2}{3} & -\frac{1}{3}\\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \end{bmatrix}$$ Now that we have converted to Jordan Canonical Form, it is extremely easy to compute $\hat{T}^n$.

4.1.4: Using the JCF to calculate the transition matrix to the power of any n, large or small

It is an important fact that for any matrix $K$ with Jordan decomposition $SJ_kS^{-1}$, we have that $K^n = S(J_k)^nS^{-1}$ Using this fact, we aim to find the general solution for the problem. $J^n = \begin{bmatrix} \left(-\frac{1}{2}\right)^n & 0 & 0\\ 0 & \left(-\frac{1}{2}\right)^n & 0\\ 0 & 0 & 1 \end{bmatrix}$, and using the laws of matrix multiplication,

$$SJ^n = \begin{bmatrix} (-1)^{n+1}\left(\frac{1}{2}\right)^n & (-1)^{n+1}\left(\frac{1}{2}\right)^n & 1\\ 0 & \left(-\frac{1}{2}\right)^n & 1\\ \left(-\frac{1}{2}\right)^n & 0 & 1 \end{bmatrix}$$ So finally, our final, generalized transition matrix after any number of steps $n$ is:

$$\hat{T}^n = \begin{bmatrix} \frac{1}{3} - \frac{1}{3}(-1)^{1+n}(2)^{1-n} & \frac{1}{3} + \frac{1}{3}(-1)^{n+1}(2)^{1-(1+n)} & \frac{1}{3} + \frac{1}{3}(-1)^{n+1}(2)^{1-(1+n)}\\ \frac{1}{3} + \frac{1}{3}(-1)^{n+1}(2)^{1-(1+n)} & \frac{1}{3} - \frac{1}{3}(-1)^{1+n}(2)^{1-n} & \frac{1}{3} + \frac{1}{3}(-1)^{n+1}(2)^{1-(1+n)}\\ \frac{1}{3} + \frac{1}{3}(-1)^{n+1}(2)^{1-(1+n)} & \frac{1}{3} + \frac{1}{3}(-1)^{n+1}(2)^{1-(1+n)} & \frac{1}{3} - \frac{1}{3}(-1)^{1+n}(2)^{1-n} \end{bmatrix}$$

4.1.5 just plugging in for this problem lol

For the sake of this problem, we seek the top left element, which is $\frac{1}{3} - \frac{1}{3}(-1)^{1+n}(2)^{1-n}$. Substituting $n=10$ readily gives the probability of the bug reaching it's starting position within 10 moves to be $\frac{171}{512} \implies m+n = \boxed{683}$

And we have also derived formulae for the bug reaching any state within $n$ moves as a byproduct!

~RedFlame2112

Solution 5 (guess & check)

This method does not rigorously get the answer, but it works. As the bug makes more and more moves, the probability of it going back to the origin approaches closer and closer to 1/3. Therefore, after 10 moves, the probability gets close to $341.33/1024$. We can either round up or down. If we round down, we see $341/1024$ cannot be reduced any further and because the only answers on the AIME are below 1000, this cannot be the right answer. However, if we round up, $342/1024$ can be reduced to $171/512$ where the sum 171+512= $\boxed{683}$ is an accepted answer.

Solution 6 (generating functions)

The generating function for this is $(x+x^2)$ since an ant on any vertex of the equilateral triangle can go $120$ degrees or $240$ degrees to a side and simplifying $(x^{120}+x^{240})$ gets you $(x+x^2)$. Since $360$ degrees brings you back to the original vertex then we must find the sum of the coefficients that share a variable with a power divisible by $3$.

Since we take this rotation $10$ times, our function becomes $(x+x^2)^{10}$ which is the same as $x^{10}(x+1)^{10}$. This completely simplified is $x(x+1)^{10}$ and since your maximum power is $11$, we only have to find the coefficients for $3$, $6$, and $9$ ($0$ would apply here but the $x$ is the lowest power there is).

For $x^9$, the coefficient is ${10 \choose 2}$ , and the same goes for $x^3$. For $x^6$, the coefficient is ${10 \choose 5}$ and the final sum for the numerator is $2*{10 \choose 2} + {10 \choose 5}$ . The total sum is $90+252=342$ and for the denominator, it was simply $2^{10}$ and this simplified was $171/512$. Therefore the sum is $683$.

Solution 7 (trees)

Start of with any vertex, say $A$. Denote $a_n$ the number of paths ending where it started. Then notice that for a path to end in the vertex you started on, you must have for the $(n-1)$ case that of the $2^{n-1}$ total paths, we must take away the paths that end in the $(n-1)$-st term where it started off. (Because imagine on the $(n-1)$ move that it landed on vertex $A$. Then if we wanted to find the number of length $n$ paths that end at $A$, we would be able to find that path, because on the $(n-1)$-st move it landed at $A$. You can't go from $A$ to $A$). Hence we have the recursion $a_n=2^{n-1}-a_{n-1}$, with $a_3 = 2$. Now reiterating gives us $a_{10} = 342$, so that the probability is $\frac{342}{2^{10}} = \frac{171}{512}$. So we have $171 + 512 = \boxed{683}$. ~th1nq3r

(Note: One might be confused because you might think maybe "But we only did it for case $A$. Now for $B$ and $C$. Oh wait they are symmetric. So then if this is the correct answer, why am I wrong, or what happened to that factor of $3$?" Well truth be told, I skipped a somewhat major step. Notice that the total amount $2^n$ only comes from if we START OFF at vertex $A$. So we really need to multiply $2^n$ by $3$ to get $3(2^n)$ as the TRUE total amount. However this factor of $3$ doesn't matter because now that we do case work, let $a_n$ once again denote the number of paths starting at vertex $A$. Then abusing symmetry, we have that the number of paths ending where it started as $3(a_n)=3(2^{n-1}-a_{n-1})$. So now when we take the probability, we cancel the factor of $3$, and obtain the same answer as if it were for all three vertices).

Video Solution by Sal Khan

https://www.youtube.com/watch?v=vKMNRcctwL4&list=PLSQl0a2vh4HCtW1EiNlfW_YoNAA38D0l4&index=20 - AMBRIGGS