|20-CS-110-001||Introduction to Computer Science||Fall 2010|
Solution to Marble Drop Puzzle
|First of all - let's take that free piece of information about the
first floor. We only need to check floors 2-30 now since we know
it doesn't break on the 1st floor. So let's treat the problem as
29 floors, looking at 1-29.
The trick is to realize that the initial algorithm creates itself. You need to cover the full space of floors 1-29 since it could be any one of them that could cause the marble to break.
If you ever drop a marble and it breaks and there are floors below it that you haven't examined yet, then you are stuck trying them one by one from the bottom up - you can't risk breaking the other marble. If you drop from an initial floor towards the bottom, call it 'n', then that's now your worst case number of drops. If it doesn't break, then you have n-1 drops to check all the floors above. So, go up n-1 drops and try again, if it breaks you can still check the n-2 levels between the first and second drop without increasing your worst case.
So, as a concrete example, let's start on the 8th floor. If it breaks, try floors 1-7. The worst case we are going for is 8. If it doesn't break, then the second drop is to try the 15th floor (8+7). If it breaks, we have six drops left to try floors 9-14 and our worse case is still 8. If it doesn't break on the 15th, the third drop is the 21st (8+7+6).
So, trying 8, we find we can make it, because 8+7+6+5+4+3+2+1 = 36
It seems like 7 isn't enough. On the 7th drop we'll have gone 28 floors.
Consider our original algorithm at the end using a worst case of 7 drops. Our 5th drop will be on the 25th floor (7+6+5+4+3=25). If we continue the original algorithm, we'll do the following drops:
It seems we didn't make it!
But don't forget, we know that it will break on at least one of the floors - so if it didn't break on 28, then it must break on the 29th! Since we needed a total of 29 floors (2-30), then our problem is solved.