A problem by Sam Thompson
A bug is currently standing on vertex
of octahedron
,
where
and
are the apexes of square pyramids
and
,
respectively. A move is counted when the bug travels to an adjacent
vertex of the octahedron. Assuming that this is the only way the bug
can travel the octahedron, and the bug is not biased towards any point, if
is the probability that the bug will be standing on vertex
after 9 moves, where
and
are coprime positive integers, then what is
?
Image Credit: Wikipedia
This problem was adapted from SMaC Contest 1 #6.
The answer is 597.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
The bug is initially at the apex A.
The next movement from either of the apexes - A or F - has to be on any of the vertices of the coplanar points B, C, D, or E. So, the probability of moving from an apex to the plane BCDE in the next move, p(AP) = 1. The probability of moving from one apex to another apex in the next move, p(AA) = 0. Similarly, the probability of moving from a point on the plane BCDE to another point in the same place in the next move, p(PP) = 2/4 = 1/2. The probability of moving from any point on the plane BCDE to either of the apex points in the next move, p(PA) = 2/4 = 1/2.
Let p(n) P be the probability that the bug is on any of the coplanar points B, C, D, E after the n-th move. And, p(n) A is the probability that the bug is on either of the apex points - A or F - after the n-th move.
We may use the following recursive pattern to determine p(n) P and p(n) A with the initial condition being p(0) P = 0 and p(0) A = 1. Please, note that the bug has to be on any of the coplanar points B, C, D, or E after the 8-th move to have a non-zero chance of reaching the apex F after the 9-th move.
p(n) P = {(1/2) * p(n-1) P} + {1 * p(n-1) A} p(n) A = {(1/2) * p(n-1) P} + {0 * p(n-1) A} = (1/2) * p(n-1)_P
Using that, we get p(0) P = 0; p(0) A = 1 (Initial condition)
p(1) P = 1/2; p(1) A = 1/2 p(2) P = 3/4; p(2) A = 1/4 p(3) P = 5/8; p(3) A = 3/8 p(4) P = 11/16; p(4) A = 5/16 :::::::::::::::::::::::::::::::::::::::::::::::::::::::: p(8) P = 85/128; p(8) A = 43/128
The probability that the bug would stand on the apex F after the 9-th move = (1/4) * (85/128) = 85/512 = m/n. m + n = 85 + 512 = 597
(Please, excuse me as the formatting guide is not working properly on my machine.)