Difference between revisions of "2003 AIME II Problems/Problem 13"

Revision as of 16:21, 28 February 2016

Problem

A bug starts at a vertex of an equilateral triangle. On each move, it randomly selects one of the two vertices where it is not currently located, and crawls along a side of the triangle to that vertex. Given that the probability that the bug moves to its starting vertex on its tenth move is $m/n,$ where $m$ and $n$ are relatively prime positive integers, find $m + n.$

Solution

Solution 1

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=683$

Solution 2

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 $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<=10$ . 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}$

@@ Line 27: / Line 27: @@
 ===Solution 3===
-Label the vertices of the triangle <math>A,B,C</math> with the ant starting at <math>A</math>. We will make a table of the number of ways to get to <math>A,B,C</math> in <math>n</math> moves <math>n<=10</math>. The values of the table are calculated from the fact that the number of ways from a vertex say <math>A</math> in <math>n</math> ways equals the number of ways to get to <math>B</math> in <math>n-1</math> ways plus the number of ways to get to <math>C</math> in <math>n-1</math> ways.
+Label the vertices of the triangle <math>A,B,C</math> with the ant starting at <math>A</math>. We will make a table of the number of ways to get to <math>A,B,C</math> in <math>n</math> moves <math>n<=10</math>. The values of the table are calculated from the fact that the number of ways from a vertex say <math>A</math> in <math>n</math> steps equals the number of ways to get to <math>B</math> in <math>n-1</math> steps plus the number of ways to get to <math>C</math> in <math>n-1</math> steps.
 <cmath>\begin{array}{|l|ccc|}
 \multicolumn{4}{c}{\text{Table}}\\\hline

2003 AIME II (Problems • Answer Key • Resources)
Preceded by Problem 12	Followed by Problem 14
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search