Brain Teaser 28: Counterfeit Coins II
Hi, I’ve developed a keen interest in brain teasers lately and thought, why not share and discuss them here. These brain teasers could potentially be asked during interviews for quantitative-related roles. They are taken from the book ‘A Practical Guide to Quantitative Finance Interviews’ by Xinfeng Zhou. The problem that we’re gonna solve in this post is “Counterfeit Coins II”.
Problem:
There are 5 bags with 100 coins in each bag. A coin can weigh 9 grams, 10 grams or 11 grams. Each bag contains coins of equal weight, but we do not know what type of coins a bag contains. You have a digital scale (the kind that tells the exact weight).
Question: How many times do you need to use the scale to determine which type of coin each bag contains?
Hint: Start with a simpler problem. What if you have 2 bags of coins instead of 5, how many coins do you need from each bag to find the type of coins in either bag? What is the minimum difference in coin numbers? Then how about 3 bags?
Solution:
First of all, for simplicity, let’s change the weights of the three types of coins from 9, 10, 11 to -1, 0, 1.
If we have 1 bag of coin, we only need 1 coin and weigh it.
If we have 2 bags of coins, there are 3² = 9 possible outcomes. Let’s say we only take 1 coin from bag 1. We need to determine how many coins we need to take from bag 2. Let’s consider the different scenarios:
- We take 1 coin from bag 2. The sums will range from -2 to 2 (5 possible numbers). This is not enough to differentiate among the 9 possible outcomes.
- We take 2 coins from bag 2. The sums will range from -3 to 3 (7 possible numbers). This, again, is not enough to differentiate among the 9 possible outcomes.
- We take 3 coins from bag 3. The sums will range from -4 to 4 (9 possible numbers). This will be enough to differentiate among the 9 possible outcomes.
Thus, we need 1 coin from bag 1 and 3 coins from bag 2 to determine the type of coins in each bag.
Let’s consider the next case. If we have 3 bags of coins, there are 3³ = 27 possible outcomes. We need the sums to range from -13 to 13 to differentiate among the 9 possible outcomes. Let’s say we take out 1 coin from bag 1 and 3 coins from bag 2. This will cover the sums ranging from -4 to 4. Therefore, we need 13–4 = 9 coins from bag 3.
If we have 4 bags of coins, there are 3⁴ = 81 possible outcomes. We need the sums to range from -40 to 40 to differentiate among the 81 possible outcomes. Let’s say we take out 1 coin from bag 1, 3 coins from bag 2, and 9 coins from bag 3. This will cover the sums ranging from -13 to 13. We will need 40–13 = 27 coins from bag 4.
Now, we can start to observe a pattern:
- 1 bag: 1 coin (bag 1)
- 2 bags: 1 coin (bag 1), 3 coins (bag 2)
- 3 bags: 1 coin (bag 1), 3 coins (bag 2), 9 coins (bag 3)
- 4 bags: 1 coin (bag 1), 3 coins (bag 2), 9 coins (bag 3), 27 coins (bag 4)
If we have 5 bags of coins, we can guess that we will need 81 coins from bag 5. Let’s confirm this. If we have 5 bags of coins, there are 3⁵ = 243 possible outcomes. We need the sums to range from -121 to 121 to differentiate among the 243 possible outcomes. Let’s say we take out 1 coin from bag 1, 3 coins from bag 2, 9 coins from bag 3, and 27 coins from bag 4. This will cover the sums ranging from -40 to 40. We will need 121–40 = 81 coins from bag 5.
Therefore, we only need to use the scale once to determine the type of coins that each bag contains. For 5 bags, we weigh the following combination: 1 coin from bag 1, 3 coins from bag 2, 9 coins from bag 3, 27 coins from bag 4 and 81 coins from bag 5.
And that’s all for this brain teaser about counterfeit coins 📀. Any feedback or questions are welcome! Are you interested in more brain teasers 🧠? Check out the other problems in this series:
Thank you for reading! :)
