problem is as follows: Given 12 coins, one of which is counterfeit, use
a balance to determine the counterfeit in three weighings, where the
counterfeit coin may be either lighter or heavier than the other coins.
I have taken this material from The
Mathematics of Games
Beasley, which I highly
The general approach is to start with 3 coins containing a counterfeit
and then to show how we can use that solution to go from 3 coins to 12
coins and then to generalize the procedure to continue to increase the
number of coins.
We start with the problem for 3 coins. There are 3 coins with
counterfeit coin that is either heavier or lighter than the other 2.
Determine which coin it is in two weighings of a balance
This problem is fairly simple to solve, since there is not
that we can do. Number the coins 1, 2 and 3.
On the first
weighing, place coin 1 on the left pan and coin 2 on the right pan.
For the second weighing, place coin 2 on the left pan and
on the right pan.
If coin 2 is the counterfeit then the scale will not be balanced for
both weighings. If the counterfeit coin is 1 or 3,
scale will be unbalanced only for one weighing. This makes it
easy to indentify the counterfeit coin and to determine if it is heavy
Note that the coins used for the second weighing does
not depend on the result of the first weighing. This will
continue to hold true. .
This means that the weighings could be done in any order.
The reason for switching pans for coin 2 on the second weighing
is important for when we increase the number of coins. For
note that no coin is on the same pan for each weighing and that every
coin is on the scale at least once. This means that the scale
will not remain balanced or tip in only one direction for both
9 Coin Problem
As an intermediate step, consider the problem for 9 coins. Place the
coins in stacks of 3. Perfom two weighings of the
of coins in the same way that we weighed the three individual coins in
the 3 coin problem. For the third weighing, break apart the
stacks of three, placing one coin from each stack on the left pan and
one on the right pan.
From the first two weighings, we know which stack contains the
counterfeit coin and whether it is heavy or light. On the
weighing, one coin from this stack is on the left pan and one coin is
on the right pan. The scale will balance if the unchosen coin from the
counterfeit stack is the counterfeit coin. Otherwise the
will tip, revealing which coin is counterfeit.
The weighings look like this:
The requirement from the 3 coin problem that no coin be in the same
place for both weighings means that none of the 3 stacks, and
hence none of the nine coins, is in the same place for the first two
weighings. This will allow us to place additional coins on
the balance that are
in the same place for the first two weighings, and we will be able to
recognize that the counterfeit is among them because only in that case
will the balance behave the same way on the first two weighings.
From 9 coins to 12 coins
We now add 3 more coins to the 9 coin problem. To go from nine
twelve, place one of the three additional coins on the left balance for
the first two weighings and one coin on the right balance for the first
weighings. For the third weighing move the coin from the
right pan to the left pan and place the unused coin in the right pan.
We will know if one of the three additional coins is
if the balance behaves the same way for the first two weighings.
The thrid weighing will then tell us which of these coins is
counerfeit and whether it is heavy or light. Again we have
arranged the weighings so that every coin is on the balance at least
once and no coin is on the same pan each time.
The three weighings would be as folllows:
We can go from 12 coins to 39 coins in a way similar to how we went
from 3 coins to 12 coins. Form 12 stacks of 3 coins and place
stacks in the same way as the 12 coins from the 12 coin problem. If the
counterfeit coin is in the 12 stacks, we will know after
weighings which stack it is in and whether it is heavy or light. For
the fourth weighing, break apart these stacks of 3 and place one coin
from each stack on the left pan and one on the right pan. If
counterfeit coin is among the 36 coins in the stacks, we will know
after the fourth weiging which coin it is and whether it is heavy or
For the three coins not in any of the 12 stacks, place one coin on the
left balance for the first three weighings and one coin on the right
balance for the first three weighings. On the fourth
move the coin from the right pan to the left pan and placed the unused
coin on the right pan. If the counterfeit coin is among these
the balance will behave the same way for the first three weighings and
the final weighing will tell us which is the counterfeit and whether it
is heavy or light.
Once again we have arranged things so that no coin is in the same place
for every weighing.
started with 3 coins. We got to
twelve coins by multiplying the 3 coins by 3 and adding 3, which we can
represent as 3 × 3 + 3 = 32
+ 3. To get to 39
coins we again multiplied by 3 and added 3.
+ 3) + 3 = 33
For round n, the number of coins is 3n
+ ... + 3. This is a geometric series with the 1 term missing
is therefore equal to (3(n+1)
- 1)/(3 - 1) - 1 = (3(n+1)
Since we started with two weighings for n = 1 (3 coins), and the number
of weighings increases by one each time, the number of weighings for
round n is n+1.
- 3)/2 coins we find the number of
possibilities by multiplying by 2, since each coin can be heavy or
light, which gives us (3(n+1)
- 3) possiblities.
In n + 1 weighings, the maximum number of possible outcomes
Remember that we excluded the possibility that each weighing will have
the same outcome, since none of the coins (including the counterfeit)
is in the same position for each weighing. We are therefore
eliminating 3 possibilites - where the scale balances, tips
or tips right for every weighing. The total number of
outcomes is therefore (3(n+1)
- 3), exactly
matching the number of possible ways that a coin can be