You have four good/new batteries and four bad/used batteries but don’t know which are which. You have a flashlight that uses two batteries, which will only work if both batteries are good – if it doesn’t work, you won’t know if both batteries are bad or just one.
How many pairs of batteries do you need to test to guarantee you find a good pair?
There are a couple of ways to set this up, but here is one possible solution:
- Number the batteries 1 through 8
- Test 1+2, 1+3, and 2+3. These can only all fail if 1 through 3 contain two bad batteries.
- Test 4+5, 4+6, and 5+6. These can only all fail if 4 through 6 contain two bad batteries.
- If all of those tests failed, 1 through 6 must have contained all four bad batteries, so 7+8 must be a good pair.
To prove that 7 tests is the lowest possible number requires applying some graph theory and is beyond the scope of our site. If you are interested, check out this Reddit thread for some explanations.