Applying Logic to an Interesting Problem on Billiard Balls
Date: 03/03/2004 at 16:56:18 From: Kara Taft Subject: Breakable billiard Balls In front of you is a 100 story building. You must determine which is the highest floor you can drop a billiard ball from without it breaking. You have only two billiard balls to use as test objects. If both of them break and you don't know the answer then you have failed at your task. What is the least number of drops needed to be sure you will have determined the breaking point? As a hint, 14 drops is the best answer, 18 drops is a good answer.
Date: 03/03/2004 at 18:32:53 From: Doctor Douglas Subject: Re: Breakable billiard Balls Hi Kara. This is a very interesting algorithm development problem. Indeed, I've found a solution where 14 drops (maximum) is the best answer. I will make a few remarks in the hopes that this will be enough for you to figure out the solution on your own. 1. Here's a stupid strategy that works if you have only ONE ball. Drop in on the lowest floor 1, if it survives, move up one floor. At the end of this process, you will know which was the last floor it survived. If you are down to one ball, this is a good strategy. 2. But you have two balls, so your strategy can be more "aggressive" in the beginning. Suppose you drop the first ball on floor ten. Then if it breaks, you know the answer is somewhere between floor 1 and floor 9. You have one ball left, and you can resort to the strategy in (1) above, and find which of these floors is the highest. It might take 9 more drops (because you have to test floor 1, floor 2,..., and floor 9). 3. Because we know from the hint that 14 drops is the maximum, we can actually be more aggressive still, we might as well drop the first ball on floor 14, and (if it breaks), use the other thirteen drops with our second ball to find the answer. Thus our strategy might look something like the following tree. A descent to the left indicates that the test on that floor resulted in a broken ball, a descent to the right indicates that the test on that floor resulted in an intact ball. We can have, at maximum, TWO leftward movements: 14 - N Numbers indicate we test on that floor. / left symbol (/) means broken ball. 1 right symbol (\) means intact ball. / \ =0 2 / \ =1 3 / \ equals sign indicates answer to problem =2 . (e.g. =2 means floor 2 is the highest) . . 13 / \ =12 =13 Notice that for most of the outcomes, we end up with two broken balls, but we do know what floor was the highest successful test. 4. This is the decision tree that results if the first test (at floor 14, is unsuccessful. The number N is the next floor to be tested (N > 14). You have to make an intelligent guess as to what this number N is, and be sure that you can test floors 15 up to N-1 with the remaining 13 drops. Remember to be as aggressive as possible, and that floor 14 is at this point known to give an intact ball. 5. As you go up this tree, you will be using up drops, so the lengths of these branches will have to get shorter. Hopefully, that will be enough for you to develop a strategy in which fourteen drops are sufficient for all 100 floors. You may be able to see the pattern develop that demonstrates that thirteen drops are insufficient. - Doctor Douglas, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2015 The Math Forum