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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.