Friday Puzzler--Eight Batteries

Re: Friday Puzzler--Eight Batteries

Larry Barrett

Start with #1. Assume it is good. So try 2; if no light try then 3; if no light then try 4; if no light then try 5; if no light then try 6. If 1 was good then 2, 3, 4, and 5 must be bad and 6, 7, 8 good. If still no light after 6 then 1 must be bad and you know nothing about the rest. Set 1 aside and repeat starting with 2.

Starting with 1 it took 5 trials to either find two good ones or prove 1 was bad.

If 1 bad it will take 4 trials to find two that are good or prove 2 is bad.

So minimum number of trials is 5+4+3+2=14 trials to be sure that you find two good ones.

Suboptimal

Alex Y

That strategy will indeed find a good pair, but there are faster strategies.

Re: Friday Puzzler--Eight Batteries

Ed in Leaside

Worse case 7 tries

Correct!

Alex Y

Great thinking outside the box. Best I could get was 8 tries:

1-2

3-4

5-6

7-8

1-3

1-4

2-3

2-4

Re: Correct!

Ed in Leaside

1-2

3-4

5-6

7-8

1-3

1-4

2-3

2-4

If the first 4 tests are dud: then each pair has a good & dead battery.

If the nexi 3 tests are dud: then no need to test 2-4, they are good.

Not quite optimal

Alex Y

Ed, I agree that after seven tries, you will be able to identify two good batteries. But the question was how many pairs you have to put in the flashlight to be assured of getting it to work, requiring 2 and 4 to be put in, the eighth pair.

But there is a way to do it (whether the question is identifying a good pair or having a good pair in the flashlight) with fewer than 7 or 8 pairs.

Hint

Alex Y

The key here is to find the most efficient way to get info by testing subsets of the eight batteries. For instance, in the (sub-optimal) solution shown before, the batteries were separated into 4 pairs, and testing the pairs told us that each pair had one good battery, and from there, it was just three more tests before knowing that we will light the flashlight with the eighth pair we install.

Another way to get a good pair installed no later than the 8th pair (and identified after the 7th failed test) is to divide the batteries into two groups of 4. Test the 6 pairings of 1-4, and if those do not light the flashlight, you know there is at most one good battery in 1-4, so at least 3 good batteries in 5-8. Pick any pair of 5-8, and if it fails, the other two batteries will light the flashlight.

But there is a grouping that will assure that you can light the flashlight with the seventh pair you try.

Re: Hint

Larry Barrett

How about 3, 3, and 2?

Test 1-2, 1-3, 2-3. If flashlight does not work then at most one of them is good. Next try 4-5, 4-6, 5-6. If flashlight does not work, then at most one of these is good. So you know that 7 and 8 are good and will work in the flashlight.

Correct!

Alex Y

At worst, flashlight will turn in for the 7th pair.