Associated Topics || Dr. Math Home || Search Dr. Math

### 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

```

```
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
=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/
```
Associated Topics:
College Algorithms

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search