A pack of 8 batteries is given, with 4 good batteries and 4 bad batteries. We need to take 2 good batteries for our device to work properly. How to calculate what is the smallest number of steps in which we are sure, that we have 2 good batteries? What is the best approach to take I we want to be left with two good batteries in our hand? Only way we can check if a pair is good or bad is to put it in the device. It either works (2 good batteries) or doesn’t work (1 good 1 bad or 2 bad)

EDIT: I've managed so far to find a solution, that we can do this with only 7 checks (where a check is putting two batteries to the device).

  • Divide 8 batteries into 4 pairs
  • Check each pair (4 checks total)
  • If none worked, all pairs are of type (0,1) or (1,0)
  • Take any two pairs, cross-check them (we already know the result of one possibility, so we're left with 3 other possibilities to check, i.e. 3 checks, 7 checks total)

But I am still wondering, If this can be done with 6 checks only? Can we apply graph theory here somehow?

  • 1
    $\begingroup$ If you take 6 batteries, you must have 2 good ones $\endgroup$ Apr 16 '19 at 5:56
  • 3
    $\begingroup$ Taking six batteries is the smallest number of steps, because you said you wanted to be sure. This is not a probability question, so I don't understand what's the point of mentioning Poisson. Probability would be relevant only if you would be happy with, say, 90 per cent change of having at least two good batteries. There is nothing to optimize here. $\endgroup$ Apr 16 '19 at 6:07
  • 3
    $\begingroup$ So what means are available for telling good batteries from bad? That's the important bit that you have left out of the question. E.g., if you can tell them apart on sight, then all you have to do it put the batteries on a table and pick out two good ones. $\endgroup$ Apr 16 '19 at 6:18
  • 1
    $\begingroup$ @paul that is very bad and not optimal approach, the closest I got to is 7 steps (7 checks): Divide 8 to 4 pairs, check pair 1, check pair 2, check pair 3, check pair 4. If none works, than all pairs are (0,1) or (1,0) pairs. Take any two pairs, cross check (3 checks, we know 1 of 4 possibilities already). 4+3=7 $\endgroup$
    – leller
    Apr 16 '19 at 7:24
  • 1
    $\begingroup$ @leller could you please edit your question and add what you have done so far? $\endgroup$
    – pH 74
    Apr 16 '19 at 7:43

A solution in six tests is given at quora: test pairs 1 & 2, 1 & 3, 2 & 3. If one of those works, you're done. If not, then at most one of those three batteries is good, which means three of the remaining batteries are good.

Test pairs 4 & 5, 4 & 6, 5 & 6. If one of those works, you're done. If not, then at most one of those three batteries is good, which means 7 & 8 are both good.


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