Counterfeit Coin

Logic Level 5

You have been given a certain number of coins that all look identical. All are made out of gold and weigh the same except for one counterfeit which weighs differently than all the rest. Your task is to pick out the counterfeit by weighing different coins against each other using a balance scale. You are only allowed three weighings on the balance scale and you don't know whether the counterfeit coin is lighter or heavier than the rest.

What is the maximum possible number of coins for which you are guaranteed to be able to find the counterfeit?

7 8 9 10 11 12 13 14

1 solution

John Ross
Jun 8, 2018

It is possible to find the counterfeit among 13 coins. For the first weighing, weigh 4 coins against another 4 coins, leaving 5 coins off the balance. Case 1: The balance is level. This means that the counterfeit is among the remaining 5 coins. Weigh 3 of these coins against 3 coins that you know are genuine. Case 1a: The balance is level. This means that the counterfeit is among the remaining 2 coins. Weigh one of these against a genuine coin. If the balance tips, you know it was that coin; if it levels, then it was the other coin. Case 1b: the balance tips toward or away from the 3 possibly counterfeit coins. We now know whether the counterfeit is lighter or heavier than the rest. Weigh 2 of these coins against each other to see wihich is heavier (or if it levels in which case the coin left off the balance is counterfeit). Case 2: The balance tips. We can now label the coins H1,H2,H3,H4 and L1,L2,L3,L4 and G1,G2,G3,G4,G5 for possibly heavy, possibly light, and definitely genuine. Now weigh H1,H2,H3,L1 on the left against H4,G1,G2,G3 on the right. Case 2a: The balance levels. This means that the counterfeit is either L2, L3, or L4 and we can weigh two of them against each other to determine which one is the lightest. Case 2b: The left side is heavier. This means that the counterfeit is either H1, H2, or H3 and we can weigh two of them against each other to determine which one is the heaviest. Case 2c: The right side is heavier. This means that the counterfeit either L1 or H4. Weighing L1 against a genuine coin will tell us which is the case.

We can prove that 13 is optimal. The only way to get any higher would be to (1) weigh 5 coins against 5 coins in the beginning or (2) leave 6 coins off. (1) If we weighed 5 against 5, and the balance tipped, then we would have 2 weighs to find 1 coin out of 10. This is impossible because with 2 weighings with 3 possible outcomes each, the maximum possible total outcomes would be 9, making it impossible to discriminate 1 out of 10. (2) If we have 6 coins and 2 weighings left, we can only afford to leave 2 coins off the balance for our second weighing. If we left 3 off and the balance leveled, then we would have 1 weighing to determine which of the 3 was different from the others which is impossible. This means that there would be 4 coins on the balance for the second weighing, possibly with some extra genuine coins. No matter how we do this it would not eliminate any of the 4 coins from being possibly counterfeit, so we would be left to discriminate 1 coin out of 4 which is impossible with 1 weighing.

Why can't we have like this, I take 14 coins initially, then I place 7 , 7 coins on each side. The one with higher weight has the wrong coin. Now I take those 7 coins, split them into 3,3,1. I place 3,3 on both sides, if they are equal we know that the 1 is the wrong coin but if someone from that 3 weighs more, then we place 1,1 out of 3 onto balance and you can calculate the rest. What do you think, let me know.

Kavit Mehta - 2 years, 12 months ago

You don't know whether the counterfeit coin is lighter or heavier than the rest.

John Ross - 2 years, 12 months ago

@John Ross can you throw some light on the inspiration for this solution....I mean what if we were allowed 4 maximum balances....what would be the approach then . Why did you decided to weigh 4vs4 first . Why not any other combinations? I basically request you to please share your thought process that led you to this algorithm . Thanks .

space sizzlers - 2 years, 9 months ago

Really the best thing to do for this problem is trial and error. The second paragraph in my solution sort of describes how I found the correct number. We know that for the first weighing we need to weigh a against a and leave b off. Then we just need to maximize a and b through trial and error. According to Wikipedia the maximum number of coins for n weighs is $\dfrac{3^n-1}{2}$

John Ross - 2 years, 9 months ago

I have an Idea if we are only allowed n-times to weighing on the balance scale , how about you have 4 boxes, box A with 3^(n-2) coin, box B with 3^(n-2) coin, C with 3^(n-2) coin, and D with 1 coin. Then at the first I compare box a and b, and then at the second time I compare box a and c. From this step, if coins in box a = box b = box c, then the counterfeit coin is in box D. Else : one of the three boxes is the lightest or the heaviest box, and we know the counterfeit coin is lighter or weighter.

After we know the counterfeit coin is lighter or weighter, we can use this algorithm:

WLOG, box A is the heaviest. With the same method, I have 3 boxes, box A with 3^(n-3) coins, box B with 3^(n-3) coins, and C with 3^(n-3) coins.

(i) If box A > B, the counterfeit coin is on box A. (ii) If box A < B, the counterfeit coin is on box B. (iii) If box A = B, the counterfeit coin is on box C.

Terza Reyhan - 2 years ago

i can do 27 coins. first take 2 piles of 9 coins. if they balance then its the remaining pile. Do same with 3 and 1. But if they dont balance then use the different pile.

Luca Ng - 11 months ago

Counterfeit Coin

1 solution

0 pending reports