PuzzlersWorld.com

  • Hacker Puzzle
  • Interview Puzzles
  • Number Puzzles
  • Maths Puzzles

GPS and Battery Puzzle

(6 votes, average: 3.67 out of 5)

April 8, 2019 by Paul Bevan 3 Comments

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:-

Tried enough already?
Click here to See Solution
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.

  • Share on Whatsapp
  • Share on Facebook
  • Share on Twitter
Facebook Comments

Checkout more Interview Puzzles Tags: Solved Puzzles

Comments

  1. Heemanshu Kumar Sinha says

    June 2, 2021 at 10:13 am

    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.

    Reply
  2. GenRex says

    May 27, 2021 at 8:32 pm

    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.

    Reply
  3. Phil R says

    April 6, 2021 at 1:47 am

    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.

    Reply

Leave a Comment Cancel reply

Submit your Puzzle

You may also like

  • Palindrome dates
  • Cook the egg for 15 minutes puzzle
  • Four glasses on a square table
  • Bar with 25 seats
  • 100 doors
  • Defective ball
  • River crossing: she-goat, wolf and cabbage
  • Wires on fire
  • Find 3 Fastest horses from 25 horses
  • Balls in a bag

Categories

  • Aive hi Puzzles
  • Akbar and Birbal
  • Alphabetical Puzzles
  • Bollywood Puzzles
  • Google Code jam
  • Hindi Riddles
  • Interview Puzzles
  • Interview Questions
  • Logical Puzzles
  • Malayalam Puzzles
  • Maths Puzzles
  • Miscellaneous
  • Number Puzzles
  • Picture Puzzles
  • Riddles
  • Tamil Puzzles
  • Technical

Social

  • View puzzlersworld’s profile on Twitter
privacy policy

Copyright © 2023 · eleven40 Pro Theme on Genesis Framework · WordPress · Log in

  • Hacker Puzzle
  • Logo Puzzles
  • Optical Illusions
  • WhatsApp Puzzles
  • Picture Puzzles
  • Riddles
    ▼
    • Hindi Riddles
  • Bollywood Puzzles
  • Alphabetical Puzzles
  • Aive hi Puzzles
  • Interview Puzzles
  • Logical Puzzles
  • Interview Questions
    ▼
    • Data Structures
    • Binary Tree
    • Algorithms
    • Recursion Questions
    • Amazon Interview Questions
    • Snapdeal Interview Questions
    • Google Code jam
  • Technical
  • Akbar and Birbal
  • Number Puzzles
  • Maths Puzzles
  • Miscellaneous