MacBook Pro Question

[shah_ankitb]

You have 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 candrop a MacBook Pro from and have it survive: for example, they might be able to take the drop from the 30th floor, butnot the 31st. You can break both MacBook Pros in your search. State the worst number of drops needed and explain how you arrived at that answer.

 

Friends can you help me out with this?

[Ingolme]

The simplest idea would be to start on the first floor and continue dropping from higher floors one by one until it breaks. Of course, the idea is to reduce the number of drops performed and the worst case scenario for this method is 100 drops so it's not good enough.

 

If we had unlimited macbooks I'd start from floor 50, if it breaks, try floor 25, if it doesn't try floor 75. and repeat the procedure dividing the building into smaller sections. If I calculated correctly, the worst case scenario would be 7 drops for this method. Since we don't have unlimited macbooks we'll have to devise another method.

 

I don't know if giving you my solution would help you learn anything. For the solution I've devised, the worst case scenario would require 51 drops but perhaps somebody more experienced than me knows a better way.

[shah_ankitb]

Thank you sir for your answer

[davej]

I don't know how you would choose a best answer. Foxy describes the binary search method, but do we even know if the 100th floor drop will guarantee destruction? In the binary search method the worst case is 50+ drops, because you cannot use the binary search for both laptops -- because you cannot fail at 50 and then risk failing again at 25. You could step up by some subset of 100. If you use steps of 20 the worst case is 5+19=24 drops. If you use steps of 10 the worst case is 10+9=19 drops. Perhaps there is an optimal subset with the smallest worst case count?

[Ingolme]

I don't know how you would choose a best answer. Foxy describes the binary search method, but do we even know if the 100th floor drop will guarantee destruction? In the binary search method the worst case is 50+ drops, because you cannot use the binary search for both laptops -- because you cannot fail at 50 and then risk failing again at 25. You could step up by some subset of 100. If you use steps of 20 the worst case is 5+19=24 drops. If you use steps of 10 the worst case is 10+9=19 drops. Perhaps there is an optimal subset with the smallest worst case count?

If the 100th floor doesn't destroy the macbook then we still have the information we wanted. The highest floor you can drop it from is 100 because there aren't any more floors.

 

My method isn't the binary search method. A binary search would require seven macbooks and the problem says we only have two. I didn't describe my actual solution because I believe this is a homework question and giving the answer wouldn't help him learn.