Light bulbs 

Once upon a time, my CTO challenged me for a fun problem of bulbs described below:

You have two light bulbs (or eggs) and a 100 storey building. You must determine the minimal floor such that if you drop the light bulb from that floor it breaks. Once you break a bulb, it can’t be reused.

Question 1: What’s the smallest number of drops required in the WORST case to determine the minimal floor.

The solution is well explained by Craig Mason-Jone here, or you can easily google it. Briefly assuming the minimal number of drops is x, first you drop the bulb at floor x. If it breaks, you try to drop the second bulb from floor 1 to floor x – 1. If the first bulb doesn’t break at floor n, you can try to drop it at floor x + x – 1. If it breaks at x + x -1, then try to drop the second bulb from floor x + 1 to x + x - 2. It breaks down to find x such that:

x + (x-1) + (x-2) + \dots + 1 \geq 100

\frac{x\times(x+1)}{2} \geq 100

It turns out x=14 is the optimal solution (examined by computer).

Question 2: But what if we have 3 bulbs ?

Similarly we assume that the minimal number of drops in the worst case is x. We know that with 2 bulbs and x – 1 drops the maximum number of floors we can examine is \frac{(x-1) \times x}{2}. Hence the first drop will be at floor \frac{(x-1) \times x}{2} + 1. If the bulb breaks, examine the floors from 1 to \frac{(x-1) \times x}{2} with 2 bulbs like mentioned above. If it doesn’t break, we now have x – 1 drops left. Thus the second drop is at floor [\frac{(x-1) \times x}{2} + 1] + [\frac{(x-2) \times (x-1)}{2} + 1]. Similarly we need to find x such that:

[\frac{1 \times 2}{2} + 1] + [\frac{2 \times 3}{2} + 1] + \dots + [\frac{(x-1)x}{2} + 1] \geq 100

\frac{x^3+5x}{6} - 1 \geq 100

\therefore x = 9

Question 3: What if we have k bulbs and n floors ?

We can follow the method as in question 2 or compute a function f(k, n) where:

f(k,n) = \min_{i \in [1,n]}\bigl\{\max[f(k-1,i-1), f(k, n-i)]+1\bigr\}

This can be explained as if we drop a bulb at floor i and the bulb breaks, f(k,n)=f(k-1, i-1) + 1 else f(k,n)=f(k,n-i) + 1; And the worst case is the larger in two. The solution is then to find i where f(k, n) is minimum.

Question 4: What if we have an infinite number of bulbs ?

The function f(k, n) becomes:

f(\infty,n)=\min_{i \in [1,n]}\bigl\{\max[f(\infty, i-1), f(\infty, n-i)]+1\bigr\}

We know that:

\forall i \in [1,n]:\ \max[f(\infty, i-1), f(\infty, n-i)] \ge f(\infty, \frac{n}{2})

Therefore:

f(\infty,n)=f(\infty, \frac{n}{2})+1

\therefore f(\infty,n)=\log_{2}{n}