1

In a 20-floor house, an elevator has two buttons. Pressing "UP" gets the elevator to go up 13 floors, pressing "DOWN" makes the elevator go down eight floors. Is it possible to get from the 13th floor to the 8th floor? Support your answer with accurate proof.

This is a fun question. If you think that you can solve it, feel free to post an answer with proof.

Jmaxmanblue
  • 479
  • 2
    This question can be brute forced: if you are on the 9th floor or above, you must push the down button (as there are no floors higher than 20), and if you are on the 7th floor or below, you must push the up button (unless there is a basement that you haven't told us about?). This means that wherever you are, there is only one button that you can push. Starting on the 13th floor, we have $$13 \to 5 \to 18 \to 10 \to 2 \to 15 \to 7 \to 20 \to 12 \to 4 \to 17 \to 9 \to 1 \to 14 \to 6 \to 19 \to 11 \to 3 \to 16 \to 8, $$ which provides a way of getting from the 13th floor to the 8th. – Xander Henderson Dec 09 '17 at 23:41
  • 2
    @XanderHenderson Right. Also, the next two steps are $8 \to 0 \to 13$ which returns to the starting floor. Since the cycle covers all floors, it follows that it's possible to get from any floor to any other one. – dxiv Dec 09 '17 at 23:45
  • @dxiv Alternatively, you are simply stuck, since no basement implies no 0th floor. Time to take the stairs (but that's okay, I need the exercise). – Xander Henderson Dec 09 '17 at 23:46
  • 1
    @XanderHenderson True in North America, but the ground level floor can be thought of as $0$ elsewhere, see for example the notes at first floor. – dxiv Dec 09 '17 at 23:50
  • 1
    @dxiv If it is a 20 floor house with a 0th floor, is the top floor 19 or 20? If 19, then the answer to the question is "no", since we have to visit floor 20 at some point. Other wise, I concede defeat... as punishment, I'll take the stairs. :( – Xander Henderson Dec 09 '17 at 23:51

2 Answers2

3

Because I have now invested way more time that is prudent on this, let's summarize:

  1. If the building has floors numbered 1 through 20, then there is a way to get from the 13th floor to the 8th floor. The path is as follows: $$ 13 \to 5 \to 18 \to 10 \to 2 \to 15 \to 7 \to 20 \to 12 \to 4 \to 17 \to 9 \to 1 \to 14 \to 6 \to 19 \to 11 \to 3 \to 16 \to 8. $$ Unfortunately, as far as I can tell, there is nothing terribly clever about this solution. It simply uses that fact that if you are on the 8th floor or above, you cannot go up, and if you are on the 8th floor or below, you cannot go down. Hence if you are on any floor of the building (other than the 8th), then there is only on possible way to go. Go that way, and you eventually get to the 8th floor.
  2. More generally, this looks like the kind of problem posed to beginning abstract algebra students: you have a pitcher that holds $m$ liters of water, and another pitcher that holds $n$ liters of water. How do you get exactly $k$ liters of water? These are typically solved via modular arithmetic, generally as a prelude to the Euclidean Algorithm. If there is a "clever" answer, it comes from this.
  3. As noted in the comments, there are a couple of assumptions that I have made that may or may not be true. First, I've assumed that the floors are numbered 1 through 20. However, if a 20 story building has a 0th floor, then the building would have floors numbered 0 through 19, in which case it is not possible to get from the 13th floor to the 8th floor. On the other hand, if the building has floors numbered 0 through 20, then it is possible to get from any floor to any other floor. Yipee.
  4. The question is nonsense. Architects don't design buildings with a 13th floor. enter image description here
Xander Henderson
  • 29,772
0

It might take a while but if you follow these two rules you'll get there after 19 trips.
If you're on the 9th floor or above go down 8 floors. (never less than 1)
If you're on the 7th floor or below go up 13 floors. (You will never go above 20)
If you're on the 8th floor get off quick.

13, -8=5, +13=18, -8=10, -8=2, +13=15, -8=7, +13=20, -8=12, -8=4, +13=17, -8=9, -8=1, +13=14, -8=6, +13=19, -8=11, -8=3, +13=16, -8=8

This works because the greatest common denominator of 8 and 13 is 1, so you'll hit all the floors eventualy.

KevB
  • 196