Consider there is a building with 100 floors. You have a pair of identical marbles which you are going to drop from the windows of this building. There is a height at which the marbles are broken if they are dropped from that height. The marbles will break if they are dropped from that height or more, and take no damage if they are dropped from any lesser height. The objective is to determine what floor is that height using as few drops as possible. You may assume that a broken marble is useless, and that you are to minimize the worst case scenario.
To put this problem into "math", there is an integer X between 1 and 100. You may guess an integer and I will tell you if X is " ≥ " or " < " your guess. If I ever say " ≥ " twice, you cannot guess again and must tell me what X is. You are to minimize the worst case for the number of guesses.
A clear naive strategy is just to go up the floors, one at a time, and when the marble breaks you know exactly what floor it happened on. Of course, the worst case here will need 100 drops and you didn't even try to make use of the fact that you have two marbles (actually, that solution is optimal if you only have one marble).
No comments:
Post a Comment