The Light Bulb and Tower Problem

A puzzle interview question I was recently asked:

You have two identical light-bulbs. You need to find out how strong they are. There is a 100-floor building and you can drop the light-bulbs out of the window. You know that there is some floor such that it will break, and it will break for all above it, but you don’t know what floor that is. It will never break for anything less than that floor.

Find the method of doing this such that the worst-case is as small as possible.

Obviously it is possible to just start at floor 1 and go up until you find it. The worst case then is 100 drops, which is pretty poor. An improvement on that is to go up every other floor, using the second light-bulb to work out which floor it was when it breaks. That gives a worst case of 51 drops.

This can be generalised to stepping up N floors each time. Then the worst case would be:

This function can easily be minimised by taking its derivative and seeing where it is 0. This method gives N = 10, suggesting you should go up every 10th step. The worst case is floor 99, which takes 19 drops.

But if it took 19 drops worst case, why did we bother starting on floor 10? If we started on floor 19 we wouldn’t make things any worse, and we might make them better. The key is: If the worst case is k drops, the first level to try should be k.

What about after that? Well, we can go up k-1 more levels and still the worst case stays the same – you only need to check out the k-1 levels between the two points if it breaks, giving an overall of k drops.

So on the assumption that the worst case is k, the best method is to:

  1. Try floor k. If it breaks, try the k-1 floors below it, thus there can be at most k drops. Else go to 2.
  2. Try floor k+(k-1). If it breaks, try the k-2 floors below it. Combined with the two drops already done, there can be at most k drops. Else go to 3.
  3. Try floor k+(k-1)+(k-2). If it breaks, try the k-3 floors below it. Combined with the three drops already done, there can be at most k drops. Else to go 4.
  4. And so on

So what should this value of k be? Well it is the least k such that there is some r such that:

That r may as well be zero, so we just need to find the least k such that the sum of the first k integers is greater than 100. Using the formula, that is just:

As k and k+1 are next to each other, this means the answer has to be somewhere around the square root of 200, which is about 14. Indeed, 14 is the least value, as it is easily seen that 13 does not work.

Therefore the floors you should try are:

  • 14, going back to floor 1 if it breaks
  • 27, going back to floor 15 if it breaks
  • 39, going back to floor 28 if it breaks
  • 50, going back to floor 40 if it breaks
  • 60, going back to floor 51 if it breaks
  • 69, going back to floor 61 if it breaks
  • 77, going back to floor 70 if it breaks
  • 84, going back to floor 78 if it breaks
  • 90, going back to floor 85 if it breaks
  • 95, going back to floor 91 if it breaks
  • 99, going back to floor 96 if it breaks
  • 100, although by now you know it must be 100 without trying it.

I’ve written a little Java program (using Multimedia Fusion) to try out the two approaches. Check it out

Download

Advertisements

One Response to The Light Bulb and Tower Problem

  1. Nice analysis! I won $10 at a Math Monday contest, answering this question with Mac computers instead of lightbulbs. (I don’t remember the number of floors.) I can’t find the blog it was on now… I never got to the calculus part. I like that.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: