1
$\begingroup$

In 80 coins one coin is counterfeit. What is minimum number of  weighings to find out counterfeit coin?

PS: The counterfeit coin can be heavy or lighter.

$\endgroup$
  • 13
    $\begingroup$ It can't be done with weighings at all. No self-respecting counterfeiter would commit the rookie mistake of getting the mass wrong. $\endgroup$ – Henning Makholm Oct 20 '12 at 14:26
  • 3
    $\begingroup$ Please specify if you know whether the coin is heavy or light. That changes the process a bit. $\endgroup$ – Ross Millikan Oct 20 '12 at 14:38
  • 2
    $\begingroup$ @Ross The question doesn't state that the counterfeit coin has a different weight from the others. My guess is that the real coins are made of gold and the counterfeit one, although it weights the same, is made of brass, and can be distinguished from the real coins with no weighings at all. $\endgroup$ – MJD Oct 20 '12 at 15:36
  • 1
    $\begingroup$ @MJD: Good point. I can't imagine how to do it with less than zero weighings. $\endgroup$ – Ross Millikan Oct 20 '12 at 15:38
5
$\begingroup$

Hint: Consider weighing one third of the coins on each side. What will this tell you?

In fact, it can be shown that the process, the definition of which you will be led to by this hint, is optimal. Try to think of why this is the case, and to classify how many weighings you need with $n$ coins.

$\endgroup$
1
$\begingroup$

Hint: Consider weighing half of the coins on each side. What will this tell you ?

$\endgroup$
  • 2
    $\begingroup$ Then what is it ? if you have some solution write it in the question! $\endgroup$ – Belgi Oct 20 '12 at 14:27
  • $\begingroup$ Consider weighing one third of the coins on each side. What will this tell you? $\endgroup$ – Lord_Farin Oct 20 '12 at 15:44
  • $\begingroup$ @Lord_Farin - put it as an answer, very nice $\endgroup$ – Belgi Oct 20 '12 at 15:49
1
$\begingroup$

I will start with a simple case of three coins and describe the method. By this example, I introduce some notation:

Case 1a) Three coins and the counterfeit is H(eavier) (equivalently, one can assume otherwise and proceed in the similar lines).

The coins are numbered as 1, 2, 3.

Weigh coins 1 and 2 in a physical balance and keep the coin 3 aside.
This I represent by
Weighing 1:
$1:2;3$
If they are in balance, i.e, $1 = 2,$ then $3$ is a counterfeit coin and it is heavier.
I represent it by
If $1=2,$ then $3$ is H.

If they are not in balance, say, pane having coin $1$ is lower than the pane having coin $2,$ then we represent it by $1 \lt 2.$
That is, if $1 \lt 2,$ then $1$ is H else $2$ is H. This I present by
{ Weighing $1$:
$1:2;3$
If $1 = 2,$ then $3$ is H.
If $1 < 2,$ then $1$ is H.
If $1 > 2,$ then $2$ is H.
}

Thus if we have three coins and we know that the counterfeit coin is H (or L), then with one weighing we can determine it.

Case 1b) Three coins and the counterfeit coin may be H or L.

{Weighing (1)
$1:2;3$
We may get, here, $1 = 2$ or $1 \lt 2$ ( or $1 \gt 2$ for which the following procedure is suitably modified)
{If $1=2,$ then $3$ is H/L }

If $1 \lt 2,$ then
{Weighing (2)
{$1:3$
If $1 > 3,$ then $3$ is H else $3$ is L
}
}
Or
{
If $1 < 2,$ then $1$ is H or $2$ is L
Weighing (2)
{ $1:3;2$
If $1 = 3,$ then $2$ is L else (i.e, $1<3$) $1$ is H
}
Thus in the case of $3$ coins and if it is unknown whether it is H or L, we need 2 weighing.

Case 2: Nine coins and we do not know whether the counterfeit coin is H or L.
Weighing (1)
$1,2,3 : 4,5,6; 7,8,9$
{
If $1,2,3 = 4,5,6$ then $7$H/L, $8$H/L, $9$H/L
Weighing (2)
$1,2,3 :7,8,9$
If $1,2,3 \gt 7,8,9$ then $7,8,9$ are H else $7,8,9$ are L. This is resolved by third weighing as in case 1a).
}
{
If $1,2,3 \lt 4,5,6$ then $1,2,3$ are H or $4,5,6$ are L.
Weighing (2)
$1H,2H,4L:3H,7,8$ (Note the swapping!)
{
If $1H,2H,4L \lt 3H,7,8,$ then $1$ or $2$ is H
{ weighing (3)
$1:2$
If $1 \lt 2,$ then $1$ is H, else $2$ is H
}
{
If $1H,2H,4L \gt 3H,7,8,$ then $3$ is H or $4$ is L.
{Weighing (3)
$1:3$
If $1 = 3,$ then $4$ is L, otherwise $3$ is H}
}
}

Thus using three weighing the counterfeit coin from $9$ coins can be found out.

Similar approach can be used to solve the case of $27$ coins in $4$ weighing and the case of $81$ cases in $5$ weighing.

The restriction of total coins as $80$ does not affect the solution procedure.

$\endgroup$

protected by Zev Chonoles Aug 28 '16 at 19:53

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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