2003 AIME II Problems/Problem 13
Contents
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 (Easiest)
Let represent the probability that the bug is at its starting vertex after
moves. If the bug is on its starting vertex after
moves, then it must be not on its starting vertex after
moves. At this point it has
chance of reaching the starting vertex in the next move. Thus
.
, so now we can build it up:
,
,
,
,
,
,
,
,
,
,
Thus 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
.
Solution 3
Label the vertices of the triangle with the ant starting at
. We will make a table of the number of ways to get to
in
moves
. The values of the table are calculated from the fact that the number of ways from a vertex say
in
steps equals the number of ways to get to
in
steps plus the number of ways to get to
in
steps.
Therefore, our answer is
Notice the pattern that there are way to get to
for even
moves. Thus, there are
ways.
Solution 4
Notice that this problem can be converted into a Markov Chain transition matrix.
The transition matrix is { {0,1,1}, {1,0,1} , {1,1,0} } * (1/2) . Then use the exponentiation method of squaring ( A*A---(A^2)*(A^2)---(A^4*A^4)--(A^8*A^2) to get the transition value of 342. Divide by 2^10 for the probability, reduce fractions, for the result of 171+512 = 683.
Solution 5 (guess & check)
This method does not rigorously get the answer, but it works. As the bug makes more and more moves, the probability of it going back to the origin approaches closer and closer to 1/3. Therefore, after 10 moves, the probability gets close to . We can either round up or down. If we round down, we see
cannot be reduced any further and because the only answers on the AIME are below 1000, this cannot be the right answer. However, if we round up,
can be reduced to
where the sum 171+512=
is an accepted answer.
Solution 6 (generating functions)
The generating function for this is since an ant on any vertex of the equilateral triangle can go
degrees or
degrees to a side and simplifying
gets you
. Since
degrees brings you back to the original vertex then we must find the sum of the coefficients that share a variable with a power divisible by
.
Since we take this rotation times, our function becomes
which is the same as
. This completely simplified is
and since your maximum power is
, we only have to find the coefficients for
,
, and
(
would apply here but the
is the lowest power there is).
For , the coefficient is
, and the same goes for
. For
, the coefficient is
and the final sum for the numerator is
. The total sum is
and for the denominator, it was simply
and this simplified was
. Therefore the sum is
.
Solution 7 (trees)
Start of with any vertex, say . Denote
the number of paths ending where it started. Then notice that for a path to end in the vertex you started on, you must have for the
case that of the
total paths, we must take away the paths that end in the
-st term where it started off. (Because imagine on the
move that it landed on vertex
. Then if we wanted to find the number of length
paths that end at
, we would be able to find that path, because on the
-st move it landed at
. You can't go from
to
). Hence we have the recursion
, with
. Now reiterating gives us
, so that the probability is
. So we have
.
~th1nq3r
(Note: One might be confused because you might think maybe "But we only did it for case
. Now for
and
. Oh wait they are symmetric. So then if this is the correct answer, why am I wrong, or what happened to that factor of
?" Well truth be told, I skipped a somewhat major step. Notice that the total amount
only comes from if we START OFF at vertex
. So we really need to multiply
by
to get
as the TRUE total amount. However this factor of
doesn't matter because now that we do case work, let
once again denote the number of paths starting at vertex
. Then abusing symmetry, we have that the number of paths ending where it started as
. So now when we take the probability, we cancel the factor of
, and obtain the same answer as if it were for all three vertices).
See also
- 1985 AIME Problems/Problem 12 - very similar problem with a tetrahedron
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.