Monday puzzle: elevator buttons malfunctioning (spoilers)

An elevator in my office building of 65 floors is malfunctioning.

Whenever someone wants to go up, the elevator moves up by 8 floors if it can. If the elevator cannot move up by 8 floors, it stays in the same spot (if you are on floor 63 and press up, the elevator stays on floor 63).

And whenever someone wants to go down, the elevator moves down by 11 floors if it can. If it cannot, then the elevator stays in the same spot. (if you press down from floor 9, the elevator stays on floor 9).

The elevator starts on floor 1. Is it possible to reach every floor in the building?

How many times would you have to stop to reach the 60th floor, if you started on floor 1?

The solution is below.

(This puzzle is adapted from here)

Answer

It is possible to reach every floor in the building.

I used a spreadsheet to illustrate exactly how this is possible.

On the table below, every floor can be reached by a combination of moving up by 8 floors and moving down by 11 floors. (For simplicity, we can imagine the elevator has an “UP” button and a “DOWN” button).

The horizontal rows show an elevator moving up by 8 floors at a time, and the vertical columns are when the elevator moves down by 11 floors at a time.

(click on table for larger image)

You can see that every floor is attainable.

The harder part is to see why this actually works.

The reason has to do with number theory. We are essentially looking for integers solutions to the following equation:

8 x – 11 y = floor number

These types of equations are known as linear Diophantine equations. For a general equation, ax + by = c, solutions exist if and only if c is a multiple of the greatest common divisor of a and b.

In our case, 8 and 11 are relatively prime and have a greatest common divisor of 1, thus there are infinitely many solutions to the equation. The tricky part is verifying that every floor can be reached without going above floor 65 or going below floor 1, which is what the table above demonstrates.

How many times would you have to stop to reach the 60th floor, if you started on floor 1?

I got the idea for this question when I noticed floor 60 is the farthest away from floor 1 in the table.

I believe (but have not proved) the quickest route to get to floor 60 is to take 24 stops along the way: go across the first row, then move down in a step ladder fashion until you reach the bottom row of the table, and then move across the last row.

The floor sequence is: 1, 9, 17, 25, 33, 41, 49, 57, 65, 54, 43, 32, 21, 10, 18, 7, 15, 4, 12, 20, 28, 36, 44, 52, and finally 60.

That’s a long way to ride to get to your floor–that floor better hope someone fixes the elevator quickly!



Share this post:

| More

Previous post:

Next post:



  • tzs

    You are correct about 24 being the minimal number of stops to reach 60. This can be thought of as a graph traversal problem, where each floor is a vertex and there are edges between each floor and the floor 8 above and 11 below, and the problem is to find the shortest path from 1 to a given a floor. Here are the shortest paths to each floor:

    1: 1
    2: 1,9,17,6,14,3,11,19,8,16,5,13,2
    3: 1,9,17,6,14,3
    4: 1,9,17,6,14,3,11,19,8,16,5,13,2,10,18,7,15,4
    5: 1,9,17,6,14,3,11,19,8,16,5
    6: 1,9,17,6
    7: 1,9,17,6,14,3,11,19,8,16,5,13,2,10,18,7
    8: 1,9,17,6,14,3,11,19,8
    9: 1,9
    10: 1,9,17,6,14,3,11,19,8,16,5,13,2,10
    11: 1,9,17,6,14,3,11
    12: 1,9,17,6,14,3,11,19,8,16,5,13,2,10,18,7,15,4,12
    13: 1,9,17,6,14,3,11,19,8,16,5,13
    14: 1,9,17,6,14
    15: 1,9,17,6,14,3,11,19,8,16,5,13,2,10,18,7,15
    16: 1,9,17,6,14,3,11,19,8,16
    17: 1,9,17
    18: 1,9,17,6,14,3,11,19,8,16,5,13,2,10,18
    19: 1,9,17,6,14,3,11,19
    20: 1,9,17,6,14,3,11,19,8,16,5,13,2,10,18,7,15,4,12,20
    21: 1,9,17,6,14,3,11,19,8,16,5,13,21
    22: 1,9,17,6,14,22
    23: 1,9,17,6,14,3,11,19,8,16,5,13,2,10,18,7,15,23
    24: 1,9,17,6,14,3,11,19,8,16,24
    25: 1,9,17,25
    26: 1,9,17,6,14,3,11,19,8,16,5,13,2,10,18,26
    27: 1,9,17,6,14,3,11,19,27
    28: 1,9,17,6,14,3,11,19,8,16,5,13,2,10,18,7,15,4,12,20,28
    29: 1,9,17,6,14,3,11,19,8,16,5,13,21,29
    30: 1,9,17,6,14,22,30
    31: 1,9,17,6,14,3,11,19,8,16,5,13,2,10,18,7,15,23,31
    32: 1,9,17,6,14,3,11,19,8,16,24,32
    33: 1,9,17,25,33
    34: 1,9,17,6,14,3,11,19,8,16,5,13,2,10,18,26,34
    35: 1,9,17,6,14,3,11,19,27,35
    36: 1,9,17,6,14,3,11,19,8,16,5,13,2,10,18,7,15,4,12,20,28,36
    37: 1,9,17,6,14,3,11,19,8,16,5,13,21,29,37
    38: 1,9,17,6,14,22,30,38
    39: 1,9,17,6,14,3,11,19,8,16,5,13,2,10,18,7,15,23,31,39
    40: 1,9,17,6,14,3,11,19,8,16,24,32,40
    41: 1,9,17,25,33,41
    42: 1,9,17,6,14,3,11,19,8,16,5,13,2,10,18,26,34,42
    43: 1,9,17,6,14,3,11,19,27,35,43
    44: 1,9,17,6,14,3,11,19,8,16,5,13,2,10,18,7,15,4,12,20,28,36,44
    45: 1,9,17,6,14,3,11,19,8,16,5,13,21,29,37,45
    46: 1,9,17,6,14,22,30,38,46
    47: 1,9,17,6,14,3,11,19,8,16,5,13,2,10,18,7,15,23,31,39,47
    48: 1,9,17,6,14,3,11,19,8,16,24,32,40,48
    49: 1,9,17,25,33,41,49
    50: 1,9,17,6,14,3,11,19,8,16,5,13,2,10,18,26,34,42,50
    51: 1,9,17,6,14,3,11,19,27,35,43,51
    52: 1,9,17,6,14,3,11,19,8,16,5,13,2,10,18,7,15,4,12,20,28,36,44,52
    53: 1,9,17,6,14,3,11,19,8,16,5,13,21,29,37,45,53
    54: 1,9,17,6,14,22,30,38,46,54
    55: 1,9,17,6,14,3,11,19,8,16,5,13,2,10,18,7,15,23,31,39,47,55
    56: 1,9,17,6,14,3,11,19,8,16,24,32,40,48,56
    57: 1,9,17,25,33,41,49,57
    58: 1,9,17,6,14,3,11,19,8,16,5,13,2,10,18,26,34,42,50,58
    59: 1,9,17,6,14,3,11,19,27,35,43,51,59
    60: 1,9,17,6,14,3,11,19,8,16,5,13,2,10,18,7,15,4,12,20,28,36,44,52,60
    61: 1,9,17,6,14,3,11,19,8,16,5,13,21,29,37,45,53,61
    62: 1,9,17,6,14,22,30,38,46,54,62
    63: 1,9,17,6,14,3,11,19,8,16,5,13,2,10,18,7,15,23,31,39,47,55,63
    64: 1,9,17,6,14,3,11,19,8,16,24,32,40,48,56,64
    65: 1,9,17,25,33,41,49,57,65

  • Trish

    One easy way to determine the minimum number of steps to get to floor C is to think of it in terms of an integer program:

    min x + y
    subject to:
    8x – 11y = C-1
    x >= 0, y >= 0
    x,y integer

    This is a 2 variable problem, so you can actually solve it graphically! Sketch the convex hull of the feasible region (ie, 8x – 11y = C-1 in the first quadrant only) and pick the integer point on the line segment which minimizes x+y (in this case it’s equivalent and easier to find the integer point which minimizes x). Then to retrieve the actual ‘route’ you just need to intersperse the x ups and y downs in an order that keeps your current floor between 1 and 65. Once you know x and y, there are lots of easy ways to systematically determine the route, as I imagine tzx did.

  • William

    I thought of it like this:

    Using a specific sequence, you can move up 1 floor. Basically add 8 until you can subtract 11 and keep doing that until you’re 1 floor higher than you started. From the first floor it looks like this:
    1, 9, 17, 6, 14, 3, 11, 19, 8, 16, 5, 13, 2

    Thus, using the same sequence (or possibly smaller) multiple times, you can move to any floor 1 through 8. From there, you can jump up however many multiples of 8 you need to get to the right floor.

    So, to get to floor 60, you take 5 stops to get to 3, then a full sequence (12 stops) to go up to 4. From there you ride up 7 times to get to 60. Total: 24 stops

  • Neeraj

    Well I’m sure there are 24 stops required for the elevator to reach floor 60, but the quickest way to “get to floor 60″ is not 24, but 11 stops. Get off at floor 59 and walk up a floor, much faster than waiting for the elevator to make 13 more stops!

Previous post:

Next post:

This site is for recreational and educational purposes only (privacy policy)

Powered by WordPress