By: The Math Factor Podcast » Follow Up: Yoak: Batteries, and the Problem of the Week

Sat, 21 Nov 2009 21:45:21 +0000

[…] Yoak: Batteries, and the Problem of the Week […]

By: laciermaths

laciermaths — Sat, 21 Nov 2009 11:34:23 +0000

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.

Comments on: Yoak: Batteries, and the Problem of the Week

By: The Math Factor Podcast » Follow Up: Yoak: Batteries, and the Problem of the Week

By: laciermaths