Determine Weight of Counterfeit coins [Asked in GS Interview]

Question:

There are 5 bags with 100 balls in each bag. A ball can weigh 9 grams, 10 grams or 11 grams. Each bag contains balls of equal weight, but we do not know what type of ball a bag contains. Cookie has a digital scale (the kind that tells the exact weight). How many times does she need to use the scale to determine which type of ball each bag contains?

Solution:

Step 1: Cookie marks 9 grams ball as — 1, 10 grams as 0 and 11 grams as +1 and bags as Bag1, Bag2 ... Bag5

Now let us start with a simple version of this problem:

When no of bags = 1 i.e. we only have Bag1

We need to weigh only one of the balls from Bag1 to determine the type of ball present in Bag1

When no of bags = 2

If we pick 1 ball marked 0 from Bag1 and another ball marked as 0 from Bag2 the sum is 0

Similarly, if Bag1 contains 1 ball marked -1 and Bag2 contains another ball marked as 1 then also sum is 0

So by taking only 1 ball from Bag1 and Bag2 each it will not be possible to determine the weight.

If we pick 1 ball marked -1 from Bag1 and 2 balls from Bag2 both marked as 0 the sum of weights is –1

Similarly, if we pick 1 ball marked 1 from Bag1 and 2 balls from Bag2 both marked as -1 then also the sum of weights is -1

So by taking only 1 ball from Bag1 and 2 balls from Bag2 it will not be possible to determine the weight.

But we take 1 ball from Bag1 and 3 balls from Bag2 the weight combinations we can have are in the range [-4,4]:

Now Cookie extends this to when no of bags = 3

We will have 27 such combinations and we will require 9 coins from Bag3 to get weights in the range [-13,13]

So a clear pattern emerges — 1 ball from Bag1, 3 balls from Bag2, 9(3²) balls from Bag3 and so on.

So we will draw 3³ balls from Bag4 and 3⁴ balls from Bag5.

Final Solution: Cookie will withdraw 1, 3, 9, 27 and 81 balls from bags 1,2,3,4 and 5 respectively, to determine which type of balls each bag contains using a single weighing machine.