Difference between revisions of "2003 AIME II Problems/Problem 13"
Dgreenb801 (talk | contribs) |
(Added another solution) |
||
| Line 3: | Line 3: | ||
== Solution == | == Solution == | ||
| + | |||
| + | ===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>. | 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>. | ||
| + | |||
| + | ===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., <math>\#CW - \#CCW \equiv 0 \pmod{3}</math>. Since <math>\#CW + \#CCW = 10</math>, it is only possible that <math>(\#CW,\, \#CCW) = (5,5), (8,2), (2,8)</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>. | ||
== 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 05:08, 1 March 2009
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 
where 
and 
are relatively prime positive integers, find 
Solution
Solution 1
After n moves, there are 
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 
moves. So after 1 move, there are 0 ways the get to the start. After 2 moves, there are 
ways to get to the start. After 3 moves, there are 
ways to get to the start. Thus after 10 moves, there are 
ways to get to the start, so the probability is 
and the answer is 
.
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., 
. Since 
, it is only possible that 
.
In the first case, we pick 
out of the ant's 
steps to be clockwise, for a total of 
paths. In the second case, we choose 
of the steps to be clockwise, and in the third case we choose 
to be clockwise. Hence the total number of ways to return to the original vertex is 
. Since the ant has two possible steps at each point, there are 
routes the ant can take, and the probability we seek is 
, and the answer is .
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 | ||
