12 Coin Problem And Its Generalization
The
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 by John Beasley, which I highly recommend.
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.
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 coin 3 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,
the
scale will be unbalanced only for one weighing. This makes it
easy to indentify the counterfeit coin and to determine if it is heavy
or lignt.
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 now, 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 weighings.
As an intermediate step, consider the problem for 9 coins. Place the coins in stacks of 3. Perfom two weighings of the stacks 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 third 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 balance 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.
We now add 3 more coins to the 9 coin problem. To go from nine coins to 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 two 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 counterfeit 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 the 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 three 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 the 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 light.
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 weighing, 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 3, 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.
I have taken this material from The Mathematics of Games by John Beasley, which I highly recommend.
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.
3
Coin Problem
We start with the problem for 3 coins. There are 3 coins with
a
counterfeit coin that is either heavier or lighter than the other 2.
Determine which coin it is in two weighings of a balance
scale.
This problem is fairly simple to solve, since there is not
much
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 coin 3 on the right pan.
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 now, 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 weighings.
12
Coin Problem
9 Coin Problem
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 stacks 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 third 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 balance will tip, revealing which coin is counterfeit.
The weighings look like this:
From 9 coins to 12 coins
We now add 3 more coins to the 9 coin problem. To go from nine coins to 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 two 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 counterfeit 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:
39
Coin Problem
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 the 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 three 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 the 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 light.
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 weighing, 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 3, 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.
General
Case
We
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( 32 + 3) + 3 = 33 + 32 + 3.
For round n, the number of coins is 3n + 3(n-1) + ... + 3. This is a geometric series with the 1 term missing and is therefore equal to (3(n+1) - 1)/(3 - 1) - 1 = (3(n+1) - 3)/2.
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.
For (3(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 is 3(n+1). 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 left or tips right for every weighing. The total number of possible outcomes is therefore (3(n+1) - 3), exactly matching the number of possible ways that a coin can be counterfeit.
3( 32 + 3) + 3 = 33 + 32 + 3.
For round n, the number of coins is 3n + 3(n-1) + ... + 3. This is a geometric series with the 1 term missing and is therefore equal to (3(n+1) - 1)/(3 - 1) - 1 = (3(n+1) - 3)/2.
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.
For (3(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 is 3(n+1). 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 left or tips right for every weighing. The total number of possible outcomes is therefore (3(n+1) - 3), exactly matching the number of possible ways that a coin can be counterfeit.