Dropping Light Bulbs (or Eggs): An Interview Puzzle Twist

I had planned to at least take a few holiday weeks off from this blog, and maybe back off from writing much more at all, putting a bow on this interesting and fun “experiment” over the last year and a half.

But subject matter seems to keep dropping in my lap.  In just the last two weeks I learned about some cool new science, a brilliant and elegant algorithm I had not heard of, and a nice twist on an “old” mathematical puzzle.

That is plenty to choose from; but since I love puzzles, and since I am still technically trying to be on vacation, this week I will just briefly present the puzzle, and we’ll see how it goes from there.

A variant of the problem appeared in a year-end compilation of “Top 25 Oddball Interview Questions” (the entire list is at glassdoor.com):

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

Before continuing, although I like this problem as a mathematical puzzle, I tend to dismiss this (or similar puzzles) as a useful interview question, for reasons I have discussed before.  But whether asked in an interview or not, note that this is not the possibly-vague “lateral thinking” type of problem as suggested here.  For those who have not heard this one before, we can make the problem precise as follows:

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.  Your objective is to determine the highest floor from which a light bulb may be dropped without breaking, using as few drops (i.e., making as few elevator trips) as possible.  What should your strategy be to minimize the worst case number of drops required?

Problem 2: This problem caught my eye because I suspect that it actually contains a typo– but an interesting typo.  In the usual statement of the problem, instead of having 20 light bulbs at your disposal, you have only 2, and if/once they are both broken, you must have enough information to determine the highest floor from which a light bulb may be safely dropped.  Now what should your strategy be?

Problem 3: The above two variants of the problem are actually somewhat special cases, “endpoints” of a more general problem that still has a very elegant solution.  In this third “twist” variant, suppose that you have 5 light bulbs; now what should your strategy be to minimize the maximum number of drops required?  As usual, can you generalize as a function of the number of floors and light bulbs?