On December 11, 2015, FiveThirtyEight began The Riddler! This is going to be fun.
Think on it a little bit if you want to solve it yourself, but the rest of this post is devoted to explaining the evolution of a solution.
The wording of the problem is a little confusing, but I think I get the jist. There are two adjacent floors of this tower the lower of which, when the smartphone is dropped it will not break, the higher of which, the smartphone will break. Our job is to find these floors so that we can report the highest story from which a dropped phone does not break.
Obviously, we could get lucky and guess the correct floor right away, drop a phone that doesn’t break, walk up a flight and drop a phone that does. The minimum number of drops would then be 2. But that isn’t what the riddle is really asking.
What it is really asking is that if we were the most unlucky as unlucky can be, and we had an optimal way of dropping smartphones out of building, what is the maximum number of drops that will take place before we get the answer? That answer I believe is 18. Here’s my train of thought.
A 100 story building has a nice number of stories, since it is a perfect square (10 * 10 = 100).
Drop the first smartphone from the 10th story. If it breaks, you have a potential nine droppings to go from stories 1-9 (technically, we could skip story 1 since the assumption is that there exists a floor from which the phone doesn’t break) with your only remaining smartphone for 10 total droppings before finding your answer.
If it doesn’t break, make your 2nd drop from the 20th story. If it breaks, you have a potential nine more droppings to go with your only remaining smartphone for 11 total droppings before finding the answer.
This process continues. If you are unlucky, and the answer is the 88th or 89th floor, then you will need 18 droppings. This is because your 9th drop will be from the 90th story, on which the first smartphone breaks. Your 10th through 17th drop will be from stories 81-88, none of which will result in a break. On your 18th drop, if the second phone breaks, the answer is the 88th story. If it doesn’t break, the answer is the 89th story.
You may wonder what if the story is the 98th or 99th floor. It turns out, because of the assumption that a smartphone will break on the 100th floor, it will take more droppings if it is the 97th or 98th floor.
Remember that your first phone hasn’t broken yet after the 9th dropping from the 90th floor. So, we can enter another optimal subroutine of dropping from the 93rd, 96th, and 99th until a break, and then going though two more droppings with the last remaining smartphone until we find our answer. Thus, if it is the 97th or 98th floor, the first phone breaks on the 99th floor, which would be your 12th dropping, then you will need 2 more droppings for only 14.
There may be a more optimal solution, so please chime in if I’m wrong.
Using the same idea for 1000 stories, I get a potential 62 total droppings (if we are unlucky and it happens to be on floor 990 or 991).
And…. I was wrong. Instead of rewriting the entry above, let’s learn from my mistake and correct it. Using the idea of doing a subroutine if you get to 90 without having it break, if we instead enter a subroutine each time, we can end with fewer droppings.
To illustrate, here are the first 15 potential droppings: Story 10, 20, 29, 38, 46, 54, 61, 68, 74, 80, 85, 89, 93, 96, 98. Using this routine, you will only need 16 droppings if the solution is one of floors 92, or 94-99.
I built a program in R to accomplish the task for any number of floors.