The 12 Coin Problem

The 12-coin problem is the best known example of a generic family of puzzles where a set of apparently identical coins or balls or other such similar objects differ only in their respective weights, and the objective is to determine which coins are genuine and which are counterfeit.  The only means available to make this determination is an accurate balance scale.  You may not resort to X-rays, to ultra-sound, to testing electrical or magnetic properties of the coins, or to bribing the puzzle maker.  You may not test any physical difference between the coins other than their weight.

The number of coins can vary depending on the puzzle.  For example, there may be 12 or 20 or 100 coins, and you may or may not be told whether the counterfeit coins are lighter or heavier than the genuine coins.

There are really two basic questions for such puzzles.  The first question is simply to come up with a strategy that will find the counterfeit coins.  The second and usually more difficult question is to find the counterfeit coins using the least possible number of weighings.  Sometimes the puzzle will specify what the least possible number of weighings is.  Other times the puzzle will not specify what the least possible number weighings is, and part of the solution will be to ascertain what the least possible number of weighings is.

With the 12-coin problem, you are told that there are 11 genuine coins and 1 counterfeit coin and you are not told whether the counterfeit coin is heavier or lighter than the genuine coins.  Your task is to ascertain which coin is counterfeit and whether it is heavier or lighter than normal.  You may or may not be told that the 12-coin puzzle can be solved with three weighings.  Without this additional knowledge, most people determine that the least possible number of weighings is four.  But truly the puzzle can be solved with no more than three weighings.

I think that presenting the solution in a simple and straightforward manner is almost more difficult than solving the puzzle in the first place.  There are numerous correct solutions to the 12-coin problem on the Internet.  Perhaps the best Internet solution may be found at Wikipedia.  The Wikipedia article presents a very easy to understand solution.  It also has the advantage that it proves that at least three moves are required.  Finally, it has the advantage that it provides an interesting alternative solution.  The alternative solution pre-defines which coins are weighed during each of the three weighings, whereas with traditional solutions the coins that are weighed on the second and third weighings depend on the results of the previous weighings.

There are good solutions to the 12 coin problem on the Internet as exemplified by the solution at Wikipedia.  But I think many of the solutions on the Internet are almost more difficult to understand than it is to solve the puzzle in the first place.  The reader will have to make his or her own determination as to whether my write-up of a solution is any better.

I think that it's helpful to start by making some preliminary observations about how to approach any puzzle involving coins and a balance scale.

1. The basic strategy almost always includes a variation on the theme of divide and conquer.  Either half the coins are placed on one side of the scale with the other half on the other side of the scale, or else one-third of the coins are placed on one side of the scale, one-third of the coins are placed on the other side of the scale, and the last one-third of the coins are not placed on either side of the scale.  The objective of these kinds of weighings is gradually to reduce the number of coins by halves or by thirds until you have isolated the coin or coins that are counterfeit.
2. In the case of the 12-coin problem you need to start out by trying to reduce the number of coins by thirds, meaning that you first weigh 4 of the coins against another 4 and leave the last 4 coins off the scale the first time through.  This strategy is dictated by the fact that you don't know initially whether the counterfeit coin is heavier or lighter than normal.  Therefore, if you start out by weighing 6 coins against 6 coins, you will know in advance that one side of the scale is going to go up and the other side is going to go down.  But when one side goes up and the other goes down, it doesn't really tell you anything at all about which of the 12 coins is counterfeit.

3. In your divide and conquer strategy, you need to be very careful not to discard coins too quickly after they have been determined to be genuine.  For example, suppose that when you first weigh 4 coins against 4 other coins, the scale is in balance.  That means that you have identified 8 genuine coins and that the problem has been reduced from 12 coins to 4 coins with two more weighings to go.  But if you then try to solve the new 4-coin problem using only those 4 coins, you will find that you cannot solve the smaller problem with only two more weighings.  To solve the problem in only two more weighings, your second and third weighings will have to use some of the genuine coins that you have already identified.
4. As you think through how to solve the puzzle, it's natural to focus your thinking at times on how best to isolate the counterfeit coin from the genuine coins.  And it's natural at other times to focus your thinking on how best to determine whether the counterfeit coin is heavier or lighter than normal.  But in fact, you will discover that to come up with a solution that requires no more than three weighings, you will have to manage the weighings in such a way that you will be isolating the counterfeit coin and also identifying whether it is heavier or lighter than normal all at the same time.

With the preliminaries out of the way, let's now describe a strategy for solving the puzzle.

1. First weighing - weigh 4 coins against 4 coins. There are two possible outcomes - the scale is in balance or the scale is out of balance.  It may be tempting to say that there are three possible outcomes - the left side of the scale is heavier, the right side of the scale is heavier, or the scale is in balance.  But if we are careful, we can simplify our write-up by treating either of the out of balance outcomes as being equivalent.

   1. Second weighing - the scale was in balance on the first weighing.  Therefore, the 8 coins that were weighed are known to be genuine and the 4 unweighed coins remain unknown.  Weigh 3 of the genuine coins against 3 of the remaining 4 unknown coins.  There are two possible outcomes - the scale is in balance or the scale is out of balance.

      1. Third weighing - the scale was in balance on the first two weighings.  Therefore, all 11 coins that have been weighed are known to be genuine and the 12^th coin that has not yet been weighed is known to be counterfeit.  It remains only to determine whether the counterfeit coin is heavier than normal or lighter than normal.  Weigh 1 of the genuine coins against the counterfeit coin to determine if the counterfeit coin is heavier or lighter than normal.

      2. Third weighing - the scale was in balance on the first weighing and out of balance on the second weighing.  Therefore, 9 coins are known to be genuine - the 8 coins that were in balance on the first weighing and the 1 unknown coin that was not weighed on the second weighing.  The 3 unknown coins that were weighed on the second weighing are still unknown.  However, it is now known whether the counterfeit coin is heavier or lighter than normal.  Weigh 2 of the 3 remaining unknown coins against each other.  If the 2 are in balance, the counterfeit coin is the 3^rd unknown coin that was not weighed on the third weighing, and its heavier or lighter status is already known.  If the 2 coins are out of balance, one of them is counterfeit and we know which one it is because its heavier or lighter status is already known.

   2. Second weighing - the scale was out of balance on the first weighing.  Therefore, the 4 coins we didn't weigh are now known to be genuine, and the 8 coins we weighed are all still unknown.  And we know a little bit about the 8 unknown coins, because we know which 4 coins were on the heavy side of the scale and which 4 coins were on the light side of the scale.  So if later in the process we are able to determine whether the counterfeit coin is heavier or lighter than normal, the number of unknown coins immediately drops from 8 to 4.

      This is the most challenging point in the solution.  It's tempting to do something like weighing 3 of the coins from the heavy side of the first weighing plus 1 of the coins from the light side of the first weighing against the 4 coins that are now known to be genuine.  That is close to the correct solution, but is not quite right.  It works if by luck the second weighing is unequal, but it gets us into needing four weighings if the second weighing is equal.  The correct solution is very similar to the incorrect solution that we might have been tempted to try.  Weigh 3 of the coins from the heavy side of the first weighing plus 1 of the coins from the light side of the first weighing against 3 of the coins that are now known to be genuine plus the 4^th coin from the heavy side of the first weighing.  The counterintuitive aspect of the solution is that we need to split the 4 coins from the heavy side of the first weighing and put some of them on one side of the scale and the other one on the other side of the scale.

      1. Third weighing - the scale was out of balance on the first weighing and was in balance on the second weighing.  All the coins involved in the second weighing are known to be genuine.  Therefore, 9 coins are known to genuine - the 4 coins that were not weighed in the first weighing, the 4 coins that were on the heavy side of the scale in the first weighing, and the 1 coin from the light side of the first weighing that was weighed again as a part of the second weighing.  The 3 coins that remain unknown were all on the light side of the first weighing.  Weigh 2 of the remaining 3 unknown coins against each other.  If they are out of balance, the coin from the lighter side of the third weighing is the counterfeit coin and it is lighter than normal.  If they are in balance, the counterfeit coin is the remaining unknown coin that was not weighed on the third weighing, and it is lighter than normal.

      2. Third weighing - the scale was out of balance on the first weighing and was out of balance on the second weighing.  The heavy side of the second weighing was the side containing the 3 coins that were on the heavy side of the first weighing  The counterfeit coin must be one of those 3 coins.  Weigh 2 of them against each other.  If they are out of balance, the heavier coin is the counterfeit coin.  If they are in balance, the counterfeit coin is the remaining unknown coin and it is heavier than normal.

      3. Third weighing - the scale was out of balance on the first weighing and was out of balance on the second weighing.  The heavy side of the second weighing was the side containing 3 genuine coins plus 1 coin that was on the heavy side of the first weighing.  The light side of the second weighing was the side containing 3 coins that were on the heavy side of the first weighing and 1 coin that was on the light side of the first weighing  10 coins are known to be genuine - the 4 coins that were not weighed on the first weighing, the 3 coins that were on the heavy side of the first weighing and on the light side of the second weighing, and the 3 coins that were on the light side of the first weighing and that were not weighed on the second weighing.  The problem is therefore reduced to 2 coins - 1 that was on the light side of the first weighing and that was also on the light side of the second weighing, and 1 that was on the heavy side of the first weighing and that was also on the heavy side of the second weighing.  It might be tempting simply to weigh the last 2 coins against each other, but the 1 that was on the heavy side of both of the first two weighings will be heavier than the 1 that was on the light side of both of the first two weighings.  So weighing the 2 remaining unknown coins against each other will not tell us anything about which one of them is genuine.  Therefore, weigh either of the 2 remaining unknown coins against a genuine coin.  If the third weighing is balanced, the counterfeit coin is the unknown coin that was not weighed on the third weighing, and it is already known whether it's heavier or lighter than normal.  If the third weighing is not balanced, the counterfeit coin is the unknown coin that was weighed on the third weighing and it is already known whether it's heavier or lighter than normal.