2

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.

sousben
  • 2,586
  • 1
  • 12
  • 29

2 Answers2

2

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.

Wen1now
  • 9,253
  • 4
  • 33
  • 86
  • 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 – sousben Sep 07 '17 at 09:46
1

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
paparazzo
  • 500
  • 5
  • 12