You are somewhere on a ladder with 5 rungs. You have a fair coin and an envelope that contains either a double-headed coin or a double-tailed coin, each with probability $1 / 2$. Every minute you flip a coin. If it lands heads you go up a rung, if it lands tails you go down a rung. If you move up from the top rung you win, if you move down from the bottom rung you lose. You can open the envelope at any time, but if you do then you must immediately flip that coin once, after which you can use it or the fair coin whenever you want. What is the best strategy (i.e. on what rung(s) should you open the envelope)?
Solution: First consider the probability of winning if you never open the envelope. Let $q(n)$ be the probability of winning from the $n$th rung with just the fair coin, then $q(n)=\frac{q(n-1)+q(n+1)}{2}$, so it is not hard to calculate that $q(n)=n / 6$. If we open the envelope, then there's a $1 / 2$ chance that it is heads and we win, and a $1 / 2$ chance that it is tails and we end up one rung down with just the fair coin (obviously we keep using the double sided coin iff it is double headed). Let us start by analyzing rung 1 . If we don't open the envelope, then we have a $1 / 2$ chance of losing and a $1 / 2$ chance of ending up on rung 2 with the envelope. If we do open the envelope, then we have a $1 / 2$ chance of losing and a $1 / 2$ chance of winning, which is a better outcome, so we should open the envelope on rung 1. Next we look at rung 5. If we don't open the envelope, then we have a $1 / 2$ chance of winning and a $1 / 2$ chance of moving down to rung 4 with the envelope. If we do open the envelope, then we we have a $1 / 2$ chance of winning and a $1 / 2$ chance of moving down to rung 4 without the envelope. Let $p(n)$ be the probability of winning from rung $n$ if we are there with the envelope still unopened. Then clearly $p(n) \geq q(n)$ for all $n$ if we're using optimal strategy, so we should not open the envelope on rung 5. Next we look at rung 4. If we open the envelope, then our chance of winning is $1 / 2+q(3) / 2=3 / 4$. If we don't, then our chance of winning is $p(5) / 2+p(3) / 2$. We do know that $p(5)=1 / 2+p(4) / 2$, but this is not enough to tell us what to do on rung 4 . Looking at rung 3 , we can open the envelope for a probability $1 / 2+q(2) / 2=2 / 3$ of winning, and we can not open the envelope for a probability $p(4) / 2+p(2) / 2$ of winning. On rung 2 , we can open the envelope for a probability $1 / 2+q(1) / 2=7 / 12$ of winning, and we can not open the envelope for a probability $p(3) / 2+p(1) / 2=p(3) / 2+1 / 4$ of winning.
Now we can use all this information together for the complete answer. We know $p(2) \geq 7 / 12$, therefore $p(3) \geq p(4) / 2+7 / 24$, and we know $p(4) \geq p(5) / 2+p(3) / 2 \geq \frac{1 / 2+p(4) / 2}{2}+p(3) / 2 \geq$ $\frac{1 / 2+p(4) / 2}{2}+\frac{p(4) / 2+7 / 24}{2}$. Isolating $p(4)$ in this inequality, we get $p(4) \geq 1 / 2+7 / 24>3 / 4$, therefore we should not open the envelope on rung 4 . Now from $p(4)=p(5) / 2+p(3) / 2$ and $p(5)=1 / 2+p(4) / 2$ we have $p(4)=\frac{1 / 2+p(4) / 2}{2}+p(3) / 2$, so $p(3)=3 p(4) / 2-1 / 2 \geq 11 / 16>2 / 3$, so we should not open the envelope on rung 3 . Now $p(2) \geq p(3) / 2+1 / 4 \geq 19 / 32>7 / 12$, so we should not open the envelope on rung 2. Therefore the best strategy is to open the envelope iff we are on the bottom rung.