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 "2003 AIME II Problems/Problem 13"

(→‎Solution 1)
(→‎Solution)
Line 11: Line 11:
  
 
In the first case, we pick <math>5</math> out of the ant's <math>10</math> steps to be clockwise, for a total of <math>{10 \choose 5}</math> paths.  In the second case, we choose <math>8</math> of the steps to be clockwise, and in the third case we choose <math>2</math> to be clockwise.  Hence the total number of ways to return to the original vertex is <math>{10 \choose 5} + {10 \choose 8} + {10 \choose 2} = 252 + 45 + 45 = 342</math>.  Since the ant has two possible steps at each point, there are <math>2^{10}</math> routes the ant can take, and the probability we seek is <math>\frac{342}{2^{10}} = \frac{171}{512}</math>, and the answer is <math>683</math>.
 
In the first case, we pick <math>5</math> out of the ant's <math>10</math> steps to be clockwise, for a total of <math>{10 \choose 5}</math> paths.  In the second case, we choose <math>8</math> of the steps to be clockwise, and in the third case we choose <math>2</math> to be clockwise.  Hence the total number of ways to return to the original vertex is <math>{10 \choose 5} + {10 \choose 8} + {10 \choose 2} = 252 + 45 + 45 = 342</math>.  Since the ant has two possible steps at each point, there are <math>2^{10}</math> routes the ant can take, and the probability we seek is <math>\frac{342}{2^{10}} = \frac{171}{512}</math>, and the answer is <math>683</math>.
 +
 +
===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.
 +
<math>\begin{tabular}[t]{|l|ccc|}
 +
\multicolumn{4}{c}{Table}\\\hline
 +
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{tabular}</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}}

Revision as of 22:48, 11 March 2013

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

After n moves, there are $2^n$ 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 $n-1$ moves. So after 1 move, there are 0 ways the get to the start. After 2 moves, there are $2^1-0$ ways to get to the start. After 3 moves, there are $2^2-(2^1-0)$ ways to get to the start. Thus after 10 moves, there are $2^9-(2^8-(2^7-(2^6-(2^5-(2^4-(2^3-(2^2-2)))))))= 342$ ways to get to the start, so the probability is $342/1024=171/512$ and the answer is $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. $\begin{tabular}[t]{|l|ccc|} \multicolumn{4}{c}{Table}\\\hline 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{tabular}$ (Error compiling LaTeX. Unknown error_msg)

See also

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2003_AIME_II_Problems/Problem_13&oldid=51701"