Elevator puzzle

[Soothsayer]

See if you can figure out this lift (elevator to you yanks) puzzle.

There are 5 elevators. The elevator doors only open when all the elevators are between the 21st and 25th floors.
There are two buttons [+8] and [-13], that will be activitated only when 2 elevators are selected. The building has 49 floors.

Starting positions:

code:

---

Floor 17   ---   Floor 26   ---   Floor 20   ---   Floor 19   ---   Floor 31

---

What is the correct sequence to get all 5 elevators to open.

For java version of puzzle go to Lift Puzzle

[Suspence]

This is a tough one. Given that the doors to these elevators will only open if all the elevators are between the 21st and 25th floors, I haven't yet figured out another way to get into the elevators to press these odd buttons, perhaps the elevator shaft...Aha, the Java version of this puzzles reveals that these are external buttons that control the elevators. You must select 2 of the elevators, and then you must choose to move both elevators either up 8 floors or down 13. Now it makes more sense...

------------------
I hate people who try to write interesting things in their signature

[MBA]

Hint please, how many steps should this take? Since there are obviously multiple solutions, how many steps are in the answer you have in mind?

[Suspence]

This is my solution:

Move elevator 1 and 2 up 8
Move 2 and 3 up 8
Move 2 and 5 down 13
Move 2 and 3 up 8
Move 4 and 5 up 8
Move 4 and 5 up 8
Move 2 and 3 down 13
Move 4 and 5 down 13


Elevator 1 started on 17 +8 = 25
Elevator 2 started on 26 +8 +8 +8 -13 -13 = 24
Elevator 3 started on 20 +8 +8 -13 = 23
Elevator 4 started on 19 +8 +8 -13 = 22
Elevator 5 started on 31 +8 +8 -13 -13 = 21

Leaving your elevators in order on floors 25, 24, 23, 22, and 21 respectively, in only 8 moves!!!
------------------
I hate people who try to write interesting things in their signature

[This message has been edited by Suspence13 (edited 03-14-2002 11:21 PM).]

[Soothsayer]

So far I have completed in (feels embarrassed) 30 moves but I believe it can be done in 16

[ctrlaltdel]

i dont understand the puzzle statement

can i get any two lifts to go either 8 floors up or 13 down?

[Soothsayer]

To clarify.

You must always select two lifts. Those lifts can either go up 8 or down 13 floors..

The doors only open when all the lifts are between 21st and 25th floors

[eixdeuce]

Suspence13's solution is a good one and completes the task in 8 moves. The optimal solution to problems like this can be found using linear programming though you don't need to in this case. In fact, one can easily show that 8 moves is the minimum number of moves required to satisfy the conditions of the problem simply by determining what needs to be done to each elevator and then using the fact that all moves need to be done in pairs.

For example,

In this case, we can move in increments of (+8), (-13), and (-5) = [(+8)+(-13)] or any other linear combination so,
Elevator 1 originally at 17 needs to be shifted at least once (+8) to reach 25.
Elevator 2 at 26 (-5) = 21.
Elevator 3 at 20 (+8)+(-5) = 23.
Elevator 4 at 19 (+8)+(-5) = 22.
Elevator 5 at 31 (-5)+(-5) = 21.

This gives a total of
3*(+8) + 5*(-5) = 3*(+8) + 5*[(+8)+(-13)] = 8*(+8) + 5*(-13)
8 moves up, and 5 moves down
Since each move is in pairs, we require that the coefficients of the moves up and moves down be even so we have to add an odd number (1,3,5,...) of down(-13) moves and any even number of (2,4,6...) up(+8) moves. So, we try the minimum of each, 1 down(-13) move and 2 up(+8) moves. Clearly, if we shift an elevator by just one up(+8) or down(-13)move, it will no longer be in the desired range, so we have to perform all three moves on a single elevator. This gives us a net shift of
2*(+8) + 1*(-13) = (+3)
The elevators which can be shifted (+3) and still remain in the range of 21-25 are
2 (on floor 21)
4 (on floor 22)
5 (on floor 21)
And you are free to choose any of them you like. Finally, the minimun number of moves is
(10 up + 6 down)/2 = 8

You divide by two because once again, the moves are paired.


Hope that was clear.



[This message has been edited by eixdeuce (edited 03-15-2002 09:49 AM).]

[Suspence]

That's exactly how I did it. I came up with an odd number of moves, and just monkeyed with it til i got it right. Also, I had to move 1 step because I sent elevator 2 through the roof in my original "solution". I had to move down 13 before moving up 8 the last time.

------------------
I hate people who try to write interesting things in their signature