Elevator Mathematics

My friend ChefMongoose sent a neat little puzzle that came in a dream. I wanted to share it.

So! It’s not often that my dreams give me math puzzles. Here’s one: You are on floor 20 of a hotel. The stairs are blocked.

There are four elevators in front of you with display panels saying ‘3’, ‘4’, ‘7’, and ’35’. They will take you up that many floors, then the number will double. Going down an elevator will take you down that many floors, then the number will halve.

(The dream didn’t tell me what will happen if you can’t halve the number. For good puzzle logic, let’s assume the elevator goes down that much, then breaks.)

There is no basement, the hotel has an infinite amount of floors. Your challenge: get to floor 101. Can it be done?

(And I have no idea if it can be done. But apparently I, Riker, and Worf were trying to do it.)

The puzzle caught my imagination. It so happens the dream set things up so that this is possible: I worked out one path, and ChefMongoose found another.

ChefMongoose was right, of course, that something has to be done about halving the floor steps. I’d thought to make it half of either one less than or one more than the count. That is, going down 7 would turn the elevator into one that goes down either 3 or 4 floors. (My solution turned out not to need either.)

It looks lucky that ChefMongoose, Riker, and Worf picked a set of elevator moves, and rules, and starting, and ending floors that had a solution. Is it, though? Suppose we wanted to get to, say, floor 35? … Well, that’s possible. (Up 7, up 14, down 4, down 2.) 34 obviously follows. (Down 1 more.) 36? (Up 7, up 3, up 6.) 38? (Up 35, down 7, down 3, down 4, down 2, down 1.) The universe of reachable floors is bigger than it might seem at first.

The elevator problem had nagged at me with the thought it was related to some famous mathematical problem. At least that it was a type of one. ChefMongoose worked out what I was thinking of, the Collatz Conjecture. But on further reflection that’s the wrong parallel. This elevator problem is more akin to the McNuggets Problem. (When McDonald’s first sold Chicken McNuggets they were in packs of six, nine, and twenty. So what is the largest number of McNuggets that could not be bought by some combination of packages?) The doubling and halving of floor range makes the problem different, though. I am curious if there are finitely many unreachable floors. I’m also curious whether allowing negative numbers — basement floors — would change what floors are accessible.

The Collatz Conjecture is a fun one. It’s almost a game. Start with a positive whole number. If it’s even, divide it in half. If it’s odd, multiply it by three and add one. Then repeat.

If we start with 1, that’s odd, so we triple it and add one, giving us 4. Even, so cut in half: 2. Even again, so cut in half: 1. That’s going to bring us back to 4.

If we start with 2, we know where this is going. Cut in half: 1. Triple and add one: 4. Cut in half: 2. And repeat.

Starting with 3 suggests something new might happen. Triple 3 and add one: 10. Halve that: 5. Triple and add one: 16. Halve: 8. Halve: 4. Halve: 2. Halve: 1.

4 we’re already a bit sick of at this point. 5 — well, we just worked 5 out. That’ll go 5, 16, 8, 4, 2, 1, etc. Start from 6: we halve it to 3 and then we just worked out 3.

7 jumps right up to 22, then 11, then 34 — what a interesting number there — and then 52, 26, 13, 40, 20, 10 and we’ve seen that routine already. 10, 5, 16, 8, 4, 2, 1.

The Collatz Conjecture is that whatever positive whole number you start from will lead, eventually, to the 4, 2, 1 cycle. It may take a while to get there. I was working the numbers in my head while falling asleep the other night and got to wondering what exactly was 27’s problem anyway. (It takes over a hundred steps to settle down, and gets to numbers as high as 9,232 before finishing.)

Nobody knows whether it’s true. It seems plausible that it might be false. We can imagine a number that doesn’t. At least I can imagine there’s some number, let me call it N, and suppose it’s odd. Then triple that and add one, so we get an even number; halve that maybe a couple times until we get an odd number, and triple that and add one and get back the original N. You might have fun trying out numbers and seeing if you can find a loop like that.

Just do that for fun, though. Mathematicians have tested out every number less than 1,152,921,504,606,846,976. (It’s a round number in binary.) They all end in that 4, 2, 1 cycle. So it seems hard to believe that 1,152,921,504,606,846,977 and onward wouldn’t. We just don’t know that’s so.

If you allow zero, then that’s a valid but very short cycle: 0 halves to 0 and never budges. If you allow negative numbers, then there are at least three more cycles. They start from -1, from -5, and from -17. It’s not known whether there are any more in the negative integers.

The conjecture’s named for Lothar Collatz, 1910 – 1990, a German mathematician who specialized in numerical analysis. That’s the study of how to do calculations that meaningfully reflect the mathematics we would like to know. The Collatz Conjecture is, to the best of my knowledge, a novelty act. I don’t know of any interesting or useful results that depend on it being true (or false). It’s just a question easy to ask and understand, and that we don’t know how to solve. But those are fun to have around too.