Light Bulb Puzzle Solution

Posted on by

Last week’s post presented several variants of the following general problem: you have a number of light bulbs, and you need to determine the highest floor in a building from which a bulb may be dropped without breaking.  All light bulbs are identical in that they all have the following properties:

  1. 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.
  2. 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.
  3. A light bulb may be dropped any number of times until it breaks, after which it is unusable and cannot be dropped again.

A “drop” consists of taking a single light bulb in the elevator up to a particular floor, dropping the light bulb from that floor, taking the elevator back down, and checking whether the dropped light bulb broke.

If the building has f=100 floors, and you have b light bulbs at your disposal, what is the least number of drops d required to guarantee that after at most d drops you can determine the highest floor from which a light bulb may be dropped without breaking?

Each variant of the problem from last week simply changed the value of b, the number of available light bulbs.  The basic idea is most clearly illustrated with the simplest case of b=1; with just a single light bulb, we can do no better than dropping from floor 1, then floor 2, 3, 4, etc., until the bulb finally breaks, requiring d=f=100 drops in the worst case.

At the other extreme, suppose that we have “plenty” of light bulbs that we can afford to break (i.e., b \geq f).  In this case, intuition correctly suggests that a binary search is the right approach: for a 100-floor building, start by dropping a light bulb from floor 50.  If it breaks, then drop a second bulb from floor 25, otherwise drop the second bulb from floor 75, reducing the number of “candidate” floors by approximately half with each drop.  The maximum number of drops required is d=\lceil\log_2(f+1)\rceil, or 7 drops in the case of the original interview question from last week:

Problem 1: “Given 20 ‘destructible’ light bulbs (which breaks at certain height), and a building with 100 floors, how do you determine the height that the light bulb breaks?” – Asked at QUALCOMM

As I said last week, I suspect that this question actually contains a typo, since 20 light bulbs is “more than plenty;” we will only ever actually use 7 of them.  Things get more interesting if we have a more limited supply of light bulbs to break.  In the usual statement of this problem, b=2, and the final variant from last week asked the question for b=5.  However, we can tackle all of these variants at once by solving the general case.

The key to the solution is to turn the problem around, so to speak, and solve for f instead of d.  That is, given a maximum number of drops d, and a supply of b light bulbs, what is the tallest building that we can handle?  More precisely, what is the maximum number of floors f(d,b) for which we can guarantee to find the “critical” floor in at most d drops?

Consider the first drop from the as-yet-unknown optimal floor k.  If the bulb breaks, then by Property 1 (and 3) above, there must be at most f(d-1,b-1) floors below floor k.  If the bulb does not break, then by Property 2 (and 3), there must be at most f(d-1,b) floors above floor k.  Thus, f(d,b) satisfies the following recurrence relation:

f(d,b) = f(d-1,b-1) + 1 + f(d-1,b)

f(d,0) = f(0,b) = 0

Using the identity

{d \choose b} = {d-1 \choose b} + {d-1 \choose b-1}

it is not difficult to show that

f(d,b) = \sum_{k=1}^b {d \choose k}

This gives us a solution to all three original problems.  For any given number of floors f^* and number of light bulbs b, we simply find the smallest number of drops d for which f(d,b) \geq f^*.  To answer Problem 2, for example, for a 100-floor building with 2 light bulbs, we need 14 drops in the worst case.

Problem 3: Similarly, with 5 or more light bulbs we can do it in 7 drops… but we must be careful, since a binary search will only work with 7 or more light bulbs.  If we only have 5 (or 6) bulbs, the optimal strategy is slightly different.  Fortunately, the counting argument above gives a recipe for determining from which floor to drop the next light bulb in any situation: assuming that we have calculated the optimal number of drops d remaining, the next drop should be from floor f(d-1,b-1) + 1, counting from the lowest remaining “candidate” floor.  For example, beginning with 5 light bulbs, the first bulb should be dropped from floor 57.  If it breaks, the second bulb is dropped from floor 26.  If it also breaks, the third bulb is dropped from floor 11.  If it breaks, the fourth bulb is dropped from floor 4.  If it breaks, the fifth and final bulb must be dropped from floors 1, 2, and 3 in the worst case, for a total of 7 drops.

Finally, using the identity

\sum_{k=0}^d {d \choose k} = 2^d

we can see how the binary search arises in the case where we have “more than enough” light bulbs.

 

10 thoughts on “Light Bulb Puzzle Solution”

  1. Hi. When you write:

    f(d,b) = f(d-1.b-1)+1+f(d-1,b)

    you’re saying at that particular drop the the bulb both breaks AND does not break. But only one of those 2 cases can happen. So how can you combine the 2 cases into a single equation? Can you elaborate?

    Reply ↓

    • You’re right, either the bulb will break *or* it won’t. We aren’t saying that the bulb breaks *and* does not break. It’s either-or… but we need to be able to successfully find the “critical floor” in either case. Recall what the function f(d,b) computes: the maximum number of contiguous floors among which we can distinguish the critical floor in d drops using b bulbs. Then think of the two f() expressions on the right-hand side as breaking down the original problem into the two possible subproblems, depending on the outcome of the first (optimally-placed) drop.

      It might help to consider an explicit example. Consider a building with 105 floors, and assume that we have two light bulbs, and that we get at most 14 drops. (Note that f(14,2)=105.) We should drop the first bulb from the 14th floor. If it breaks, then you can think of us being left with a “shorter building” consisting of the lower 13 floors, one remaining bulb, and 13 more drops (i.e., f(13,1)=13). If it does *not* break, then our “shorter building” consists of the 91 floors *above us*, also with 13 more drops, but still with 2 bulbs left (i.e., f(13,2)=91).

      Reply ↓

  2. In the case you illustrate (105 floors and 2 bulbs), what is the required number of drops when 97th floor is the lowest floor from which when dropped, the bulb breaks?

    Reply ↓

    • In this case we need 13 drops. Using the “recipe” described above, the first 11 drops are from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, and 99, when the bulb finally breaks. (In each of these cases, we are moving up f(d-1,1)+1==d floors at a time.)

      At this point, we are in a “shorter building” consisting of the 3 floors 96-98, with 1 drop left. Since f(d,0)+1==1, we simply work up a floor at a time, dropping from floor 96 (without breaking), then floor 97, where the bulb breaks, for a total of 13 drops.

      Reply ↓

  3. Pingback: The discreet hotel manager | Possibly Wrong

  4. brilliant analysis. Loved it. couple of questions. Unless my math is wrong the following are the numbers for F(7,3)= 63 , F(7,4)=97, F(7,5)= 113, F(7,6)=110, F(7,7)=101. Why do you think logically with 7 changes and increasing amount of light bulbs, the numbers of floors that I can tackle is coming down. It appears i might have made an error but i cant seem to find it.

    Reply ↓

  5. sorry. found my error. I forgot to add 1 when going with more than 3 bulbs. I was just attempting recursive addition. It all matches now. F(7,3) =63, F(7,4)=98, F(7,5)=119,F(7,6)=126, F(7,7)=128. It is interesting how you don’t gain much still moving from 5 bulbs to 7 bulbs with 7 attempts

    Reply ↓

  7. I learned of the following direct explanation for why f(d,b)\ge\sum_{k=1}^{b}\binom{d}{k}, which proves the constructive strategy is optimal. First, consider the proof why binary search is optimal. If you make k queries about an unknown number, each of the form “is the number \ge q?”, then the information you get is a sequence of k zeroes and ones. If there were more than 2^k possibilities for the unknown number, then the pigeonhole principle shows there would be two numbers for which your strategy gives the same answer, meaning your strategy cannot distinguish them.

    Now, in the light bulb dropping setup, the information you observe is still a sequence of d zeroes and ones, where zero means the bulb survived and one means it broke. However, this string must now have at most b ones. The number of such strings is of course \sum_{k=0}^b \binom{d}k, so the pigeonhole principle dictates that this quantity must be at least $\latex f+1$, else there would not be enough information to distinguish the f+1 possibilities (the f accounting for each possible floor being the highest floor, and the +1 accounting for no floors being high enough).

    Reply ↓

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.