Problema Solution
You have been given 2 special, extremely rugged MacBook Pros. You are in an office building that is 100 stories high. Using the fewest possible number of drops from windows in your office building, determine the highest floor you can drop a MacBook Pro from and have it survive: for example, they might be able to take the drop from the 30th floor, but not the 31st. You can break both MacBook Pros in your search. State the worst-case number of drops needed and explain how you arrived at that answer.
Answer provided by our tutors
Stage 1: Drop the MacBook every x floors.
Let x be the number of floors skipped in stage 1.
S1 = (100 - x)/x = 100/x - 1 steps at most.
The MacBook breaks on the k-th floor.
Stage 2: Go back to (k - x + 1)th floor and drop from every floor until it breaks.
Stage 2 will have S2 = x - 1 steps at most.
Adding the two we have 100/x - 1 + x - 1 = 100/x + x - 2.
The function y = 100/x + x - 2 has minimum for x = 10.
Thus the steps are minimized when you skip 10 steps at a time.
We drop one MacBook from every 10th floor until it breaks then go back to one floor lower then the previous step (so if it breaks at 50 you go back to floor 41 because it didn't break at 40) and iteratively drop the second MacBook until it breaks. Then you know that the highest floor is the floor just beneath the one the second MacBook broke on.
The worst case would be if it breaks on the 90th floor = 9 drops.
And then we try 81, 82, 83, 84, 85, 86, 87, 88 and 89 = another 9 drops.
Or a total of 9 + 9 = 18 drops (the worst case).