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

 

Bag 1	Bag 2	Bag 2	Bag 2	Sum of weights
-1	-1	-1	-1	-4
-1	0	0	0	-1
-1	1	1	1	2

Bag 1	Bag 2	Bag 2	Bag 2	Sum of weights
0	-1	-1	-1	-3
0	0	0	0	0
0	1	1	1	3

Bag 1	Bag 2	Bag 2	Bag 2	Sum of weights
1	-1	-1	-1	-2
1	0	0	0	1
1	1	1	1	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] 

 

Bag1	Bag2	Bag2	Bag2	Bag3	Bag3	Bag3	Bag3	Bag3	Bag3	Bag3	Bag3	Bag3	Sum of weights
-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-13
-1	0	0	0	-1	-1	-1	-1	-1	-1	-1	-1	-1	-10
-1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-7
-1	-1	-1	-1	0	0	0	0	0	0	0	0	0	-4
-1	0	0	0	0	0	0	0	0	0	0	0	0	-1
-1	1	1	1	0	0	0	0	0	0	0	0	0	2
-1	-1	-1	-1	1	1	1	1	1	1	1	1	1	5
-1	0	0	0	1	1	1	1	1	1	1	1	1	8
-1	1	1	1	1	1	1	1	1	1	1	1	1	11
0	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-12
0	0	0	0	-1	-1	-1	-1	-1	-1	-1	-1	-1	-9
0	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-6
0	-1	-1	-1	0	0	0	0	0	0	0	0	0	-3
0	0	0	0	0	0	0	0	0	0	0	0	0	0
0	1	1	1	0	0	0	0	0	0	0	0	0	3
0	-1	-1	-1	1	1	1	1	1	1	1	1	1	6
0	0	0	0	1	1	1	1	1	1	1	1	1	9
0	1	1	1	1	1	1	1	1	1	1	1	1	12
1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-11
1	0	0	0	-1	-1	-1	-1	-1	-1	-1	-1	-1	-8
1	1	1	1	-1	-1	-1	-1	-1	-1	-1	-1	-1	-5
1	-1	-1	-1	0	0	0	0	0	0	0	0	0	-2
1	0	0	0	0	0	0	0	0	0	0	0	0	1
1	1	1	1	0	0	0	0	0	0	0	0	0	4
1	-1	-1	-1	1	1	1	1	1	1	1	1	1	7
1	0	0	0	1	1	1	1	1	1	1	1	1	10
1	1	1	1	1	1	1	1	1	1	1	1	1	13

 

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

 

So we will draw 3^3 balls from Bag4 and 3^4 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.