# Flashlight and 6 batteries

In front of you are 6 batteries and a flashlight. You know that 4 out of the 6 batteries are fully charged, and 2 out of the 6 batteries are empty, but you don't know which ones are charged and which are empty. The flashlight requires 3 fully charged batteries to turn on. You need to develop a method to light the flashlight. This method should minimize the number of trials in the worst-case scenario. Find such a method, show that it works, and demonstrate that it is minimal.

• Welcome to Puzzling, take our tour! Could you please provide proper attribution for this question? Commented Aug 11 at 14:01
• Related (but different) question: Flashlight and 8 batteries Commented Aug 11 at 14:05
• "The flashlight requires 3 fully charged batteries to turn on." — And the flashlight only holds 3 batteries? Or does it e.g. hold 4 batteries, and at least 3 of them must be fully charged? Commented Aug 12 at 19:56

This is a proof that the

6

from Jonathan Allan's answer is optimal.

Can you guarantee a win in 5?

First note that you may as well try a fixed list of battery triples, since at each point either you've won or you haven't learned anything further from the failures. And, it's a bit easier to think of each guess as 3 batteries to exclude, where you win if both defective batteries are among them. So, the question is, can you list 5 triples of letters A-F so that each pair of letters is contained in some triple (as a subset)?

There are $$\binom{6}{2} = 15$$ pairs of letters, and each of the 5 triples checks off $$\binom{3}{2} = 3$$ pairs, so at first it looks like this might just exactly work if there's no overlap.

But, if you look at a single letter, say A, there're five pairs including it (AB, AC, AD, AE, AF), and each triple checks off two, so the parity means you can't get each pair exactly once. (Thanks to @Lopsy for this nice observation.)

It is possible to light the flashlight in the wort case on the

sixth attempt

I have no proof of optimality (certainly possible by applying graph theoretic techniques, but I'm no expert there), but this feels like it must be...

Label the batteries 1-6 and line them from smallest on the left to largest on the right. The state (empty, $$0$$, or full, $$1$$) of our battery line is now one of $$\binom{6}{4} = 15$$ possibilities:

A = 001111 B = 011101 C = 101011 D = 110011 E = 111001
F = 010111 G = 011110 H = 101101 J = 110101 K = 111010
L = 011011 M = 100111 N = 101110 P = 110110 Q = 111100

Now try, in any order, these six selections:

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


Why does it work?

Every single battery, B, is in exactly three trials, and for each B the other two across its three trials are arranged such that if we knew B worked then either (a) one of the three trials would work, or (b) one of the other three trials works (without using B, which still works).

For example, for battery 2:

if all of these fail:

 1 2 4
2 3 4
2 5 6


we know that battery 4 is empty and that one of 5 and 6 are empty (since we "know" 2 is full), so 1 and 3 are full and one of the first two of the other three tests will work

 1 3 5 - either this
1 3 6 - or this
4 5 6 - this one is guaranteed to fail


Let's give it a go:

 possible states: A B C D E F G H J K L M N P Q

try 1 2 4
possible states: A B C D E F G H   K L M N

try 1 3 5
possible states: A B   D E F G H     L M

try 1 3 6
possible states: A B   D   F G       L M

try 2 3 4
possible states: A     D   F         L M
(If we get here without any light we now know that 5 and 6 are full.)

try: 2 5 6
possible states: A                     M
(If we get here without any light we now know that 4 is full too.)

try 4 5 6
possible states:<None>
(works in both A and M)


Putting the states here again for ease of comparison with the above:

A = 001111 B = 011101 C = 101011 D = 110011 E = 111001
F = 010111 G = 011110 H = 101101 J = 110101 K = 111010
L = 011011 M = 100111 N = 101110 P = 110110 Q = 111100
• It seems that your tables only have 15 (labeled A-Q except I and O) of the 20 possibilities. I did not check if that affects your solution. Commented Aug 11 at 22:24
• There are only 15, not 20, I've fixed the text up. Commented Aug 11 at 23:00
• Hi Jonathan, Your solution is correct, and it is minimal. Personally, I like to label the trials like this: 123, 124, 345, 346, 156, 256 It is equivalent to your solution, but I think it highlights the symmetries. Your proof that it works is also correct. Personally, I prefer this one: Among the pairs 12, 34, and 56, there must be one that has two good batteries. Suppose it’s 12 (without loss of generality). If the first two trials don’t work, then batteries 5 and 6 are good, and the last two will work. If you want, I can give you a proof that 6 trials are minimal. Congrat. Commented Aug 11 at 23:11

Don't know if it's minimal but here's my attempt.

Let's call the batteries A,B,C,D,E,F and group them in two groups.

Group 1: A,B,C
Group 2: D,E,F

Assuming the worst case:

Group 1: A,B,C → no light
Group 2: D,E,F→ no light

So 2 trials.

Now

We know that two fully charged batteries are in both groups. So you remove one from group 2 (let's say) D and replace it with A,B and C respectively.

A,E,F → no light
B,E,F → no light
C,E,F → no light.

So 3 trials.

Now you know D is fully charged so all you have to do is to replace D with A,B and C respectively.

D,B,C → no light.

A,D,C → no light

A,B,D → lights on.

So in total we get

2+3+3 = 8 trials

• Your solution works. But it is not minimal. Commented Aug 11 at 20:12
• Your CEF trial is uneeded - your first trials show that exactly one dud is in ABC, and exactly one in DEF. If AEF and BEF both fail, then EF must contain a dud, and D is safe. Unfortunately, this isn't enough to make it optimal.
– Sirv
Commented Aug 12 at 0:00

It takes:

6 tries

Example:

1. Take 123.

2. If it fails, there are 2 or 3 charged batteries in 456. To come closer to the goal, take 2 from the latter (like 145).

3. If it fails, there are 2 or 3 charged batteries in 236. Take 246 (a 6, with the others being unique to 456 and 236).

4. If it fails, there are 2 or 3 charged batteries in 135. We have now 456, 236 and 135, so 2 of 3, 5 and 6 are charged. The good batteries might be 2345, 1346, 2615. Take a subset of each. There were 3 insertions before, so it takes 6 in total.

Proof:

There are $$6*5*4/6 =20$$ potential trios and $$6*5/2=15$$ combinations in total. Only 4 trios will be valid. Each negative result rules out up to 3 combinations, which amounts to 4 trios, and fewer at times, so you can't have 4 eliminations or below.

• This doesn't work : Imagine that batteries #1 and #4 are empty. If I test (123) & (456), then (124) & (125) and finaly (345) & (346) I have tested 6 times using your algorithm, but in each group there is either #1 or #4, so every test failed Commented Aug 14 at 13:39
• 124 and 125 would fail, so that means 3 is charged. 2 out of 4, 5 and 6 are charged. If 345 fails, 6 is charged. One of 136 or 236 works. Commented Aug 14 at 14:00
• Edited to address the slightly different approach. Commented Aug 14 at 14:34
• Ok, I think the difference is that while you find 3 good batteries with 6 attemps, you did not turn on the flashlight until the 7 attemps (when you put batteries 136 in your exemple). Commented Aug 15 at 6:48
• I fail to see the problem. If you already know where at least 3 of the good batteries are, it stops being an "attempt". It's only an attempt if you don't know the outcome in advance. Do you mean it's not minimal? Commented Aug 15 at 6:53