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?

Answer 1

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.

Answer 2

A naive upper bound is N = 243 = 3⁵, 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

121

There are 3⁵ = 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 5^th, 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 ≤ 3⁴ = 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.

Answer 3

The answer is

121

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

$(3^n-1)/2$

coins.

Answer 4

Worse case scenario :
- Split all the coins in 4 equal groups.(32 coins)
- Test 2 groups, they are equal of weight so you put them aside.(1st test 16 coins left)
- Split your 3rd group in half and compare them, they are equal so you put them aside. (2nd test 8 coins left)
- Split your 4th group in 4 and compare 2 of them together. They are the same so you put them aside. (3rd test 4 coins left)
- Split one of the last 2 groups in half and compare them. They are the same so you put them aside. (4th test 2 coin left)
- Split the last group in 2 and compare 1 of them with one you put aside earlier and you can know which of the remaining one is fake. (5th test 1 coin left)
total 32 coins

Answer 5

Total coins

24

Explanation:-

Steps one and two

You have 24 coins. Split them into groups of 3 with 8 coins each. Measure group AvsB. If the balance is still, then the fake coin is in group 3. But this isn't the worst case scenario. We must assume AvsB results in a tilt to either side. So we measure AvsC. If they remain center and don't tilt, B has the fake. else A has the fake.

Step three

We take the 8 coins and divide them into groups of 4 each. We measure either group with 4 correct coins we discarded earlier. If the pan balances, the other group has the culprit, if not, this group has the culprit.

Step four

We take the 4 coins and divide them into groups of 2 each. We measure either group with 2 correct coins we discarded earlier. If the pan balances, the other group has the culprit, if not, this group has the culprit.

Step five

We take the 2 coins and divide them into groups of 1 each. We measure either group with 1 correct coin we discarded earlier. If the pan balances, the other coin is the culprit, if not, this coin is the culprit.

Answer 6

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}$$