Problem with batteries

Label the batteries A, B, C, D, E, F, G, H.

Try the combinations AB, BC, and AC. In the worst case, those three combinations will fail. This means that there are either 0 or 1 good batteries among A, B, and C. Then there are 3 or 4 good batteries among D, E, F, G, and H.

Now try the combination DE. In the worst case, this combination will fail. This means that there are 0 or 1 good batteries among D and E. Now we know that F, G, and H have at least 2 good batteries.

Try the combinations FG, GH, and FH. Since there are at least 2 good batteries among them, one of these combinations will work. In the worst case, it will be the last combination you try. Thus, it will take $\boxed{7}$ tries in the worst case to get the flashlight to turn on.

This proves that it can be done in 7 tries, but is it possible to do it in fewer tries? Consider that the given solution partitions the batteries into groups of 3, 2, and 3 (checked in that order). In the worst case, this requires $\binom{3}{2}+\binom{2}{2}+\binom{3}{2}=7$ checks. Now consider how else the batteries could be partitioned.

If one were to check all combinations of a group of 6, then we are guaranteed to turn the flashlight on at least once. However, this would take $\binom{6}{2}=15$ tries in the worst case. Likewise, checking all combinations out of a group of 5 would take $\binom{5}{2}=10$ tries, and it wouldn't even guarantee that we could turn the flashlight on!

If one were to check a group of 4, then this would require $\binom{4}{2}=6$ tries, and it would not guarantee that the flashlight would turn on. Since it would take at least 1 more try to turn the flashlight on, you wouldn't be able to beat the count of 7 in this way. Therefore, batteries should only be checked in groups of 3 or less.

A strategy of checking the batteries in groups of 2 doesn't give nearly enough information to deduce where the good batteries are. If you partition the batteries into 4 groups of 2, and check each group, in the worst case, all 4 tries will fail. Even though you know that there is 1 good battery in each pair, finding the combination of 2 good batteries within 4 batteries would take up to 4 more tries (and would be the same as checking a group of 4).

Thus, the optimal strategy would involve checking batteries in groups of 3. Now suppose you checked two groups of 3. In the worst case, none of the 6 tries would work. You would need 1 more try with the remaining group of two (and in this case, it would be guaranteed to work -- this is another solution). Likewise, checking groups of 2, 3, and 3 (in that order) is another solution (also requiring 7 tries in the worst case).

There's one more solution, but it too requires 7 tries in the worst case. You could check groups of 2, 2, and 3 (in any order). If all 5 of those tries fail, then the last remaining battery must be good. You'd have to check it against one of the groups of 2 (and this would require 2 more tries in the worst case. This is effectively the same as making a group of 3) Thus, the minimum number of tries needed is 7.

You might be thinking of a strategy that involves only checking some of the combinations out of a group. For example, how about a strategy of checking AB, BC, and CD (and ignoring the combinations of AC, AD, and BD)? In the worst case, these tries would all fail, and you would gather that the 4 batteries contain 0, 1, or 2 good batteries. This is no better than simply checking AB and CD! Furthermore, you cannot eliminate the possibility of there being 2 good batteries in the group until you check the remaining 3 combinations.

The proof that 6 tests do not suffice can be expressed as a graph theory problem.

Each battery is the vertex of a graph $G,$ and the tests are edges in the graph. We will suppose an arbitrary graph with 8 vertices (batteries) and 6 edges (tests).

We are going to attempt a "worst case coloring", in this case coloring dead batteries red. We want to prove we can always color the 4 dead vertices such that two working batteries (uncolored vertices) never get tested together, that is, there is no edge between them. In graph theory lingo, we want to find a vertex cover of size 4 or smaller; this is defined as a set of vertices such that each edge of the graph is incident to at least one vertex of the set. (We incidentally ignore unconnected vertices in all this, since they don't get tested.)

If the graph $G$ has a vertex of degree 3 or higher, color it red. The 3 (or more) edges from that vertex have been accounted for; take the remaining edges not incident to the already-red vertex and color one vertex of each, and we have our vertex cover. (Sample below.)

Otherwise, there will be two vertices of degree 2 that are not incident. (This is always true given 8 vertices and 6 edges -- if you don't see why, think pigeonhole principle .) Color each of those vertices, and then there will be 2 edges unaccounted for. Color one vertex of each of those edges, and we have our vertex cover. (Sample below.)

My solution is simple.

There are 2 pairs of good batteries and 2 pairs of bad batteries.

So for the flashlight to turn on, you must use 2 good batteries of four. For the flashlight NOT to turn on, you must use 2 bad batteries altogether. Not only that, but to combine one good battery with one bad battery.

So the combination of one good battery and one bad battery is at least four, assuming that you used all the batteries only once: 4 (1 good battery + 1 bad battery) = FAILED 2 (1 bad battery + 1 bad battery) = FAILED 1 (1 good battery + 1 good battery) = SUCCEED!

Split the batteries into two groups: (A, B, C, D) and (E, F, G, H). Try the following AB, AC, AD, BC, BD, CD (these are all the possible combinations of the first group). If one of these succeeds, you've found a pair, if neither does, any combination of E, F, G, H will succeed (since all four of the first set are dead, all of the remaining ones are good). Thus you have 7 tries max.

Form 4 groups of 2 batteries: G1, G2, G3, G4. Worst case scenario, all four groups fail => at least one dead battery from each group => there doesn't exist a group with fail-fail (and success-success, obviously) since fail-fail implies there exists at least one group of success-success by counting. Hence, WLOG, choose G1 and G2. Choose any A1 from G1 and test with both elements G2. Worst case, both fail if A1 is dead. Test B1 from G1 with A2, B2 from G2. Worst case, first trial fails because A2 is dead. Hence, B1 and B2 must work. Total trials = 7.

Minimum number of attempts assumes selecting all the bad batteries first

4C2 (selecting 2 batteries from the 4 dead ones) = 6 combinations.

Next one is sure to be 2 good ones so +1 more attempt

7 Combinations