You have a building with 100 stories, and two identical balls. Your goal is to discover the topmost level from which the balls can be dropped without breaking. Do this in the least number of tries (drops). 4 Answers Drop from 10th floor. If that works, drop from 20th floor. Etc. Until you reach a floor where the ball breaks. Say it's 70th floor. Then you know the highest floor is between 61 and 69, so you have at most 9 more drops. Worst case is floor 99 or 100, which you can find in 19 drops. This strategy will find the highest floor in any building of N floors in at most ((2*sqrt(N)) - 1) tries. Try to breakup the numbers into groups of 3 (B1floor, B2floor, remaining). Let answer be: 55 Try 1 (breakup into 30,30,40remain): B1-Floor 30, B2-Floor 60, B2 breaks, B1 doesn't So, answer < 60 Try 2: B1-Floor 20, B2-Floor 40, B1, B2 both survive So, 40 < answer < 60. Try 3(breaking into three 7's) : B1 - Floor 47, B2-Floor 54, B1,B2 both survive So answer is bigger than 54 but less than 60. 54<answer < 60. Try 4 (breaking into 2's): B1 - Floor 56, B2-Floor 58 B1, B2 both break. So, answer is less than 56 and 58 but more than 54. So, answer is 55. Objective is to narrow down the range between a,b where (a<answer<b) at each try. Shall we test it on the 1st floor? In my scenario I assumed don't have to. Drop it from 11,21,31,...,91th floor. The worst case is you make it towards to the 91th floor. If it breaks on 91th floor, roll back to test floor 82th to 90th (81th floor you've already tested.) The total worst case test number is 9+9=18 (only breaks at 90th or higher floor). If it didn't break on 91th floor, test 96th floor. If it doesn't break, always select the middle floor among the remaining floors. The worst case test number is 9+1+3=14. The reason why if ball didn't break on 91th floor and then you can go jump several floors is that you have two balls, which you can afford 1 loss from the ball. So you don't have to go one by one like from 82th to 90th. Show More Responses Delete floor 1 since you don't drop it at floor 1. Floors to drop is at floor 2~100 Section them in 3 parts A,B,C a=[2~34] , b=[35~67] , c=[68~100] 33 floors each. SET 1 - Drop it at floor 34, then 67. if breaks at 34, it leaves either [2~33] to test. 32 floors if breaks pass 34 and breaks 67 it leaves [35~66] to test . 32 floors if both pass, leaves 68~100 which is 33 floors, Assuming worst case scenario, assume it passed both. TOTAL DROPS : 2 WORST SET 33 floors. SET 2 - DIVIDE AGAIN to 3 parts D, E, F = [68~78], [79~89], [90~100] 11 each Same logic, test at 78, 89. if either breaks, leaves 10 floors remaining. [68~77] or [79~88]. if both passes, leaves 11 floors hence assume worst luck. [90~100] TOTAL DROPS 4 WORST SET 11 floors. Divide again to 3, but 11/3 = 3.6666666. Since we are testing heights, it makes sense to round up our first set. [90~93],[94~97], [98~100]. **if you get why, skip ** ** if we round down, we get 3 floors, 4 floors, 4 floors to cover all 11 floors [90~92],[93~96],[97~100] **If we do this, and test floors 92, 96 and assume worst case scenario, we are left with 97~100. 4 floors. ** if we did it rounding up, even in worst case scenario we get 3 floors. Assuming you skipped ** section, again our luck blows so we assume worst case scenario [98~100] remains. even if we got lucky, we'd be left with 3 floors, [90~92] or [94~96] TOTAL DROPS 6- 3 numbers remain. ROUND 4 >FINAL< so we have 3 numbers.. lets assume 98, 99, 100. drop it at 98 and 99 and 100. if it breaks at 98, top floor it can be dropped is 97 (7 drops) it it passes 98 and breaks at 99, top floor= 98. (8 drops) it passes both, then it can be either 99 or 100 so we test 100. if it breaks, its floor 99, if not its floor 100. (9 drops) So in the worst luck scenario, you only need 9 drops. |