You have a GPS that takes 2 working batteries. You have 8 batteries but only 4 of them work.
What is the fewest number of pairs you need to test to guarantee you can get the GPS on.
GPS will work when both the batteries are working, it will not work if any of the battery is faulty.
Let’s if we take 2 pairs of batteries and put them in slot 1 and slot 2, test them out, if working fine, else take another two and test them out and so on..
if we are lucky in these 4 turns, GPS device will work, but let’s say we were most unlucky and it did not work all the 4 times.
Now lets group the batteries in two group of 4 (slot 1 and slot 2)
There can be these cases in group of 4
All 4 batteries are working -> take any pair and we will get working battery in just 1 chance
Only 3 batteries are working -> we will get working batteries in max 2 picks
Only, 2 batteries are working -> this is a tricky one
let’s say we pick 2 batteries(1) and it didn’t work, we check other two batteries(2) and that didn’t work too (we are most unlucky).
so, we know that both pairs have one faulty and one working batteries.
Set 1: F1, W1
Set 2: F2 W2
now, let’s say we again pick one battery from first pair and another battery from another pair(3) and it did not work too.
posible cases: F1F2, F1W2, W1F2
if it was F1F2 the other pair should work (i.e. one more try) (4).
but, if it was F1W2 or W1F2 => if we pick one battery from set 1 (which we picked earlier) and another battery from Set2 (which we did not pick)(5). it can either be F1F2 (for the case of F1W2) OR W1W2 (for the case of W1F2).
if it was W1W2 -> it should have worked, but as we are most unlucky and it was F1F2, another try using other two batteries should work for sure(6).
thus total max tries in this case= 6
Actually we did not get any gain by doing all this, 6 is actually worst case in this case, i.e. try every possible pair(4C2)
Only 1 battery is working -> if it does not work in 6 chances, we know other 4 batteries are either all 3 OR all 4 working case, and we know we can solve that in max 2 picks.
Zero working batteries-> if it does not work in 6 chances, we know other 4 batteries are either all 3 OR all 4 working case and we know we can solve that in max 2 picks.
thus we know we can get working battery pair in 4 +6 + 2 => 12 chances.