ANAMIKA

'(The Blog) With No Name', perhaps best described as a stream of notes and thoughts - 'remembered, recovered and (sometimes) invented'.

Saturday, April 16, 2005

Glass bulbs - a puzzle

The 'base version' of the puzzle:

You are standing next to a 100 floor building and are given two glass bulbs from a stock of identical bulbs and need to destructively measure their strength as follows - the strength of the bulb is defined as the lowest floor of the building from which it will break on being dropped. It is required to calibrate the bulb strength with least number of drop experiments in the worst case.

For instance if there were only one bulb, one necessarily has to drop it from floor number 1, 2, 3,.... till it breaks. In the worst case one might end up doing 100 drops. There is no scope for improvement.

What if two bulbs are given and you are allowed to break both?

The full version:

Same as before but you are given M bulbs from a large stock and an N floor building. How to minimize the worst case number of drop experiments?

From a computer science viewpoint, this can be viewed as a searching problem - We have a key that is unknown and are trying to find it in a given sorted list by comparisons with elements thereof with the comparisons giving only "less" or "greater" as answers. More precisely we are trying to find the least element in the sorted list that is greater than or equal to the key.

But there is a constraint. The number of comparisons between the given key and list elements larger than the key cannot be more than a certain number (corresponds to the number of bulbs available to break). Without this constraint, one could employ a free binary search or some such procedure.