Flashlight and 8 batteries

Question

A flashlight requires 2 AA-type batteries to operate. Both these batteries need to be charged for the flashlight to provide light.

We happen to have 8 batteries, but 4 of them are charged while the other 4 are discharged/unusable, and they look all the same. So we would have to test them two at a time inside the flashlight.

The power went out in our home, and we need to have some light fast. What is the minimum number of tests which guarantees us to find a working pair, however unlucky we may be?

Answer 1

Not sure if minimal, but here is a way to do it in

7 tries

Method

Divide the 8 batteries into three groups - two groups with 3 batteries each and the remaining group with 2 batteries. By the Pigeonhole Principle, at least one of these groups will contain at least 2 fully charged batteries.

This means that if we test every combination within each group, at least one combination is guaranteed to work. In the groups of 3, there are $\binom{3}{2} = 3$ combinations to test while in the group of 2 there is just $\binom{2}{2} = 1$ so overall we have, at most, $3+3+1=7$ tests to make.

Also, as Jaap Scherphuis points out in the comments

You actually need to do just 6 tests since the last "test" is guaranteed to have two working batteries.

Answer 2

Here is a proof that hexomino's answer of

7 tries

is best possible.

Suppose we have any set of at most 6 trials. I claim there's a way to pick 4 of the batteries to be good and the rest to be bad, such that all those <=6 trials fail. (Therefore, we can't in fact solve the problem in <= 6 trials, so we need >=7, so hexomino's solution is optimal.)

Here's how.

If we try any battery 3 or more times, mark that one bad, and then pick one battery from each of the <=3 trials that don't use that battery and mark it bad. We have now marked at most four batteries bad. Any pattern of goodness-or-badness that makes those batteries bad will make all six of our trials fail, so this set of trials is no good.

The alternative is

that we don't try any battery more than twice. Imagine joining pairs of batteries together with string when they are part of a single trial; we never have more than two strings from a single battery, which means that they fall into chains and loops (and isolated batteries, which we can consider to be length-1 chains). Now assign goodness and badness as follows. Along each chain, let the battery at one end be good and then alternate good and bad. This forces all the trials in that chain to fail. Around each loop, pick one battery to be bad and again alternate; in this case we may end up with two adjacent bad batteries if the loop is of odd size. Again, this forces all the trials in that loop to fail. Now, at least half the batteries in each chain or even-length loop are good. In an odd-length loop, we need (n+1)/2 bad batteries rather than n/2. So the total number of bad batteries needed to make all these trials fail is at most half the number of trials plus half the number of odd loops. With 6 trials, this means we need at least two odd loops. There's only one way to do that: 3+3. Those odd loops do indeed need 4 bad batteries between them -- but then we can assign the other two batteries to both be good, making all the trials fail with only 4 bad batteries. Conclusion: any set of 6 trials allows us to pick at most 4 bad batteries that suffice to make all the trials fail.

(This can be expressed more concisely using the language of graph theory, but it seemed better not to.)

Answer 3

Here's an alternative solution to get the flashlight working in at most

7 tries:

I'll call the batteries A-H. First, test these pairs:

AB, CD, and EF. Since every failed test requires at least one bad battery, and we didn't repeat any batteries yet, if none of those worked, then we've tested at least three bad batteries. This means that there's at most one untested bad battery, so G and H can't both be bad.

That leaves us with 3 cases. Case 1:

G and H are both good.

Case 2:

G is good and H is bad.

Case 3:

G is bad and H is good.

Next, test these pairs:

AG, BG, CH, and DH.

If we're in case 1, then at least one of those must work because

with G and H both good, they could only all fail if A, B, C, and D were all bad. This wouldn't leave any remaining bad batteries, which is impossible since EF failed earlier.

If we're in case 2, then at least one of those must work because

with G good, AG and BG could only both fail if A and B were both bad. H also being bad would leave only one bad battery among CDEF, which is impossible since CD and EF both failed earlier.

If we're in case 3, then at least one of those must work because

with H good, CH and DH could only both fail if C and D were both bad. G also being bad would leave only one bad battery among ABEF, which is impossible since AB and EF both failed earlier.

Answer 4

The following should demonstrate that six tests (7 "tries") is optimal.

To show n out of n+1 batteries are dead,

all pairings of the n+1 batteries must be tested. For n >= 1, we have n(n+1)/2 pairings.

Thus:

1 test is required to show that 1 of 2 batteries is dead

3 tests are required to show that 2 of 3 batteries are dead

6 tests are required to show that 3 of 4 batteries are dead

And at 6 tests, this matches hexomino's solution without guaranteeing a working pair, so we can ignore this and the possibility of marking 4 in 5 as dead for the purposes of optimization.

Recall we're optimizing for the worst luck, so we consider that we won't find a working set of batteries until we definitively identify/eliminate the dead ones. This also means that eliminating batteries we don't know are dead is the same as eliminating live batteries.

This makes our goal:

1. eliminating four batteries as dead

while

2. keeping 2 other batteries not eliminated (which then must be live)

Some notes on brute-forcing:

For any group of n >= 3 batteries containing at least 1 dead battery and k >= 2 live batteries, the worst case requires we execute n(n-1)/2 - k(k-1)/2 failed tests in order to identify all of the dead batteries (and hence the live ones).

As a corrollary, we can't identify individual live/dead batteries in a group if

we don't know that at least two are live, so brute-forcing a group isn't an option without at least two live batteries.

So, for example, take a group of 2 live batteries and 2 dead batteries.

If these are the only batteries we haven't eliminated, we must brute-force the group in order to identify both live ones, which takes 5 tests (suboptimal per hexomino's solution; 1 test alone can't identify a group of 2 live and 2 dead batteries), making the 2-live, 2-dead subproblem part of only non-optimal solutions.

We arrive at this subproblem by

running two tests to eliminate one dead and one live battery each,

so the optimal solution eliminates

one or fewer sets of 1 live, 1 dead.

Only 2 other scenarios remain:

If we eliminate one such set, we are left with 3 live, 3 dead after 1 test; brute-forcing from here is suboptimal, so we use 3 tests to eliminate 2 dead, 1 live to arrive at 1 dead, 2 live, which must be brute-forced and requires 2 more tests.

(total 6 tests)

If we don't eliminate any 1-live, 1-dead sets, our only option is using 3 tests twice, each time eliminating 2 dead, 1 live, to arrive at 2 live, which requires no further tests.

(this is hexomino's solution, which also requires 6 tests)

Answer 5

I came up with

5 tries

Though perhaps there is a flaw in the logic. Found the flaw in my first step. If all three combinations don't work, this means that at least two are uncharged, not all three.

First

3 tries - pick 3 batteries and try each of the 3 combinations (1-2, 2-3, 1-3). Worst case all three combinations fail and all 3 batteries are uncharged, meaning only one of the remaining 5 batteries is uncharged.

Next

4th try - pick 2 batteries from the remaining 5 (4-5). This either works (both charged) or doesn't (one uncharged). If it doesn't work, you know all remaining batteries are charged.

Last

5th try - pick any two remaining batteries (6-7).

Answer 6

A variant of @JosephSible-ReinstateMonica's answer, which I found independently and whose explanation is a bit more clear to me.

You can do it in

7 trials

First of all, name the batteries A-H, then

try AB, CD, EF and GH (4 tests). If one test succeeds, you stop and use those batteries.

Otherwise

that means that every pair of batteries contains one good battery and one bad battery. So let's find the two good batteries among A, B, C and D, which can be done in three tests. Test AC and BD (2 more tests). If both test fails that means that you paired the bad battery from AB with the good battery from CD and vice versa. In this case test AD (last test) if this works, use AD. Otherwise it means that A and D were the two bad batteries, so the two good batteries must be BC.

Answer 7

This is another way of wording the solution:

Divide the 8 batteries in three groups, ABC, DEF, and GH.

Test the first group: AB (1), AC (2), BC (3). If we found a working pair, good! Otherwise continue.

Test the second group: DE (4), DF (5), EF (6). If we found a working pair, good! Otherwise, the only possibility left is that there was only one charged battery in the first group and only one charged battery in the second group. Therefore the other two charged batteries must be G and H, and at the GH (7) test our flashlight will gloriously shine a beam of light.

Therefore you are guaranteed to find a working pair of batteries in 7 tries maximum.