Marbles and Floors

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.