2
$\begingroup$

This question already has an answer here:

You've just bought an anti-shock skin for your macbook air and want to make a review video for your vlog showing how good it is at absorbing shocks.

The skin has a special property that either completely absorbs the shock and leaves the computer inside intact if the shock is not too big. Otherwise, the laptop will break apart in a spectacular fashion and will never be usable again. You also know for a fact that the skin cannot absorb a 100 floor fall.

You happen to own 2 identical laptops and skins that will break apart at exactly the same height, and don't mind killing one or both of them. Also, very conveniently, you have access to all floors of a 100-stories skyscraper.

Your goal is to determine what is the highest floor at which the skin can still absorb the shock. As you are also very time conscious, you want to determine the strategy that has the smallest maximum number of attempts (worst case scenario).

Please provide detailed explanation why your strategy is the best one.

Bonus question: can you generalize the answer to an N-th floor building, still with 2 drops?

Notes: I know there are at least a couple of similar puzzles here and here but they are not identical in the sense that here we are asking to minimize the maximum number of attempts. I was asked this puzzle in a job interview (I only changed the story), where I failed to explain why my solution was the best one. I have an idea now but am curious to compare with your explanations.

$\endgroup$

marked as duplicate by Jamal Senjaya, JMP, Gamow, Peter Taylor, Deusovi Sep 7 '17 at 20:18

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ not a duplicate as explained in the Notes $\endgroup$ – sousben Sep 7 '17 at 9:40
  • $\begingroup$ The solutions to that puzzle are given for the general case as well, and I don't think the general case is different enough from the specific case to be considered not duplicates $\endgroup$ – Jamal Senjaya Sep 7 '17 at 9:51
  • $\begingroup$ Visit TSL for an extended discussion on the general case $\endgroup$ – Wen1now Sep 7 '17 at 10:28
  • 1
    $\begingroup$ Although "Will the glass ball break?" asks us to minimise the average number of drops over all possible results, which isn't prima facie the same as minimising the maximum number of drops, Dinosaur Egg Drop v2 does ask us to minimise the maximum number of drops. $\endgroup$ – Peter Taylor Sep 7 '17 at 18:25
2
$\begingroup$

Test at floors $14,27,39,50,60,69,77,84,90,95,99$. When it fails, then just test the floors going up to that e.g If it fails on floor 60, then test 51,52,53,...

This takes a total of 14 trials maximum.

Proof of minimality: your first drop must be less than 14 to beat 14 trials; if it is more then if the first drop fails then we lose. Similarly, the second drop must be <13 more than the first one, for the same reason. Continuing, we see that in 13 drops we only reach floor 91 by 13 drops, not enough. Hence we need at least 14 drops.

$\endgroup$
  • $\begingroup$ This answer is correct and therefore accepted, but I was after a more analytical explanation. I'll edit the question in order to drive answers in that direction $\endgroup$ – sousben Sep 7 '17 at 9:46
1
$\begingroup$

Each initial drop is the floor plus floors below
If it fails go back to the start
Start at 100 and just add one for every used drop

100 1
98  2
95  3
91  4
86  5
80  6
73  7
65  8
56  9
46  10
35  11
23  12
10  13
-4  14
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.