Biding My Time - The Answer

If you haven't read the original post where I asked the question, you may want to before reading the answer below. This question was asked of me in a telephone interview, and I managed to work out the formula below on the phone in about five minutes. I didn't go the extra step of performing the derivative and setting to zero on the phone - the interviewer was happy enough with the formula.


If you only had one marble/ball/egg, whatever, you would be forced to go serially from floor n to floor n+1 until it breaks and then floor n would be the answer. Since you have two marbles/balls/eggs, whatevers, you can use the first one to narrow down the scope. The question is how to do that narrowing most efficiently.

Assume you are going to divide the 100 floors evenly into groups of n floors, then the first marble can be dropped on every nth floor and when it breaks, the final marble only has to check the n-1 floors between the last two floors checked.

Let d be the number of drops and n be the number of floors per section for the first marble. In the worst case for d (which is what we care about) then:

   d = 100/n + (n-1)

So now to find the minimum d with respect to n, we need to use some high school calculus to take the derivative and set to zero. This yields:

  dd     -100
  --  =  ----  + 1
  dn      n^2

  -n^2  = -100

   n = +/- 10

Since only positive numbers make sense in the scenario, we can see that we should drop the first marble from every tenth floor and then the worst case for the number of drops to find the floor in question is 19.