Battery Dilemma

If we test six batteries at a time, and only get a success when four good batteries are chosen, this is the same as testing an "antitorch" which takes two batteries, and only works when both are bad (since the main torch only works when two bad batteries have been left out).

Interchanging the role of "good" and "bad", this problem is therefore the same as that of a more ordinary torch that uses two batteries, and only works when both are good.

To find a pair of good batteries for this ordinary torch, split the eight batteries into two groups of $3$ batteries and one pair of batteries. One of these three groups must contain two or more good batteries. It takes up to $3$ tests to determine whether a group of $3$ contains a pair of good batteries, and just one test to test the pair. Thus we can find light up the torch after at most $7$ tests, and so we will know where a pair of good batteries is after at most $\boxed{6}$ tests.

Now let us show that we cannot do this with fewer tests. We shall show that, for any choice of $6$ tests, there will be a distribution of the batteries which means that those six tests will not result in a torch that lights up. Unless the torch lights, and we have won, we get no feedback from the tests, and so there is no possibility of a strategy which depends on the outcomes of previous tests. Thus we just need to decide on which selection of batteries to test, and see what happens.

For any set of six tests, let $G$ be the graph defined by having the eight batteries as vertices and with six edges, where an edge exists between two vertices precisely when those two batteries have been tested. Since the number of edges is less than the number of vertices minus one, this graph is not connected. I claim that we can find always find four vertices out of the eight so that no two out of these four have edges between them. If true, this would mean that there are four batteries out of the eight such that no two of them have been tested. This would mean that, if those four batteries were the good ones, then the proposed set of six tests would not find a pair of working batteries.

If the disconnected graph $G$ has four or more components, then we can choose four vertices such that each vertex belongs to a different component, and we are done.

If the disconnected graph $G$ has three components, then the three components can have the following vertex counts: $(6,1,1)$ , $(5,2,1)$ , $(4,3,1)$ , $(4,2,2)$ or $(3,3,2)$ . In the first case, the $6$ -vertex component has $6 < {}^6C_2$ edges, and so there are two vertices out of the six which do not have an edge between them, If we choose those two vertices, and one vertex from each of the other two components, we obtain four vertices, no two of which have an edge between them. In the second case, the component with $5$ vertices has $5 < {}^5C_2$ vertices, so we can choose two vertices from that component and one each from the other two, to obtain a set of four vertices with the right properties. In the third case the component with $4$ vertices has at most $4=6-2< {}^4C_2$ edges, so we can find two unconnected vertices from that component, and one each from the other two, to obtain the desired set of four. Similarly, in the fourth case, the component with $4$ vertices contains $4 < {}^4C_2$ vertices, so we can choose two unconnected vertices from that component and one vertex each from the other two components to obtain the desired set of four vertices. Finally, in the $(3,3,2)$ case, one of the components with $3$ vertices will contain $2$ edges, while the other contains $3$ . We can choose two unconnected vertices from the component with $3$ vertices and $2$ edges, and one vertex each from the other two components, and we are done.

If there are just two components, then the components can have the possible vertex counts: $(4,4)$ , $(5,3)$ , $(6,2)$ and $(7,1)$ . In the first case, the two components both contain $3 < {}^4C_2$ edges, so we can choose two unconnected vertices from each component, making a set of four vertices with the required properties. In the second case, the components have $4 < {}^5C_2$ and $2 < {}^3C_2$ edges each, and so we can choose two unconnected vertices from each component, giving us a set of four vertices as required. In the other two cases, the component with $6$ (resp. $7$ ) vertices contains $5$ (resp. $6$ ) edges, and is connected, and hence is a tree. For any $n \ge 6$ , the complete graph $K_n$ has the property that if its edges are $2$ -coloured (so that each of its edges are coloured either red or blue), then it is possible to find a monochromatic subtriangle. We can $2$ -colour the graph $K_6$ (resp. $K_7$ ) by colouring an edge between two vertices red if the component of $G$ with $6$ (resp. $7$ ) vertices contains that edge, and colouring that edge blue otherwise. Since the component of $G$ with $6$ (resp. $7$ ) vertices is a tree, it contains no triangles, and hence the coloured graph $K_6$ (resp. $K_7$ ) contains no red triangles, and hence much contain a blue triangle. Thus we can find a trio of vertices in the component of $G$ with $6$ (resp. $7$ ) vertices such that no two of them are connected by an edge. Add a vertex from the other component, and we are done!

Thus we do indeed need at least $7$ tests to light up the torch.

Number the batteries 1 to 8. As Mark Hennings suggests, split the batteries into a groups: (1,2,3) (4,5,6) (7,8)

Test batteries (4 to 8) plus one battery from the first group -- which will be three tests. If there are three bad batteries in group 1 then the device will work first time. If there are two bad batteries in group 1 then when you use the one good battery the device will work. If there is only one bad battery in group 1 then the device will not work for any of the three tests.

So if the device did not work in any of the first three test we know that there is exactly one bad battery in (1,2,3).

Now test batteries (1 to 3 plus 7,8) plus one battery from the second group -- which will be three tests. If there are three bad batteries in group 2 then the device will work first time. If there are two bad batteries in group 2 then when you use the one good battery the device will work. If there is only one bad battery in group 2 then the device will not work for any of the three tests.

So if the device did not work in any of the second three test we know that there is exactly one bad battery in (1,2,3) and one bad battery in (4,5,6). So the other two bad batteries must be (7,8). We only have to identify a set of batteries that will work - we don't have to run a 7th test to prove it, and we know that using (1 to 6) will work.

While you might be lucky and find a combination that works before you have completed the 6 tests, we were asked to find the worst-case scenario.

We are looking for two bad batteries outside the torch. If it doesn’t light, at least one of the pair outside must be good. This is the information you get. We need to collect enough bits of information or exhaust all possibilities, collecting information is normally shorter.

Test 1:If we label the batteries a1 a2 b1 b2 c1 c2 d1 d2. Put in pairs a b and c in the torch. For worst case the torch doesn’t light till the last possible opportunity. No light so d1 and d2 cannot be two bad.

Test 2: Repeat leaving out pair c. No light therefore pair c must have at least one good

Test 3 and 4: Repeat leaving out pair b then pair a. None of the pairs can be 2 bad. Therefore all pairs must all be ‘one bad, one good’.

Test 5: Leave out a1 and b1, still no light a1,b1 can’t be 2 bad.

Test 6: leave out a2 and b2, still no light then a1 and b2 or a2 and b1 must be a pair of bad.

Test 7: leave out a1 and b2, no light, a2 and b1 must both be bad.

This is one more test than needed but you would have done it quicker than working out a shorter method.(best real life solution)

However having done test 3 you also know that there are at least 2 good batteries in the torch from set c and d so set a cannot be two good. Extra info, so either set b is 2 good or all sets are one each. (Test 4.1) a1 b1 left out and (test 5.1)a1 b2 left out , no light, we now know that a1 must be good, therefore a2 must be bad. (Test 6.1)a2 with b1 left out, no light, b2 must be bad. Light will therefore work with a2 and b2 left out. 6 tests, one conclusion.

It should be possible to calculate from the number of bits of information you need where you need to know 2 bits of info (2i) where i is knowing where one bad battery is. Each test gives you I think i/3 as it limits a pair from bad-bad or bad-good or good-good to only 2 of those options, but I will leave that idea to someone else.

Number the batteries 1-8. At any given time, six of the batteries are in the device, but we only need four good batteries to make it work. So to simplify the analysis, choose two of the batteries and just leave them in the device. If one or both are good, we'll find out relatively quickly. If both are bad, so be it - we're looking for "worst-case" scenario anyway.

Now test all possible combinations of the remaining six batteries in groups of four:

1,2,3,4
1,3,4,5
1,4,5,6
2,3,4,5
2,4,5,6
3,4,5,6

We're done: Some combination of these six batteries, plus batteries 7 and 8 always in the device, will make the device work.

I'd argue more than 6 tests are possible in the worst possible scenario. Picking at random 6 batteries half of which are duds you proceed to replace each battery with another dud after replacing each battery you know that the remaining battery must be charged and it can take a further 4 tries to replace a dud.