16
$\begingroup$

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?

$\endgroup$
11
  • 2
    $\begingroup$ Isn't the minimal number 1? You might get lucky. I think you are asking for the maximal number of times to test? $\endgroup$ – APrough Mar 24 at 11:53
  • 4
    $\begingroup$ @APrough It could be worded better, but it is asking for a strategy in which the worst case takes as few tests as possible. The minimum number of tests wih which you a guaranteed to find a working pair, however unlucky you are. $\endgroup$ – Jaap Scherphuis Mar 24 at 12:00
  • 1
    $\begingroup$ The power went out, you need your flashlight to find your flashlight and your batteries. This is a chicken-and-egg problem that has no solution. $\endgroup$ – xhienne Mar 24 at 23:11
  • 2
    $\begingroup$ One could use a rather unintuitive approach of bouncing the batteries. The bounce might not be a good measure for the total charge, but one would still be able to distinguish the discharged from the charged ones. Since it is dark, one would need to listen to the difference in bounce frequency. This way, a maximum of 5 tries (+ 1 known good choice) for the worst case of chosing a charged and subsequently four discharged ones would be required. But this is more of a loophole. $\endgroup$ – Christian Karcher Mar 25 at 8:31
  • 1
    $\begingroup$ @HemantAgarwal IIRC it was a TEDx YouTube video. I don't remember the setting or the narration, but the logic is the same. $\endgroup$ – dr_ Jun 9 at 18:12
20
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Interestingly that this puzzle is essentially the same as this (the linked one has 132 "batteries" instead of 8). So, probably, your answer should be correct. $\endgroup$ – trolley813 Mar 24 at 10:59
  • 1
    $\begingroup$ I immediately recognised this riddle as one that the TedEd youtube channel has posted, under the name The Giant Iron Riddle, so your answer is almost certainly correct... $\endgroup$ – TakingNotes Mar 24 at 11:10
  • 2
    $\begingroup$ You could see this as using only 6 tests, since if 6 tests fail you have determined a pair of working batteries as required. You don't need to test the final pair, though you would need to insert them to actually use the flashlight. $\endgroup$ – Jaap Scherphuis Mar 24 at 14:09
  • $\begingroup$ @JaapScherphuis Thanks, I've added that in. $\endgroup$ – hexomino Mar 24 at 14:42
9
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ How do you test the first battery three times and mark it bad? $\endgroup$ – Kevin Mar 24 at 20:02
  • $\begingroup$ I think I wasn't clear enough about what I meant. I'll tweak the wording. What I meant was: suppose you've got some pattern of testing that doesn't do more than 6 tries; then we can find a way to pick 4 good and 4 bad batteries in such a way that all those trials will fail. (Therefore we need more than 6.) And the first step in doing that is: if any battery is used >=3 times in that pattern of trials, make it a bad one. $\endgroup$ – Gareth McCaughan Mar 24 at 20:42
  • $\begingroup$ OK, I reworded it a bit. I hope it's less misleading now. $\endgroup$ – Gareth McCaughan Mar 24 at 20:45
  • $\begingroup$ What if the test depends on the previous result, is it possible that it invalidates the possibility of certain bad battery being tested in a specific configuration? $\endgroup$ – justhalf Mar 25 at 4:17
  • $\begingroup$ @justhalf There's only two possible test results, and for one of them, you succeeded and stop early. $\endgroup$ – Joseph Sible-Reinstate Monica Mar 25 at 4:22
4
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ This is equivalent to hexomino's answer, but in a different order matching the different argument that proves it works. Hexomino's groups correspond to ABG, CDH, and EF here. $\endgroup$ – Jaap Scherphuis Mar 25 at 5:19
2
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ Flaw: There may be one charged battery in the first three, and all three pairs will fail. $\endgroup$ – Daniel Mathias Mar 24 at 21:07
  • $\begingroup$ For a concrete setup that demonstrates the flaw, let the odd-numbered batteries be uncharged and the even-numbered batteries be charged. $\endgroup$ – Joseph Sible-Reinstate Monica Mar 25 at 5:13
1
$\begingroup$

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.

$\endgroup$
1
  • 4
    $\begingroup$ In this solution you can have 7 failing tests before you conclude that B and C are good. Hexomino's and Joseph's answers have at most 6 failing test before you deduce the working pair (they don't need to do a seventh test, apart from inserting them to actually use the flashlight). $\endgroup$ – Jaap Scherphuis Mar 25 at 12:30
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.