Perilous Ping-Pong

Date: 11/14/97 at 10:16:11
From: Amanda Stone
Subject: Perilous ping-pong

The President is going to a ping-pong match in Tokyo. He is taking
8 balls with him. A terrorist has implanted one of the balls with 
explosives, but they add such a small amount that no one can tell the 
difference. The CIA has only enough time for TWO weighings before the 
match.  

I know that you must weigh more than one ball on each scale and that 
you can get information from the good batch of balls. Can you help?

Thanks.

Date: 11/14/97 at 13:34:37
From: Doctor Tom
Subject: Re: Perilous ping-pong

Hi Amanda,

I assume the explosive (bad) ball is heavier and the others all weigh 
the same, or the problem is totally hopeless.

This isn't possible to solve if all you can do is weigh them. It can 
be done in 3 weighings, assuming you already know what a normal ball 
weighs. In 3 weighings, here's how to do it:

  Weigh 4 balls. If it is exactly 4 times as heavy as
  one ball, the explosive ball is in the other batch, and
  in any case, you've now got it down to 4.

  Take the set of four with the bad ball and weigh 2 of them.
  You now know which set of 2 is bad.

  Weigh one of the 2 bad balls. If it's normal, the other is bad.

I can prove that the problem, as stated, can't be solved in two
weighings. Each weighing will give only one bit of information, and 
there are 8 balls, so 8 possible solutions, which is 3 bits of 
information. With only 2 bits in two weighings, you can't possibly 
work the problem.

The other possibility is that maybe the question means to use a
balance (where you can compare 2 weights). In this case, the problem 
can be solved, even without knowing what a good ball weighs. In fact, 
you could do it with up to 9 balls.

  First, balance 3 against 3. If they balance, the heavy ball must
  be among the other two, and a single comparison of those two on
  the balance shows which one is heavy.

  If not, the set of 3 that's heavier contains the bad one. Put
  one of those on each side of the balance, and if one is heavier,
  it's the bad one.  If they match, the other ball is bad.

-Doctor Tom,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/