20-CS-110-001 Introduction to Computer Science Fall 2010

Marble Drop Puzzle

    You are standing outside a 30 story building. A man gives you two marbles and tells you that dropping them from one of the floors will make the marbles break, and it's your job to figure out what floor that is. You're standing on the first floor, and he demonstrates by dropping one of the marbles which doesn't break, he leaves the rest of the floors up to you, but:
  1. You only have two marbles.
  2. You want to optimize for the worst case number of drops. (as opposed to, say, for the best average number of drops).
In other words, what's the lowest answer you can give to: "I can find that floor in ___ drops" ?
       
    solution