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

m
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
{{solution}}
+
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>.
  
 
== 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 16:54, 21 January 2008

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

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$.

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