1

Let the highest floor of a building be an integer L. There are 2 elevators A and B, where A starts at floor zero and B starts at floor L. If someone presses the elevator button on floor N, the closest lift to that floor N will move to that floor. Neither one of the elevators can move if the other one is moving. If A and B are both at the same distance to floor N, the lift on the lowest floor will move. If both elevators are on the same floor, lift A will move.

How can it be proven that A will never be on a floor higher than B and B will never be on a floor lower than A?

**

my train of thought right now is that this can be proven by showing that B will never be able to move by half or more of the distance between B and A. I don't really know how to prove that though. maybe I could include arithmetic?

I was working on a programming problem when I had this problem. At first, I miswrote something which resulted in some errors. I fixed it and tried experimenting with the code, then I realized that B will never be on a lower floor than A. I then made a sketch on paper to confirm it and thought about how a mathematical proof would be for something like this or what kinds of proofs can be used. Any kind of help or keywords to be searched on google will be appreciated! Thanks!! ///

SeeMore
  • 11

1 Answers1

1

We need to prove that an invariant – that $A$'s floor is always strictly below $B$'s floor – holds after any button press if it holds before the press. These are all the cases:

  • If the button is pressed at or below $A$'s floor, or between $A$'s and $B$'s but closer to $A$ than $B$, $A$ moves down, or up but strictly less than half the floor gap between $A$ and $B$, respectively. Thus $A$ is still strictly below $B$.
  • By symmetry, the invariant holds if the button is pressed at or above $B$'s floor, or between the floors but closer to $B$ than $A$.
  • If the button is pressed at a floor exactly between $A$ and $B$, since the lower lift is $A$, $A$ moves and $A$ is still strictly below $B$ afterwards. (There must be at least two floors' distance between $A$ and $B$ before the press, and at least one afterwards, for this to happen.)

Assuming the natural $L>0$, the invariant thus holds under all conditions since it holds at the start.

Parcly Taxel
  • 103,344