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/