10
$\begingroup$

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

enter image description here

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?

$\endgroup$
  • 6
    $\begingroup$ if N=2 how do you know? $\endgroup$ – JonMark Perry Jan 11 '17 at 11:19
  • $\begingroup$ @JonMarkPerry if N=2, you cannot find it of course since one is genuine and one is fake -.-... I ask for the maximum amount of coins. $\endgroup$ – Oray Jan 11 '17 at 11:21
  • $\begingroup$ @Oray I think you mean minimum $\endgroup$ – TrojanByAccident Jan 11 '17 at 11:33
  • $\begingroup$ @TrojanByAccident no maximum... $\endgroup$ – Oray Jan 11 '17 at 11:34
  • $\begingroup$ Related: puzzling.stackexchange.com/questions/47659/… $\endgroup$ – TrojanByAccident Jan 11 '17 at 11:34
6
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Oh! I just remembered the technique! We have to divide in 3 groups all the time, and eliminate 2 after each comparisons. $\endgroup$ – stack reader Jan 11 '17 at 12:11
  • 3
    $\begingroup$ The maximal $N$ may be even more than this. It's proved in the answer to this question that 5 weighings is enough even for a more complicated problem. In this one, we know exactly one coin is fake, which simplifies the problem slightly. $\endgroup$ – Rand al'Thor Jan 11 '17 at 12:12
  • $\begingroup$ @randal'thor true. also, this question doesn't ask you to tell if it's lighter or heavier, you just have to point out the bad one. that could also increase the number of coins possibly $\endgroup$ – Ivo Beckers Jan 11 '17 at 12:14
  • $\begingroup$ A proof of this (and many, many other variants) can be found here. $\endgroup$ – Ankoganit Jan 11 '17 at 15:33
  • 1
    $\begingroup$ I am not sure that I should accept this answer without showing weighings. I will wait a bit more, if noone can show it, I will edit your answer with my explanation and accept it if you allow... $\endgroup$ – Oray Jan 11 '17 at 16:00
6
$\begingroup$

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

121

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Why do the 5th step like that when you could do it similarly to the previous steps? $\endgroup$ – TrojanByAccident Jan 11 '17 at 12:01
  • $\begingroup$ @TrojanByAccident I'm in a rush so my explanation is kinda messy but if you compare the last 2 together, they will be different, but you won't know which one is fake. So comparing them with those you know are good will be better. $\endgroup$ – stack reader Jan 11 '17 at 12:04
  • $\begingroup$ sorry, I meant the 4th step $\endgroup$ – TrojanByAccident Jan 11 '17 at 12:16
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ A correct answer, with full explanatory proof, has already been provided and accepted. How does your answer, which offers a formula but provides no cite or proof of its correctness and/or applicability, add value to what has already been said? $\endgroup$ – Rubio Jan 13 '17 at 22:12
  • $\begingroup$ I use an induction-like proof. I start from the smallest possible N, and find the maximum coins in which the fake and its type (heavier or lighter) can be determined. I did it 15 years ago and I will show the proof later. No time now, sorry. $\endgroup$ – Money Oriented Programmer Jan 14 '17 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.