Difference between revisions of "1985 AIME Problems/Problem 12"
(→See also) |
(problem and solution) |
||
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
| + | Let <math>A</math>, <math>B</math>, <math>C</math> and <math>D</math> be the [[vertex | vertices]] of a regular [[tetrahedron]] each of whose [[edge]]s measures 1 meter. A bug, starting from vertex <math>A</math>, 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 <math>p = \frac n{729}</math> be the [[probability]] that the bug is at vertex <math>A</math> when it has crawled exactly 7 meters. Find the value of <math>n</math>. | ||
== Solution == | == Solution == | ||
| + | Let <math>P(n)</math> denote the probability that the bug is at <math>A</math> after it has crawled <math>n</math> meters. Since the bug can only be at vertex <math>A</math> if it just left a vertex which is not <math>A</math>, we have <math>P(n + 1) = \frac13 (1 - P(n))</math>. We also know <math>P(0) = 1</math>, so we can quickly compute <math>P(1)=0</math>, <math>P(2) = \frac 13</math>, <math>P(3) = \frac29</math>, <math>P(4) = \frac7{27}</math>, <math>P(5) = \frac{20}{81}</math>, <math>P(6) = \frac{61}{243}</math> and <math>P(7) = \frac{182}{729}</math>, so the answer is <math>182</math>. One can solve this [[recursion]] fairly easily to determine a closed-form expression for <math>P(n)</math>. | ||
| + | |||
| + | There also exists a simple heuristic method to arrive at the answer to this question, due to [[User:ComplexZeta | 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 distribution | uniform]]. In particular, we would expect <math>P(n)</math> to be very close to <math>\frac 14</math> for decently-sized <math>n</math>, for example <math>n = 7</math>. (In fact, from looking at the previous solution we can see that it is already close when <math>n = 3</math>, 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 <math>\frac n{729}</math>, we realize that <math>n</math> must be very close to <math>\frac{729}{4} = 182.25</math>, as indeed it is. | ||
== See also == | == See also == | ||
| + | * [[1985 AIME Problems/Problem 11 | Previous problem]] | ||
| + | * [[1985 AIME Problems/Problem 13 | Next problem]] | ||
* [[1985 AIME Problems]] | * [[1985 AIME Problems]] | ||
| + | |||
| + | [[Category:Intermediate Combinatorics Problems]] | ||
Revision as of 20:02, 1 December 2006
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 
.
Solution
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 .
There also 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.
