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?