Elevator stops in building

Solution 1:

Well, let me first extract from your question an important idea for solving this - you have identified, essentially, a set of reasonable strategies (which I've parameterized in some unknown integer $0 \leq n \leq 37$):

If Bill is at or below floor $n$, he should press the red button. If he is above floor $n$ and below floor $38$, he should press the green button. If he is above floor $38$, he should press the red button.

The question we're faced with is finding the best $n$ - for instance, one extreme case would be $n=0$, where he always presses the green button* when it'll eventually lead to the desired floor. On the other extreme, if $n=37$, Bill just presses the red button until he gets to his location. One might wish to justify why the strategy must be of this form - but it's not too hard to see that, since the green button is entirely non-random, it'd be silly to start pressing it and then to later decide, having learned nothing new, to press the red button.

Now, we can do our analysis. Let's imagine $n$ is fixed and evaluate the strategy. What we need to do is to define a series of variables $T_k$ which tells us how many more buttons we expect to press if we find ourselves on the $k^{th}$ floor.

Clearly, $T_{38}=0$. If $k$ is a floor on which we'd choose the green button, we have simply: $$T_k = 1 + T_{k+1}$$ since we need to press the green button, then do whatever we need to do to finish from the $(k+1)^{th}$ floor. So, we'd get $T_{37}=1$ and $T_{36}=2$ provided that $n$ is no more than $35$ - or, more generally $$T_k = (38 - k)$$ if $n < k \leq 38$.

If $k$ is a floor on which we'd choose the red button - so, any floor where $k\leq n$ or $38<k$ - then $$T_k = 1 + \frac{1}{100}\left(T_1+T_2+T_3+\ldots+T_{100}\right)$$ since we use one button press for sure and then end up, with probability $\frac{1}{100}$ each, at some other floor - and then should expect however many button presses it requires to get from that floor on. Then, the probabilistic part of the question is over - the rest is algebra. Note that our goal can be stated to minimize $T_{39}$ (or any floor above $38$), since doing so just takes one more button press than it takes to get to $38$ from a random floor.

Our equations can be simplified by realizing that, if we're going to press the red button, it doesn't really matter which floor we're on right now - that is, all of these values of $T_k$ are equal - let's call them all $$R=T_1=T_2=\ldots = T_{n-1} = T_n = T_{39} = T_{40} = \ldots = T_{100}.$$ There are $62 + n$ floors on which this random strategy holds, and we can thus simplify that $$R = 1 + \frac{62+n}{100}\cdot R + \frac{1}{100}\left(T_{n+1}+T_{n+2}+\ldots + T_{38}\right)$$ where we just pull out every term equal to $R$ from the original sum.

Then a bit of algebra gives $$R = \frac{100}{38 - n}\cdot \left(1 + \frac{1}{100}\left(T_{n+1}+T_{n+2}+\ldots + T_{38}\right)\right)$$ We can also recognize that the inner sum is known as just the sum of the first $38-n$ natural numbers, which is $\frac{(38-n)(37-n)}2$. Substituting this in and cancelling what needs to be cancelled gives: $$R = \frac{100}{38-n} + \frac{37-n}2$$ Note that we could get this result faster by realizing that we'll spend some amount of time moving randomly then have to go one step at a time. Formally, you could phrase this in random variables by writing that the time taken is $T$ which is $T_R + T_G$ where $T_R$ is the number of presses of the red button and $T_G$ is the number of presses of the green button. $T_R$ follows a geometric distribution with $p=\frac{38-n}{100}$. $T_G$ follows a uniform distribution on $\{0,1,2,\ldots,37-n\}$. The means of these distributions are $\frac{100}{38-n}$ and $\frac{37-n}2$ respectively. However, if you're uncertain of how to approach these questions, it's often better to work from first principles and not involve fancy constructions using random variables and linearity of expectation, as this fast path does.

However we arrive here, we finish by minimizing that expression for $R$ over $n$. We don't need to be clever here - there's not so many values and if you try all of them, you find the best value is $n=24$ and that $R=13+\frac{9}{14}$, meaning that if you press the green button on floors $25$ to $38$, you will, on average, require $13+\frac{9}{14}$ presses to get from any floor on which we'd press the red button to floor $38$. In terms of the original question, since the first random movement is free (and forced), this means Bill will need $12+\frac{9}{14}$ button presses on average.

(*I'm assuming the floors are $1,2,3,\ldots,100$ not $0,1,2,\ldots,99$ - you'll need to check your nearest skyscrapper to see if your country uses zero based indexing of floors)

Solution 2:

Since @MiloBrandt gave us a perfect and complete answer, I'm gonna give a partial answer for a simpler problem that I hope someone will find interesting.

Since we are considering an elevator (and not a circular bus) I'm gonna consider the same problem under the hypothesys that we always start from the floor $0$ (the lowest floor of the palace) and instead of evaluating the lowest number of pushes I'm gonna put the focus on three different strategies and evaluate which is "the best" to gain some time but with the result to reach always the 38th floor.

As I said, we can distinguish 3 different strategies, of 3 different players. The first one is an "old man" strategy: "keep pushing the green botton", you are gonna take 38 pushes but you are sure to arrive at destination.

The "kid" strategy: "keep pushing the red botton and hope". Eventually they are going to reach the 38th floor but with a probability of 1/100 of getting the exact floor at every push. Since this is a better strategy than the old man's one only if the number of pushes is lower that 38, we can conclude that "on average" only 37 times out of 100 they will use less pushes than the old man, so this is not the best strategy "on average".

Then we can identify a "middle" strategy: push the red button. If you get to a floor that is between the first floor and the 38th then push the green botton until you get to the 38th floor.

Even in this case, to beat the old man's strategy, we have to use less than 38 pushes. At the firts push we can get a floor $n$ such that $2\le n \le38$. If this did not happened, then we have lost one chance. Than we need to get a floor such that $3\le n \le 38$ and so on..

On every step we need to reach at least a floor higher than the prewious. If I did not made any error the probability this does not happens is: $63/100 \cdot 64/100 \cdot 65/100 \dots = 0.00029\dots$

In conclusion: the middle strategy is better than the old man strategy quite everytime and kids should grow up to understand that there exists a better strategy than theirs!