Ladders on a rung, $1/2$ chance to go up and $1/2$ chance to go down, with a twist

Question

I am doing this problem here from the HMMT competition: https://hmmt-archive.s3.amazonaws.com/tournaments/1999/feb/oral/solutions.pdf

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)?

Here's the solution. I understand everything that follows and had independently come up with the same:

First consider the probability of winning if you never open the envelope. Let $q(n)$ be the probability of winning from the nth rung with just the fair coin, then $q(n) = (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) \ge 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.

However, I don't understand how any of the assertions in the next sentence follow from what's already been quoted.

We know $p(2) \ge 7/12$, therefore $p(3)\ge p(4)/2 + 7/24$, and we know $p(4) \ge p(5)/2 + p(3)/2 \ge (1/2+p(4)/2)/2 + p(3)/2 \ge (1/2+p(4)/2)/2 + (p(4)/2+7/24)/2$.

I don't even understand how it follows that $p(2) \ge 7/12$, much less anything that follows. Can anyone help?

Answer 1

First, $p(2)\geq 7/12$ follows immediately from the earlier statement

On rung $2$, we can open the envelope for a probability $1/2 + q(1)/2 = 7/12$ of winning...

Then $p(3)\geq p(4)/2+7/24$ follows from

Looking at rung $3$, ...we can not open the envelope for a probability $p(4)/2 + p(2)/2$ of winning.

since $p(3)\geq p(4)+p(2)/2$ and $p(2)\geq 7/12$.

Then $p(4)\geq p(5)/2+p(3)/2$ follows from

Next we look at rung $4$... If we don’t, then our chance of winning is $p(5)/2 + p(3)/2$.

and the rest is just substituting in known values.