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.

Answer:

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.