Flashlight and 6 batteries

Question

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.

Answer 1

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.)

Answer 2

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

Answer 3

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 additional 3 trials.

So in total we get

2+3+3 = 8 trials

Answer 4

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.