There are $n$ planets. Luke is on planet $A$. For each planet, except planet $B$ and $C$, there are two unidirectional roads that join other planets. From at most one of these two roads, Luke can find a sequence of roads that bring him back to the planet he had just left. Luke's journey ends when he reaches planet $B$ or $C$. When he leaves a planet, he chooses one of the two roads with equal probability. If the probability that he arrives on planet $B$ is $\frac{1}{2016}$, what is the minimum value of $n$?

How would you attack this problem? I have no idea :(.

Any help would be greatly appreciated.


closed as off-topic by heropup, user223391, Leucippus, Jack, user91500 Dec 11 '16 at 6:06

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – heropup, Community, Leucippus, Jack, user91500
If this question can be reworded to fit the rules in the help center, please edit the question.


We can solve the problem with $n=13$, by starting with $$A\to X_1\to X_2\to X_3\to X_4\to X_5\to X_6\to X_7\to X_8\to X_9\to X_{10}\to B $$ and letting all other arrows point to $C$, except that the second arrow of $X_5$ points back to $A$. Then the probability that we ever take the edge $X_5\to X_6$ is $\frac1{2^6}+\frac1{2^{12}}+\frac1{2^{18}}+\ldots = \frac1{63}$. Once we are at $X_6$, the probability to reach $B$ is $2^{-5}$, hence in total we have a probability of $\frac1{63\cdot 32}=\frac1{2016}$ to reach $B$.

On the other hand, there is no solution with $n\le 12$, for in that case the shortest path from $A$ to $B$ (which must exist) would consist of at most $10$ edges (as it cannot pass through $C$), leading to a lower bound of $2^{-10}>\frac1{2016}$ for the probability.


Not the answer you're looking for? Browse other questions tagged or ask your own question.