Problem 8 · The strange lift
Worst-case strategy: counting unavoidable rides.
Integer answer, at most 4 digitsIn a 20-storey hotel the first 10 floors are green and floors 11 to 20 are red. The hotel has no stairs, and the only way to change floors is a strange lift behaving as follows: whoever enters the lift on a green floor goes exactly to the requested floor. Whoever enters on a red floor goes to a floor of the same colour as the one selected, but not necessarily the selected one; in any case, the lift changes floors. Whatever the floor, the lift always arrives empty when called. A person must visit all the floors, starting from the first and returning to the first. If the lift behaves in the worst possible way, what is the minimum number of rides needed to achieve this?
Reasoned solution
Key idea: from a green floor we fully control the destination; from a red floor we only control the destination's colour.
Unavoidable rides. Each red floor can only be guaranteed by entering it from a green floor (from a red one, the lift chooses). So we need $10$ green → red rides, and after each one we must leave: $10$ more red → green rides (requesting a green floor; we land on some green floor). That's $20$ already.
The green floors. In the worst case, every exit from a red floor drops us on floor $1$ (or on already-visited greens): no gifts. That leaves $9$ green floors to visit ($2$ to $10$), each reachable exactly with one ride from a green floor: $9$ more rides. The final return to floor $1$ costs nothing extra: order the tour so that the last red-floor exit (which in the worst case drops us on floor $1$, the adversary's one repeated “punishment”) is the end of the trip — and if the adversary drops us on another green floor instead, then that floor was a free gift earlier, saving a ride we now spend returning to $1$.