Lazy Liz's Escape

Let the expected number of days it will take, at any point in time, for Lazy Liz to climb out from a depth of $10n$ meters be $d(n)$ . We seek to find $d(1)$ . We note first that after the flip occurs, one day will elapse. There is then a one half probability that the coin is heads and a one half probability that it is tails. If it is heads, then 0 more days elapse: Lazy Liz has made it out of the hole. If, on the other hand, the coin shows tails, Lazy Liz needs an expected number of $d(2)$ more days, as she has fallen 10 meters deeper. Hence, we have $d(1) = 1 + \frac{0+d(2)}{2}$ . By similar reasoning, $d(2) = 1 + \frac{d(1)+d(3)}{2}$ , since it takes 1 day after the coin is flipped and the chance she goes up to 10 meters or down to 30 meters is one half. For all integers $n$ where $2\le n \le 20$ , we have that $d(n) = 1+\frac{d(n-1)+d(n+1)}{2}$ . If she is at the bottom of the hole, then $d(21) = 1+\frac{d(20)+d(21)}{2}$ , since, upon flipping tails, she will still be at a depth of 210 meters. If we solve this final expression, we find $d(21) = 2 + d(20)$ . Substituting this into $d(20) = 1+\frac{d(19)+d(21)}{2}$ and solving gives $d(20) = 4+d(19)$ . It is not difficult to show then that for all integers $n$ where $2\le n \le 21$ , we have $d(n) = 2(22-n)+d(n-1)$ . Hence, $d(2) = 40+d(1)$ . Substituting this into the original $d(1) = 1+\frac{d(2)}{2}$ yields $\boxed{d(21) = 42}$ . $\blacksquare$

One might easily be lead astray with the given task statement into defining a random variable $X$ representing the time needed to climb out, and trying to calculate the mean of this variable using the formula $E(X) = \displaystyle \sum_{i=1}^{\infty} {i*P(i)}$ . However, this becomes problematic to evaluate properly after the bottom of the well gets hit, so there has to be a more clever approach.

Let's define $D(h)$ as the expected amount of days to climb out when starting at height $h*10$ from the top. Clearly, $D(0) = 0$ , since we are free once we reach the top. We can now spot a recurrence relation tying $D(h)$ to $D(h-1)$ and $D(h+1)$ . Namely, the expected amount of days starting from the position $h$ is the arithmetic mean (because there's equal probability of shifting in each direction) of the expected amounts of the two adjacent positions to it, plus one (because we needed one extra move to get from $h$ to $h\pm1$ . We can write this as:

$D(h) = \frac{D(h-1) + D(h+1)}{2} + 1 \ (1 \le h \le 20)$

For $h=21$ , moving down is equivalent to staying in the same state, so we can write $D(21) = \frac{D(20) + D(21)}{2} + 1$ . This can be simplified to get $D(21) = D(20) + 2$ . Substituting this into the recurrence relation for $D(20)$ we get $D(20) = D(19) + 4$ , and so on, until we get the formula $D(1) = D(0) + 42$ . Since we know that $D(0) = 0$ , we can conclude, finally, that $\boxed{D(1) = 42}$ .

Let $n$ th step denote the point at a distance of $10n$ from the bottom of the well. Let us denote the expected time to come out of the well when standing at the $n$ th step by $E_n$ . Then we seek to determine $E_{20}$ . From the symmetry of the problem it is easy to write down the following intermediate equations
$E_{n}= 1 + \frac{1}{2} E_{n-1} + \frac{1}{2} E_{n+1}$ for all $n=1,2,\ldots,19$ and two boundary equations,
$E_0=1+\frac{1}{2} E_1 + \frac{1}{2} E_0$
$E_{20}=1+ \frac{1}{2} E_{19}$

The intermediate equations are obtained by considering that she is standing at $n$ th step and after 1 step she reaches either $n+1$ th or $n-1$ th step with equal probabilities. The other equations are also obtained similarly. These system of equations are pretty straight-forward to solve by repeated substitutions and we get the result $E_{20}=42$

Lets just factor out the multiple of 10 for the hell of it

Let E(n) be the expected number days to climb up the well with n metres to go. We want to find out E(1)

E(1) = 1 + 1/2 E(2) E(n) = 1 + 1/2 E(n-1) + 1/2 E(n+1) E(21) = 1 + 1/2 E(20) + 1/2 E(21)

Rearranging the last equation says that E(21) = E(20) + 2 Rearrange equation 2 to get E(n-1) = 2E(n) - E(n+1) - 2

E(20) = E(21) - 2 E(19) = 2E(20) - E(21) - 2 = 2E(20) - (E(20) + 2) - 2 = E(20) - 4 E(18) = 2E(19) - E(20) - 2 = 2E(19) - (E(19) + 4) - 2 = E(19) - 6 E(17) = 2E(18) - E(19) - 2 = 2E(18) - (E(18) + 6) - 2 = E(18) - 8 ... E(1) = 2E(2) - E(3) - 2 = 2E(2) - (E(2) + 38) - 2 = E(2) - 40

2E(1) = 2 + E(2) E(1) = E(2) - 40

Subtracting the two equations, we find that E(1) = 42

Let A(n) be the expected number days to climb up the well with n metres to go. We want to find out A(1)

A(1) = 1 + 1/2 A(2)

A(n) = 1 + 1/2 A(n-1) + 1/2 A(n+1)

A(21) = 1 + 1/2 A(20) + 1/2 A(21)

we have 21 equations with 21 unknowns and they are linearly independent.

Rearrange the last equation, we have A(21) = A(20) + 2

Rearrange equation 2, we have A(n-1) = 2A(n) - A(n+1) - 2

A(20) = A(21) - 2

A(19) = 2A(20) - A(21) - 2 = 2A(20) - (A(20) + 2) - 2 = A(20) - 4

A(18) = 2A(19) - A(20) - 2 = 2A(19) - (A(19) + 4) - 2 = A(19) - 6

A(17) = 2A(18) - A(19) - 2 = 2A(18) - (A(18) + 6) - 2 = A(18) - 8

UP TO

A(1) = 2A(2) - A(3) - 2 = 2A(2) - (A(2) + 38) - 2 = A(2) - 40

2A(1) = 2 + A(2)

A(1) = A(2) - 40

Subtracting the two equations, we find that A(1) = 42

Lets just factor out the multiple of 10 for the hell of it

Let E(n) be the expected number days to climb up the well with n metres to go. We want to find out E(1)

E(1) = 1 + 1/2 E(2) E(n) = 1 + 1/2 E(n-1) + 1/2 E(n+1) E(21) = 1 + 1/2 E(20) + 1/2 E(21)

At this stage we could put this all into a matrix and solve, we do have 21 equations and 21 unknowns and they are linearly independent.

The system is tridiagonal though and that suggests we may have a cooler way of solving it. Rearranging the last equation says that E(21) = E(20) + 2 Rearrange equation 2 to get E(n-1) = 2E(n) - E(n+1) - 2

E(20) = E(21) - 2 E(19) = 2E(20) - E(21) - 2 = 2E(20) - (E(20) + 2) - 2 = E(20) - 4 E(18) = 2E(19) - E(20) - 2 = 2E(19) - (E(19) + 4) - 2 = E(19) - 6 E(17) = 2E(18) - E(19) - 2 = 2E(18) - (E(18) + 6) - 2 = E(18) - 8 ... E(1) = 2E(2) - E(3) - 2 = 2E(2) - (E(2) + 38) - 2 = E(2) - 40

2E(1) = 2 + E(2) E(1) = E(2) - 40 Subtracting the two equations, we find that E(1) = 42

let f(n) = expected number of days to come out of well from (10n) metres deep we want to find f(1) and we know f(0) = 0 then we note that for n = 1~20, f(n) = (0.5)(f(n+1)+1) + (0.5)(f(n-1))+1) This is because there is 0.5 chance of going up 10 meters and 0.5 chance of going down 10 meters and for n = 21, we have f(n) = (0.5)(f(n)+1) + (0.5)(f(n-1))+1) This is because there is 0.5 chance of going up 10 meters and 0.5 chance of staying at the same spot (Liz is at the bottom of the well) Using the second equation, we get: f(21)=0.5f(21)+0.5f(20)+1 f(21)=f(20)+2 Using the first equation, we get: f(20)=0.5f(21)+0.5f(19)=1 f(20)=f(19)+4 And using the first equation 20 more times, we get: f(19)=f(18)+6 f(i)=f(i-1)+(44-2i) ...... f(1)=f(0)+42 Thus, f(1)=0+42=42 We are done.

Let $E_j$ be the expected number of days to escape from the well starting $10 \times j$ meters from the top. We have the following equations:

$\begin{array}{rcl} E_1 & = & 1 + \frac{E_2}{2}\\ E_2 & = & 1 + \frac{E_3}{2} + \frac{E_1}{2}\\ & \vdots &\\ E_{20} &=& 1 + \frac{E_{21}}{2} + \frac{E_{19}}{2}\\ E_{21} & =& 1 + \frac{E_{21}}{2} + \frac{E_{20}}{2}\\ \end{array}$

Notice that every $\frac{E_j}{2}$ appears twice on the right hand side, except $E_1$ which appears only once. So adding these equations together and bringing all $E_J$ terms to the left hand side gives $\frac{E_1}{2} = 21$ , so the expected number of days to escape is $E_1 = 42$ .

As the probability of a head or a tail over a set of throws must be 0.5, the common answers like she will reach the top in the first day etc. are ruled out. As Lady Liz is 10 meters from the top and the well is 210 meters deep, the only case where we get equal probability of heads and tails is that she slides down 200 meters by getting 20 tails and then getting another tail so that she still stays on the bottom and then tosses 21 heads to climb 210 meters and come out of the well. In this case, no.of heads = no. of tails = 21. So, probability of a head or a tail is equal and hence the total number of days to come out of the well = 21 + 21 = 42. So, Lady Liz will come out in 42 days.

if she gets heads every day she takes 21 days to climb the well.but it does not happen on an average it takes 42 days to climb up

as there is equal possibility of head and tail ,he can reach the top in even no. of trials but he can't reach top without wasting one of his trial as he will reach the top in odd no. of trials only.also he can't waste hie one trial without reaching the bottom.so total no. of days = 20+21+(1)=42 ,,,,here(1) is the wasted one tail which will come when he will be at the bottom of the well. so the required no. of days= 42