1 Fake Coin among N Amount of coins

Question

You are given $N$ coins which consists of only $1$ fake coin. You also have a sensitive old-fashioned Pan Balance Scale.

You are asked to find the fake coin in totally 5 times weighing on the Pan Balance Scale among given $N$ coins ($N>2$):

You know that all genuine coins have the same weight but you do not
know their weights. 
You also know that the fake coin is different than genuine coins.

So, what is the maximum amount of coins ($N$) you can have which guarantees to find the fake coin in optimally at most $5$ tries on the pan in the worst possible case?

user3294068 · Accepted Answer

An algorithm for reaching Ivo's answer:

First note that for 121 coins, there are 242 possibilities.  This is slightly less than $3^5 = 243$.

If you weigh 41 coins on each scale, and it tips left or right, then you have narrowed the fake coin down to one of the 82 coins you weighed.  Since $82 > 3^4$, you cannot determine which is the fake coin in only four more weighings.  Thus, you can weigh at most 40 coins on each scale in the first weighing.  If you leave 41 coins out, then there are 82 remaining possibilities and that is more than you can fully distinguish in 4 weighings.  But you can determine the fake.  You don't have to distinguish all 82 states; you only need to distinguish the fake coin.

Step 1: weigh 40 coins vs 40 coins.

If this balances, then those 80 coins are all good.  Next weigh 27 of the 41 remaining coins against 27 of the good ones.  If that balances, weigh 9 of the remaining 14 against 9 of the good ones.  If that balances, weigh 3 of the remaining 5 against 3 of the good ones.  If that balances, weigh 1 of the remaining 2 against 1 good one.  If that balances, you know the last coin is fake, but you don't know whether it is heavy or light.

If any weighing after the first is not balanced, then you have narrowed the fake down to one of $3^n$ coins, and you know if it is heavy or light, and you have $n$ weighings remaining.  From there, continually divide $1/3$ of that group against another $1/3$ to narrow it down to the fake coin.

If the first weighing did not balance, then you have narrowed it down to either one of he coins on the heavy pan is heavy or one of the others is light.  80 possibilities.  From here, you need to narrow the possibilities down by factors of 3.

Label the potentially heavy coins as H, and the potentially light coins as L.  The good coins (known not to be fake ) are G.

Second weighing: weigh 14H + 14L on pan A, versus 13H + 13L + 2G on pan B.  If pan A is heavy, then one of the 14H on pan A or 13L on pan B is the fake.  If pan B is heavy, then one of the 14L on pan A or 13H on pan B is heavy.  If the pans balance, then one of the other 13H or 13L is the fake.  In any case, you have narrowed the possibilities 26 or 27 coins, half heavy and half light (with up to 1 extra in one group).

Third weighing: weigh 5H + 5L on pan A versus 4H + 4L + 2G on pan B.  This will narrow the possibilities down to one of 8 or 9 coins, half heavy and half light.

Fourth weighing: weigh 2H + 2L on pan A versus 1H + 1L + 2G on pan B.  This narrows down the possibilities to one of 2 or 3 coins, half heavy and half light.

Fifth weighing: weigh 1H + 1L on pan A versus 2G on pan B. If the pans do not balance, you know which is fake.  If they do balance, then the remaining coin is fake.

stack reader · Answer

Karan Atree · Answer

Total coins

Explanation:-

Steps one and two

Step three

Step four

Step five

Ivo Beckers · Answer

The answer is

It surprised me a little bit, I expected it to be lower. I don't know the exact steps but it has been proven according to this that you can determine a bad coin in $n$ steps for a maximum of

coins.

Mike Earnest · Answer

A naive upper bound is N = 243 = 35, since you must distinguish among N possibilities using 5 ternary tests. However, you can prove a better bound.

Here is a proof that the maximum possible value of $N$ is

There are 35 = 243 possible outcomes of the five weighings, which can be represented as a string of 5 letters, each of which is L, R or B, for left heavy, right heavy, or balanced. The outcome you see is determined by which coin is fake, its weight, and which scales it was put on. For example, if coin 7 was heavy, and it was placed on the right for weighings 1 and 2, on the left for 3 and 4, and not weighed during the 5th, you would observe the outcome LLRRB. On the other hand, if coin 7 was light, you would observe the opposite outcome where L and R are interchanged, RRLLB.

This illustrates the fact that if an outcome causes you to conclude a coin is fake, its opposite must as well. Therefore, for each coin there must be two outcomes which cause you to conclude that coin is fake. The only exception is a coin which is never weighed, since this corresponds to the outcome BBBBB, which is its own opposite. This means there can be at most (243-1)/2+1 = 122 coins if there is a successful strategy.

To get the promised upper bound of 121, we have to be more careful. Suppose that the first weighing places K coins on each side of the scale, leaving L of them aside.

If the scale doesn't balance, there are now 2K possibilities for the fake coin, to be determined in four tests which have three possibilities each. Therefore, it must be true 2K ≤ 34 = 81. Since 2K is even and 81 is odd, this further implies 2K ≤ 80. 
If the scale does balance, the fake is one of the L remaining ones. By the same logic as before, you can only find the fake now if L ≤ (81-1)/2+1 = 41.

Combining the last two bullets, the total number of coins, 2K + L, is at most 80 + 41 = 121, as advertised.

The Shortest Mustache Theorem · Answer

The fake coin and its type (heavier or lighter) can be determined from 120 coins by using the balance at most 5 times.

The formula is $$frac{3^N-3}{2}$$

1 Fake Coin among N Amount of coins

6 Answers

Add your own answers!

Ask a Question