This month's IEEE GlobalSpec newsletter challenge is:
You’re given 20 destructible light bulbs, and a building with 100 floors. How do you determine the highest floor from which a light bulb may be dropped without breaking, using as few drops as possible?
Extra credit: How do you solve this puzzle having only been given two bulbs?
And the answer is:
First, it helps to define some common properties for this problem:
- If a light bulb is dropped from a given floor and breaks, then any other light bulb will also break if dropped from that or any higher floor.
-If a light bulb is dropped from a given floor and does not break, then neither it nor any other light bulb will break if subsequently dropped from that or any lower floor.
-A light bulb may be dropped any number of times until it breaks, after which it is unusable and cannot be dropped again.
From here out, let f = the building’s total floors and b = the number of bulbs available, and d = the number of drops required.
If we have 20 bulbs – which is more than enough to determine the number of required drops – a simple binary search will suffice. We start by dropping a bulb from the 50th floor. If it breaks, we move to the 25th floor and drop again; if it doesn’t, we move to the 75th floor and drop again.
Therefore, the maximum number of drops is:

or in this case, seven drops.
Extra credit:
Things get more interesting if we have two bulbs – fewer than the maximum number of drops determined above. In this case we need to flip the problem and, given the maximum number of drops d, solve for f instead.
Imagine conducting the first drop from floor k. If the bulb breaks, there must be at most f (d - 1, b - 1) floors below k. If it does not break, there be at most f (d – 1, b) floors above k.
Therefore, f (d,b) satisfies


And we can show via the recursive formula that:

This formula gives a solution to this problem with any amount of floors and bulbs. Given 100 floors and two bulbs, we need 14 drops in a worst-case scenario.
|
Comments rated to be Good Answers:
Comments rated to be "almost" Good Answers: