Yoak: Batteries, and the Problem of the Week
Recently I discovered Stan Wagon’s Problem of the Week. This is a delightful mailing list / site and some of the problems are in the vein of puzzles I post here. Recent problem 1125 captured the attention of several Math Factor authors so I thought I’d post the puzzle here as an excuse to introduce you all to that list.
You have eight batteries and know that four are good and four are dead, but don’t know which are which. Your only method of testing them is to insert two into a device that will work if you’ve put in two good batteries and not otherwise. How many such “tests” are required in order to be sure that you’ve located two good batteries?
As of this posting, the answer to this question is not yet on the POTW website, but if you come to this later, the spoiler may be there, so be careful to avoid spoilers if you want to work this through.
The Math Factor in iTunes
RSS feed
Comments RSS
mathbun.com
laciermaths said,
November 21, 2009 at 6:34 am
First, put the batteries in pairs, and test each pair. Since exactly half of the batteries are good, we find zero, one, or two pairs of good batteries.
If we find two pairs, we are finished, and used at most four tests.
If we find one pair, then we have six batteries of unknown quality, of which two are good. A naive strategy suggests testing each of the six with one of the known-to-be-good batteries, so we should try to devise a strategy that uses fewer than six tests. To see that one doesn’t exist, consider that there are 15 possible tests we can run among the six batteries; only one of them will show up positive, and we have already gone through three of them. Since testing a good battery and a bad battery imparts no information about the good battery, we would need twelve tests in the worst case. So the naive strategy is best, and we use at most ten tests altogether in this case. (Another way to put it is that now, among the unknown batteries, a smaller proportion are good, so we can’t do any cute pigeonhole pairing tricks like we do above.)
If we find no good pairs, then exactly one battery in each pair is good. Suppose we take pairs (A,B) and (C,D), and both pairs tested negative. There are four remaining tests we can make on these four batteries, and we only need to execute three of them (if all of them are negative, then we know the last test would be positive by process of elimination). Thus we need three tests for each pair of pairs, or 4 + 3 + 3 altogether in the worst case.
Therefore at most ten tests are required to determine which batteries are good.
The Math Factor Podcast » Follow Up: Yoak: Batteries, and the Problem of the Week said,
November 21, 2009 at 4:45 pm
[…] Yoak: Batteries, and the Problem of the Week […]