Smartphone Droppings

On December 11, 2015, FiveThirtyEight began The Riddler!  This is going to be fun.

This week's riddle is quoted below:

You work for a tech firm developing the newest smartphone that supposedly can survive falls from great heights. Your firm wants to advertise the maximum height from which the phone can be dropped without breaking.

You are given two of the smartphones and access to a 100-story tower from which you can drop either phone from whatever story you want. If it doesn’t break when it falls, you can retrieve it and use it for future drops. But if it breaks, you don’t get a replacement phone.

Using the two phones, what is the minimum number of drops you need to ensure that you can determine exactly the highest story from which a dropped phone does not break? (Assume you know that it breaks when dropped from the very top.) What if, instead, the tower were 1,000 stories high?

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.

_________________________________________________________________________________

This third portion has been added after the first comment below which reveals the correct answer. However, I was lucky enough to think of this solution before reading his comment.  As I was drinking coffee on the morning after giving the solution above, I began thinking that now that I know that 16 drops is all that it takes, why not start at the 16th floor, or better yet, the 15th or 14th to try and get a smaller solution.  

By beginning on the 14th floor, you will have at most 14 drops if the phone breaks on the 14th.  With a second drop 13 floors higher on floor 27, you will again have at most 14 drops if the phone breaks on the 27th.  Continue this process and you will find that you need only 14 drops for even a 105 story building.  

Since summing 1 through 44 gives 990 and summing 1 through 45 gives 1035, it appears that you need 45 drops for a 1000 story building.  

Now, for the generalization.  What if you were given x smartphones, where x ranges from 1 to the number of floors?