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.
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.
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.
Hint: Consider weighing half of the coins on each side. What will this tell you ?
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.