Super Challenger Week 3

Week 4 Puzzle:

You have two light bulbs in a 100-story building. You want to find the floor at which the bulbs will break when dropped. Find the floor using the least number of drops.

 

Answer: 14

1,   2,  3,  4,  5,  6,  7,  8,  9, 10, 11  <=== Drop #
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99  <=== Floor
13, 26, 38, 49, 59, 68, 76, 83, 89, 94, 98  <=== Worst case floor #
13, 12, 11, 10,  9,  8,  7,  6,  5,  4,  3  <=== # of sequential drops
14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14  <=== Total # of drops in worst case

The worst case happens when the bulbs break at floor 13. Our first bulb breaks when we drop it from the 14th floor. Then we have to drop the second bulb one by one until we get to 13 (13 + 1 = 14 drops).

If the bulb doesn’t break after the first drop we can add another 14 floors and drop from the 28th floor just like the 19 drop solution above. However if the bulb breaks at the 27th floor we would have to make 15 drops.

Instead, if we add 13 floors (14 floors – 1 drop), and the first bulb breaks on the 2nd attempt, our worst case is the bulb breaking at the 26th floor. This is still only 14 drops, 2 to break the first light bulb + 12 to break the second.

Continuing on by adding 12 floors we get 3 drops to break the first bulb + 11 to break the second. For every extra drop we use to break the first bulb, we have to decrease the amount of floors to add by one to compensate for that drop.

How do you determine that you should start with 14? It is the first number n where the sum of the numbers 1 through n is greater than 100 (1-14 = 105 vs 1-13 = 91).