(6 votes, average: 3.67 out of 5)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.
Check your answer:-
Click here to See SolutionLet’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.
10 tials:
Divide into groups of 3 and 5.
Check first group:
it can have any of 4 scenarios: All 3 working, Two working, All 3 non-working, One working
In first case only one trial is needed.
In second case three trials may be required to get a successful result.
In third and fourth cases, we’ll not get a result after three trials. but will be able to conclude that second group has minimum 3 working batteries.
Now test second group:
Assume first battery is dead, we’ll know after 4 tries. Discard this battery.
Take second battery, if this too is dead then we’ll know after three tries with remaining batteries.
If first two batteries are dead then last three have to be working as per conclusion from first group.
Hence no further trials needed.
Thus maximum trials required to guarantee success: 3( from first group)+ (4+3)(from second group)= 10 trials.
It can be done in 8 pair.Make 4 slots – 2 in each, try all 4 pairs. Best case – we get a working pair. Worst case – none of the pairs work. That means every pair has 1 working battery. So try all the 4 possible configurations of 4 batteries in the first two slots, we’ll surely get a working pair.
Six tests are sufficient — meaning seven to actually get the GPS device to operate, or six to identify a pair of batteries that you know will work. Numbering the batteries 1..8, try, in order, the pairs {1,2}, {1,3}, {2,3}, {4,5}, {4,6}, {5,6}, {7,8}. At least one of these must work. Why? In graph-theoretic terms, think of a graph whose eight vertices represent the eight different batteries and whose edges represent trying out that pair in the GPS device. Then we are considering the 8-vertex graph with two disjoint triangles, {1,2,3} and {4,5,6}, and a separate edge, {7,8}. It is easy to see that every four-element subset of vertices is guaranteed to contain an edge.