mathematics - 1 Fake Coin among N Amount of coins

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?

Answer

An algorithm for reaching Ivo's answer:

You can find the fake out of up to 121 coins, but you cannot necessarily distinguish if the fake is heavy or light. You cannot find the fake among more than 121 coins, as there are simply too many possibilities.

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.