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

(Solution)
(Solution)
Line 5: Line 5:
  
 
===Solution 1===
 
===Solution 1===
After n moves, there are <math>2^n</math> possible paths for the ant. But the key is to realize that the number of paths that get back the the start after n moves is the same as the number of paths the do NOT get the ant to the start after <math>n-1</math> moves. So after 1 move, there are 0 ways the get to the start. After 2 moves, there are <math>2^1-0</math> ways to get to the start. After 3 moves, there are <math>2^2-(2^1-0)</math> ways to get to the start. Thus after 10 moves, there are <math>2^9-(2^8-(2^7-(2^6-(2^5-(2^4-(2^3-(2^2-2)))))))= 342</math> ways to get to the start, so the probability is <math>342/1024=171/512</math> and the answer is <math>683</math>.
+
Let <math>P_n</math> represent the probability that the bug is at its starting vertex after <math>n</math> moves. If the bug is on its starting vertex after <math>n</math> moves, then it must be not on its starting vertex after <math>n-1</math> moves. Thus <math>P_n=\frac{1}{2}(1-P_{n-1})</math>.
 +
<math>P_0=1</math>, so now we can build it up:
 +
 
 +
<math>P_1=0</math>,
 +
<math>P_2=\frac{1}{2}</math>,
 +
<math>P_3=\frac{1}{4}</math>,
 +
<math>P_4=\frac{3}{8}</math>,
 +
<math>P_5=\frac{5}{16}</math>,
 +
<math>P_6=\frac{11}{32}</math>,
 +
<math>P_7=\frac{21}{64}</math>,
 +
<math>P_8=\frac{43}{128}</math>,
 +
<math>P_9=\frac{85}{256}</math>,
 +
<math>P_{10}=\frac{171}{512}</math>,
 +
 
 +
Thus the answer is <math>171+512=683</math>
  
 
===Solution 2===
 
===Solution 2===
Line 23: Line 37:
 
10 &342 &341 &341 \\hline
 
10 &342 &341 &341 \\hline
 
\end{tabular}</math>
 
\end{tabular}</math>
 
===Solution 4===
 
Let <math>P_n</math> represent the probability that the bug is at its starting vertex after <math>n</math> moves. If the bug is on its starting vertex after <math>n</math> moves, then it must be not on its starting vertex after <math>n-1</math> moves. Thus <math>P_n=\frac{1}{2}(1-P_{n-1})</math>.
 
<math>P_0=1</math>, so now we can build it up:
 
 
<math>P_1=0</math>,
 
<math>P_2=\frac{1}{2}</math>,
 
<math>P_3=\frac{1}{4}</math>,
 
<math>P_4=\frac{3}{8}</math>,
 
<math>P_5=\frac{5}{16}</math>,
 
<math>P_6=\frac{11}{32}</math>,
 
<math>P_7=\frac{21}{64}</math>,
 
<math>P_8=\frac{43}{128}</math>,
 
<math>P_9=\frac{85}{256}</math>,
 
<math>P_{10}=\frac{171}{512}</math>,
 
 
Thus the answer is <math>171+512=683</math>
 
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=2003|n=II|num-b=12|num-a=14}}
 
{{AIME box|year=2003|n=II|num-b=12|num-a=14}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 20:19, 6 March 2015

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. 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$ ways equals the number of ways to get to $B$ in $n-1$ ways plus the number of ways to get to $C$ in $n-1$ ways. $Unknown environment 'tabular'$ (Error compiling LaTeX. Unknown error_msg)

See also

2003 AIME II (ProblemsAnswer KeyResources)
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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png