1985 AIME Problems/Problem 12
Problem
Let ,
,
and
be the vertices of a regular tetrahedron each of whose edges measures 1 meter. A bug, starting from vertex
, observes the following rule: at each vertex it chooses one of the three edges meeting at that vertex, each edge being equally likely to be chosen, and crawls along that edge to the vertex at its opposite end. Let
be the probability that the bug is at vertex
when it has crawled exactly 7 meters. Find the value of
.
Contents
Solutions
Solution 1
Let denote the probability that the bug is at
after it has crawled
meters. Since the bug can only be at vertex
if it just left a vertex which is not
, we have
. We also know
, so we can quickly compute
,
,
,
,
,
and
, so the answer is
. One can solve this recursion fairly easily to determine a closed-form expression for
.
Solution 2
We can find the number of different times the bug reaches vertex before the 7th move, and use these smaller cycles to calculate the number of different ways the bug can end up back at
.
Define to be the number of paths of length
which start and end at
but do not pass through
otherwise. Obviously
. In general for
, the bug has three initial edges to pick from. From there, since the bug cannot return to
by definition, the bug has exactly two choices. This continues from the 2nd move up to the
th move. The last move must be a return to
, so this move is determined. So
.
Now we need to find the number of cycles by which the bug can reach at the end. Since
,
cannot be used since on the 7th move the bug cannot move from
to
. So we need to find the number of partitions of 7 using only 2,3,4,5, and 7. These are
,
,
, and
. We can calculate these and sum them up using our formula. Also, order matters, so we need to find the number of ways to arrange each partition.
![${3\choose1}f(2)f(2)f(3) + {2\choose1}f(2)f(5) + {2\choose1}f(3)f(4) + f(7)$](http://latex.artofproblemsolving.com/c/8/1/c812b183c3cf604b67ca9204ba051a695042977d.png)
![$= 3(3)(3)(2\cdot3) + 2(3)(2^33) + 2(2\cdot3)(2^23) + (2^53)$](http://latex.artofproblemsolving.com/8/7/9/87916ffa4c9bf4f5e0216dda2aa6471dd91befa9.png)
![$= 546$](http://latex.artofproblemsolving.com/b/c/b/bcb42277d86dcd7fef7988f6a45f711227bcb48c.png)
Finally, this is a probability question, so we divide by :
.
Solution 3
There exists a simple heuristic method to arrive at the answer to this question, due to Simon Rubinstein-Salzedo, as follows: after a couple of moves, the randomness of movement of the bug and smallness of the system ensures that we should expect its probability distribution to be very close to uniform. In particular, we would expect to be very close to
for decently-sized
, for example
. (In fact, from looking at the previous solution we can see that it is already close when
, and in fact, the earlier values are also the best possible approximations given the restraints on where the bug can be.) Since we know the answer is of the form
, we realize that
must be very close to
, as indeed it is.
Solution 4 (Cheap Solution)
Only do this if you don't know how to solve the problem and want to make a good guess. Since there are 4 vertices of a tetrahedron, there is approximately a 1/4 probability of coming back to A after 7 moves. Dividing 729 by 4 gives a number between 182 and 183. If the ant continuously alternates his location from A to some other vertice, in the end, it will not be at A. Therefore we chose the smaller number, 182. - Rocket123
Solution 5
Let denote the number of ways that the bug arrives at
after crawling
meters, then we have
.
Notice that is basically the number of different routes for its previous
crawls excluding the possibility that the bug ends up at
after crawling
meters.
See also
- 2003 AIME II Problems/Problem 13 - very similar problem with an equilateral triangle
1985 AIME (Problems • Answer Key • Resources) | ||
Preceded by Problem 11 |
Followed by Problem 13 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |