Series: Subject: Topic:
Question: 31 of 246

# Marbles and Floors

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?
Asked by: hari_nowayout | Member Since Jul-2008 | Asked on: Mar 26th, 2011
Showing Answers 1 - 1 of 1 Answers
Sereche

Answered On : Jul 8th, 2012

View all answers by Sereche

Sounds like a simple binary search to me. For 100 floors, you would need at most 7 marbles to reach an answer. More generally, with n floors, you would need ceiling(Log2(n+1)) marbles.

If the floors are numbered 1 through 100, you would first drop a marble from floor 64 (2^6). If it breaks, test floor 32 (2^6+2^5); if not, test floor 96 (2^6+2^5). You would continue this process (either adding or subtracting the next-highest power of 2) until your interval is 2^0 = 1. For more information regarding this process, see

https://en.wikipedia.org/wiki/Binary_search

With only 2 marbles, you cannot conclusively answer the question. Assuming that a marble will break if dropped from the hundredth floor, you would first try a drop from floor 50, then from floor 25 or 75. This gives you an estimate range of 25 floors.

The above algorithm optimizes for minimum number of drops in the worst-case. I have heard a variant of this question where, for every drop, the experimenter must run up to the floor, then run back down to the ground to see if the marble broke (and therefore, dropping from higher floors is a more expensive test). The answer to this question is, of course, much more difficult.

If you think the above answer is not correct, Please select a reason and add your answer below.