Two Marbles and a 100 storey building

This is apparently a popular puzzle, and I decided to have a go because why not?

Puzzle description:

You have a 100-story building and a couple of marbles. You must identify the lowest floor for which a marble will break if you drop it from this floor. How fast can you find this floor if you are given an infinite supply of marbles? What if you have only two marbles?

While reading the description I was getting a heavy “divide and conquer” vibe from it, so I took it from there.

Solution with infinite marbles Link to heading

This is indeed a divide and conquer problem, and in particular a pure binary search one. We therefore need to find the minium amount of drops required to find the solution floor.

We do that by dividing the input in half on every drop, what we’re essentially doing is saying “how many powers of 2 can we fit in a 100 storey building?” And the answer to that is log₂ (x) where x = 100, which gives us 6.6438 $\approx 7$.

If you think I pulled that solution out of my nether regions, you need to remember what a logarithm is. A mental trick I use is to remember logs is to reword it lke this: “how many times do I have to raise the base to get the X?”. In this case $2^{6.64} \approx 100$. We end up rounding 6.6438 to 7 because 100 is not a power of 2.

The actual floor where the marble breaks will depend on factors not mentioned in the puzzle, but what we do know is that we can find said floor in 7 drops at worst.

This runs in $ O(log (n))$ time.

Solution with two marbles Link to heading

The pure binary search approach doesn’t work here, we don’t have seven marbles. Yet some sort of criterion to reduce the problem space is still needed. The first marble has to be cleverly used to find one or more intervals, while the second simply has to be used to linear search floor by floor until it breaks.

The tricky part is discerning the jumps/intervals of the first marble in order to minimise the drops of the second one, if it is ever needed. Going to floor 50 is a bad idea, because the first marble might break and we might potentially need to linear search from floor 1 - 49 with the second one; or on the flip side if it doesn’t break at floor 50, it could also not break from floor 51 - 100, potentially requiring another 49 drops.

Reducing the initial floor from 50 to 25 is an improvement, but I was still getting outcomes that required $ > 20 $ drops (I didn’t try all possible combinations – ain’t nobody got time for that). I further reduced the initial floor from 25 to $12.5 \approx 13$.

I was satisfied with floor 13 as starting point, but also noticed that it would be more sensible to reduce the jump size by 1 as we’re climbing the building. Why? Because it stands to reason that as we go higher the probability of the marbles breaking increases, and we ought to minimise risk (I’m a finance graduate after all), Which gives us the following sequence:

{ $ 13, 25, 36, 46, 55, 63, 70, 76, 81, 85, 88, 90, 91 $ }

But 13 floors jumps don’t perform well if solution floor is at 100, it takes 13 + 8 = 21 drops.

I knew the optimal solution was somewhere in the range of 12 - 15 as starting points, so I tried them but settled for 14 as I noticed that the average worst case drops stayed the same:

{ $ 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100 $ }

If for example, the solution is on floor 38, it takes us 3 + 11 = 14 drops to get there. If it’s on floor 89, it takes us 9 + 5 = 14 drops, etc. Doing the same with 12 and 15 doesn’t yield the same result, that is worst case drops vary dramatically, but with 14 it always takes at most 14 drops to find the solution floor.

The runtime for this is hard to tell, but we know it’s somewhere in between a linear search $ O(n) $ and a binary search $ O(log(n))$.