1985 AIME Problems/Problem 12
Contents
- 1 Problem
- 2 Solution 1 (Single Variable Recursion)
- 3 Solution 2 (Multivariable Recursion by Algebra)
- 4 Solution 3 (Multivariable Recursion by Table)
- 5 Solution 4 (Single Variable Version of Solution 2)
- 6 Solution 5 (Partitions)
- 7 Solution 6 (Educated Guess)
- 8 Solution 7 (Educated Guess)
- 9 Remark
- 10 See also
Problem
Let ,
,
and
be the vertices of a regular tetrahedron, each of whose edges measures
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
meters. Find the value of
.
Solution 1 (Single Variable Recursion)
For all nonnegative integers let
be the probability that the bug is at vertex
when it has crawled exactly
meters. We wish to find
Clearly, we have For all
note that after
crawls:
- The probability that the bug is at vertex
is
and the probability that it crawls to vertex
on the next move is
- The probability that the bug is not at vertex
is
and the probability that it crawls to vertex
on the next move is
Together, the recursive formula for is
Two solutions follow from here:
Solution 1.1 (Recursive Formula)
We evaluate recursively:
Therefore, the answer is
~Azjps (Fundamental Logic)
~MRENTHUSIASM (Reconstruction)
Solution 1.2 (Explicit Formula)
Let for some function
and constant
For all
the recursive formula for
becomes
Solving for
we get
For simplicity purposes, we set
which gives
Clearly,
is a geometric sequence with the common ratio
Substituting
and
into
produces
the first term of the geometric sequence.
So, for all nonnegative integers the explicit formula for
is
and the explicit formula for
is
Finally, the requested probability is
from which
~MRENTHUSIASM
Solution 2 (Multivariable Recursion by Algebra)
Denominator
There are ways for the bug to make
independent crawls without restrictions.
Numerator
Let denote the number of ways for the bug to crawl exactly
meters starting from vertex
and ending at vertex
where
and
is a positive integer. We wish to find
Since the bug must crawl to vertex or
on the first move, we have
where
More generally, we get
For
note that
- Base Case:
- Recursive Case:
Clearly, is a geometric sequence with the first term
and the common ratio
Therefore, its explicit formula is
Recall that
By
and
we rewrite
recursively:
Answer
The requested probability is from which
~MRENTHUSIASM
Solution 3 (Multivariable Recursion by Table)
Define notation as Solution 2 does.
In fact, we can generalize the following relationships for all nonnegative integers
Using these equations, we recursively fill out the table below:
Note that the paths from
to
and the paths from
to
have one-to-one correspondence. So, we must get
for all values of
The requested probability is from which
~MRENTHUSIASM
Solution 4 (Single Variable Version of Solution 2)
Let denotes the number of ways that the bug arrives at
after crawling
meters, then we have
.
Notice that there is respectively way to arrive at
for each of the different routes after the previous
crawls, excluding the possibility that the bug ends up at
after the
th crawl (as it will be forced to move somewhere else.). Thus, we get the recurrence relation
Quick calculations yield
Thus,
.
~Nafer
Solution 5 (Partitions)
We can find the number of different times the bug reaches vertex before the
th 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
nd 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
we know that
cannot be used, as on the
th move the bug cannot move from
to
So we need to find the number of partitions of
using only
and
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:
Finally, this is a probability question, so we divide by
or
The answer is
Solution 6 (Educated Guess)
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 solutions 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. The answer is
.
Solution 7 (Educated Guess)
Only do this if you don't know how to solve the problem and want to make a good guess. Since there are vertices of a tetrahedron, there is approximately an
probability of coming back to
after
moves. Dividing
by
gives a number between
and
If the bug continuously alternates its location from
to some other vertex, in the end, it will not be at
Therefore we choose the smaller number,
~Rocket123
Remark
Here is a similar problem from another AIME test: 2003 AIME II Problem 13, in which we have an equilateral triangle instead.
See also
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 |