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.

43 McNuggets Made Difficult

I mentioned in the last comments thread the McNuggets Problem, and realized belatedly that maybe not everybody knew just what that was. It’s a cute little one, which Wolfram’s Mathworld is able to date to 1991, or maybe 1990. There’s a reference to a March 1990 puzzle on Usenet newsgroup rec.puzzles, but to find it would require some Google-like search engine capable of finding postings on Usenet, and that technology is sadly beyond us.

Whether 1990 or 1991 seems late, since I’m certain the puzzle first appeared about the same time people first saw the original Chicken McNuggets menu options on sale, sometime in the mid-80s. In the original offerings, one could buy a pack of six, nine, or if Mom was feeling particularly flush with cash or you gave a credible impersonation of being willing to share with your siblings, twenty. The obvious question, then, is what’s the largest number of McNuggets which can’t be bought by some combination of these?

This can be studied rigorously, although I don’t know anyone who actually would. It’s more fun to play and see what can be constructed: 12, obviously; 15, as surely; 18 as well (and that by two different patterns, three packs of six or two packs of nine). 21, 24 (again by two paths), 26, 27, 29, 30 … it looks very much like we’re running out of numbers to buy, and some experimentation finds that 43 is the biggest number of McNuggets which can’t be bought. At least, we can find the formulas for 44, 45, 46, 47, 48, and 49, and obviously, any number above that you can get by buying enough six-packs on top of whatever one of those is.