There is a 100 story high building. We have 2 identical glasses. We would like to know the highest floor from which it is possible to drop a glass and not have it broken on the ground. What is the least number of experimental drops we need in order to determine the answer? (and how so?)I know it is less than 19.
7 drops should be needed to be sure. #1 drop from the 50th floor breaks, go to 25. Doesn't break, goto 75 # 2 breaks from 25, goto 12. Doesn't break from 25, goto 37 # 2 breaks from 75, goto 62. Doesn't break from 75, goto 87 # 3 breaks from 12, goto 6. Doesn't break from 12, goto 18 # 3 breaks from 37, goto 31. Doesn't break from 37, goto 43. # 3 breaks from 62, goto 68. Doesn't break from 62, goto 56. # 3 breaks from 87, goto 81. Doesn't break from 87, goto 93. As you can see, each drop allows you to cut the min-max distance by 1/2. Within 6 or 7 tries you should have a valid answer. Ok, with your new I info I have a new answer. :) Least number of drops = 2 (floors 10 and 1 (both break) Most number of tests = 18. (floor 99) Drop from floors 12 1+11 24 2+11 36 3+11 48 4+11 60 5+11 70 6+9 80 7+9 90 8+9 100 9+9
I believe you are basically doing a binary search. I hope that helps enough because as long as you know that algorithm, you can just calculate the max. Edit: sorry, forgot to note you are limited to 2, so I guess you would be in some trouble if you broke both, which could happen with a naive binary search. So, I guess in that way my intuition would say moving up somehow. Let's say 10 at a time. Drop glass from 10th floor - it breaks, now you only have to test floors 1-9 sequentially, that's 10 drops at most - it doesn't, drop from 20th floor - it breaks, test floors 11-19 sequentially, that's 11 drops at most - it doesn't break, drop from 30th, etc.
