# 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(

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

Replies
6
Views
999
Replies
2
Views
1K
Replies
5
Views
2K
Replies
2
Views
1K
Replies
2
Views
637