You are in a 100 story building and you have two identical marbles. You want to find out the highest floor in the building you can drop marbles off without them breaking. After you drop a marble, if it breaks it is unusable. If it survives it is not weakened at all.
Find the minimum number of drops you need to guarantee finding the highest floor you can safely drop marbles from.
You need at most 14 drops.
Proof
Let the maximum number of drops be
With 2 marbles, we know if we break the first marble on the first drop, we will
only have 1 marble and
If the first drop succeeds we still have 2 marbles, but only
Continuing like this we can see that the maximum number of floors we can test is given by:
The smallest
Drop the first marble on floors
General case
With
Firstly note, having more than
In any given strategy, decide how many marbles will break, and call it
There are
Any strategy that achieves this limit is thus optimal.
Let us define such a strategy. We will use the variables:
for the current number of drops left for the current number of marbles left for the maximum floor number we can safely drop a marble from. for the current floor number
Initially set
- Set
-
Drop a marble from from floor
, and set- If it survives set
- If it breaks set
- If it survives set
- If
and jump back to the top - Otherwise stop, the maximum safe floor is