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.

--

--

--

IIM Bangalore | Writing about Machine Learning & Quantitative finance.

Love podcasts or audiobooks? Learn on the go with our new app.

Statistical Power in Hypothesis Testing

Quantum Randomness and Schrodeniger’s Cat in Metaverse

Miracles of number 1.618 (Part 1)

Polkadot Big Picture (May 2022)

Data Science Pioneers: Khwarizmi

Calculating pi using the Archimedes’ method

Playing infinite chess — 3:16

A Guide to Metrics in Exploratory Data Analysis

A wordcloud of metrics/estimates/sample statistics explained in this article.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Priyanka Dalmia

Priyanka Dalmia

IIM Bangalore | Writing about Machine Learning & Quantitative finance.

More from Medium

Which challenges recruiters are facing in hiring good software engineers

Diana Blaschke Interview

How I landed my Target SWE Internship — A Year in Advance

Ingenious way to do X-Ray Sourcing