Counterfeit Coin problem

[tuanl]

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(

 

[amanda.jayne]

http://lmgtfy.com/?q=balance+puzzle

See the first link.

Start with 27 * 3 instead of 12 * 3.

If you are studying for an interview, I would suggest consulting the master reading list books for quant interviews.

Heard on The Street: Quantitative Questions from Wall Street Job Interviews by Timothy Crack

and

Quant Job Interview Questions And Answers

both contain detailed solutions in the back.

 

[IlyaKEightSix]

Left/right/off

27/27/27
9/9/9
3/3/3
1/1/1

4 uses.

 

[tuanl]

Left/right/off

27/27/27
9/9/9
3/3/3
1/1/1

4 uses.

Nice split! But on the 4th weighing, how do we determine which coin is counterfeit, since we don't know if the counterfeit is heavier or lighter than the other coins?

PS: Nevermind. I finally got it!

 

[pruse]

4 is most certainly wrong. You can do it in 4 only if you know that the counterfeit coin is, say, heavier.

 

[tuanl]

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.

 

[pruse]

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.

 

[tuanl]

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?

 

[tuanl]

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.

 

[pruse]

Yes, it's 5. Now prove that it can't be done in 4...

 

[tuanl]

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