Here's the answer to the 2-glass balls, 100 storey building problem along with reasoning:
The key is to use both balls optimally. E.g. if we throw the first ball from 100th floor, we will end up throwing ball 2 from floor 1 upwards 1, 2, 3 etc until it breaks. At the other end, throwing ball 1 from 1st (or 2nd) floor onwards will make 2nd ball almost redundant.
If we throw 1st ball from floor 10, 20, 30 etc & the 2nd from 1-9, 11-19, 21-29 etc will mean that in the worst case at each point, (9, 19, 29, ... 99), we will need 1+9, 2+9, 3+9, ...10+9 throws (1st ball 10 times, 2nd 9 times).
Throwing 1st ball from 20, 40, 60 etc & the 2nd from 1-19, 21-39, 41-59 etc will require 1+19, 2+19, 3+19, ... 5+19 throws (1st ball 5 times, 2nd 19 times) in the worst cases (19, 39, 59 ... 99). This shows that the answer is between 10 & 20 when no. of throws of both balls will be balanced at each worst case point.
It's easy to see that the interval between successive throws of 1st ball should be reduced by 1 to ensure that the max no. of throws will stay the same.So if we throw the 1st ball from 10, 19, 27, 34, 40, 45, 49, 52, 54, 55 etc instead of 10, 20, 30, 40 etc, the max throws in the worst case will stay constant at 1+9, 2+8, 3+7, 4+6 (for floors 9, 18, 26, 33, 39, 44, 48, 51, 53, 54 etc) but what do we do after 55? In other words, does the max no. of throws = 10 for 55 storeyed building give us a formula for a 100-storeyed building?
Note that the 1st number is the no. of throws of 1st ball while the 2nd no. is the no . of throws of 2nd ball.
The sum of numbers 1 to n is given by the formula n*(n+1)/2. So the sum of numbers 1 to 10 is 10*11/2=55 where 10 is the no. of floor from where the 1st ball is thrown.
Extrapolating, we have to find the smallest n where n*(n+1)/2 equals or exceeds 100. thus we get the answer as 14 (14*15/2 = 105 > 100).
Dropping the first ball from floors 14, 27, 39, 50 etc ensures you won't need more than 14 throws for any floor till 100.
comment:
p_commentcount