• C++ Programming for Financial Engineering
    Highly recommended by thousands of MFE students. Covers essential C++ topics with applications to financial engineering. Learn more Join!
    Python for Finance with Intro to Data Science
    Gain practical understanding of Python to read, understand, and write professional Python code for your first day on the job. Learn more Join!
    An Intuition-Based Options Primer for FE
    Ideal for entry level positions interviews and graduate studies, specializing in options trading arbitrage and options valuation models. Learn more Join!

Counterfeit Coin problem

Out of 81 coins, there is one counterfeit. What is the minimum number of weighings to find out counterfeit coin.

PS: I googled this problem online and saw various answers, mostly between 4 and 5. But I myself haven't been able to figure out which one is correct:((
 
4 is most certainly wrong. You can do it in 4 only if you know that the counterfeit coin is, say, heavier.
 
4 is most certainly wrong. You can do it in 4 only if you know that the counterfeit coin is, say, heavier.

Did you try reading the link given by Amanda.Jayne above? It contains the solution to the case of 12 coins, one of which is counterfeit. They solved it in 3 steps.
 
Did you try reading the link given by Amanda.Jayne above? It contains the solution to the case of 12 coins, one of which is counterfeit. They solved it in 3 steps.

Yeah, I'm aware of the 12 coin problem. But your problem is 81 coins.
 
I think the minimum number of weighings needed is (7). But I haven't been able to show that (6) is not possible. My current question is: if you have 81 coins and you know that the counterfeit coin must be in a particular set of 24 coins in 3 weighings, can you find out that counterfeit coin in only 3 more weighings?
 
Nevermind about my post above. After seeing a similar problem from "Heard on the street" book (problem 1.14), I'm sure that the minimum number of weighings needed is (5).

The key insight is to divide 81 into 3 piles of 27 and we need a minimum of 2 weighings to see which pile(out of these 3) contains a counterfeit coin and determne whether that coin is heavier or lighter than the other coins. Finally, we use the lemma: Out of 27 coins, one of them is counterfeit and we know it's lighter(or heavier) than the other coins, the minimum of weighings to determine the counterfeit coin is 3.
 
According to the same book, if we have 81 coins, one of which is counterfeit and we know it's heavier(or lighter) than the remaining one, then the minimum number of weighings is (4).

Thus, in our problem, we need at least one more weighing to determine whether the counterfeit is heavier(or lighter). We actually need 2 weighing to do this in our case, but we're lucky enough to only need 3 more weighings due to the division of 81 into piles of 27 coins. Therefore, 4 is not possible
 
Top