A blog called FiveThirtyEight started a weekly series of logic problems. I’ve been trying to get back into these (since taking a break from the IBM ones) I quickly collected teammate and coworker Rob McDonald to help and we got to work:
“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?”
Rob and I started and independently came up with solutions that had us drop the first phone in large (linear) increments. This meant you would drop the first phone at floor ten then, if it didn’t break, twenty, then thirty until it broke. Using the second phone you would then drop it at floors of one started at the highest floor at which the first phone survived.
For example, if the “breakzone” is floor 23 you would drop the first phone at floor 10. It would survive. You would then drop it at floor 20 where it would survive. Then floor 30 where it would break. You would take your second phone and drop it at floor 21 (survive), 22 (survive), then 23 (break) and know it breaks on floor 23. This took a total of 6 drops.
The worst case scenario for this method is the breakzone being on floor 89. In this case you would take 9 drops to break the first phone and then another 9 to break the second for a total of 18 drops.
This method is sound but has an unnecessarily high maximum number of drops at the expense of a lower minimum number. The linear step size means the first phone’s worst case scenario is a breakzone near floor 100 and the second phone’s worst case scenario is the breakzone has a 9 in the one’s column. The linear nature means these scenarios are independent… which can be remedied in what we believe is the solution, below.
Let’s start by dropping the first phone at a floor, i. If it breaks we know the breakzone is somewhere between 1 and i and it will take i-1 drops to find that specific floor, resulting in a worst-case of i drops. If it survives we will drop it from an increment i-1 higher. This reduces our search space with the second phone by one to account for the fact that we already dropped the first phone once. This method of decrementing the step size with the first phone still needs a step size, however. We found that by searching for the smallest number whose sum of integers smaller than and including it add up to the number of floors.
Where s = number of stories, i = maximum number of drops, which you minimize the value of.
Using this equation we found i to be 14 with a 100 story building and 45 when there are 1000 stories.
To go over the two examples used before:
Breakzone 23: You would drop the first phone on floor 14 (survive). You would drop the first phone on floor 27 (breaks). You then drop phone 2 on floor 15, 16, 17, 18, 19, 20, 21, 22, 23 (breaks) for a total of 11 drops.
Breakzone 89: You drop the first phone on floor 14,27,39,50,60,69,77,84,90 (breaks). You then drop the second phone on floors 85,86,87,88,89(breaks) for a total of 14 drops.
Rob and I were pretty pleased with our methodology and answers which was found using pen+paper and Microsoft Excel.