The Twelve-Coin Problem

The Twelve-Coin Problem is a logical thought exercise based on Information Theory that asks you to uniquely identify an item in a set. More specifically:

You are given twelve coins, one of which is counterfeit. The counterfeit coin looks identical to the other eleven, but weighs either slightly less or slightly more. To help identify the counterfeit you are given a balance scale that you may use up to three times.

Understanding the Problem

Before solving the problem, the problem must be well understood. While this seems obvious, it is relatively easy to overlook an aspect of the problem description that can greatly simplify things. In addition to considering what is stated in the problem, it is often just as crucial to evaluate what is not stated. Keeping this in mind while assessing the description, we can determine eight things.

• There are precisely twelve coins.
• One of them is guaranteed to be a counterfeit coin (the case of no counterfeit coin does not need to be considered).
• The only tool available is a simple balance scale.
• The balance scale may be used a maximum of three times.
• Not every coin needs to be a part of every weighing (which may seem silly to point out but is crucial to the solution).
• Coins may be weighed more than once and in any combination.
• All we have to do is identify the counterfeit coin, not whether it is heavy or light.
• Any scale use only makes sense if the number of coins is equal on each side.

Being able to leave coins out is essential. Without this possibility, every coin must be on the left or right for every scale use. That would only give us two options for a coin at each weighing. With only two options and three uses of the scale permitted, there would be \(2^3 = 8\) unique combinations (three bits of information). Eight unique combinations would not be enough to identify the counterfeit with twelve coins on the table. Leaving a coin out adds another possible state, resulting in \(3^3 = 27\) unique combinations (three trits of information).

One unfortunate stipulation, which makes this problem so interesting, is that it is unknown whether the counterfeit coin is lighter or heavier than the others. The lack of certainty is significant because when one side of the scale is heavy, it only tells us that a counterfeit is currently on the scale, not which side it is on. Therefore a particular combination of trits and its inverse would have to point to the same coin as the counterfeit. This dual nature limits the number of options to half of the original possible combinations, theoretically allowing the ability to identify 13.5 coins (though this is impossible) successfully.

Solving the Problem

With the problem well understood, it is now possible to develop a system that uniquely identifies any coin as counterfeit. The system will also consider whether the coin is heavier or lighter than the others.
The table below shows the potential patterns assuming that the coin is based on the left plate by default. Since it is a balance scale, the coins can not reasonably only use the left side to start. The table illustrates all the potential combinations of trits that could produce unique information.
Another critical aspect is that both a sequence and its inverse point to the same coin. One sequence represents the case where the coin is heavy and the other when the coin is light. Inversion only applies when a coin is on the scale with (\neg L \rightarrow R) (inverting (L) being down means (R) must be down and vice-versa). The "half option" mentioned above is the unlikely case where a coin is not included in any comparisons (meaning none of the weighed coins is counterfeit). Being entirely excluded has an inverse that is still the same information (not included). Therefore, this option cannot reveal whether the counterfeit coin is heavy or light.
In no particular pattern order, the table below shows a theoretical way to uniquely identify which of fourteen coins could be counterfeit and which of thirteen are either heavier or lighter than the others.

The table entries obviously cannot work directly as the first use of the scale would put nine coins on the left side and none on the right, which ultimately tells us nothing. The trick is selecting each round to maximize the information obtained.

Solution

For the problem to work within the confines of its description, some coins flip their heavy/light patterns so that the scale always has the same number of coins on each side. The swapping of some columns gives a new pattern table utilizing a compatible subset of options:

By reading down the Heavy Pattern column in the table we can assign coins to the scale plates for each round and verify that there is always the same number of coins on each side.

For this solution to be valid, it must work. The table below shows the results of the three uses of the scale with an interpretation according to the above tables. The results use the following letters as a shorthand:

• \(N\): Scale did not tip in either direction (balanced).
• \(L\): The left plate was heavier.
• \(R\): The right plate was heavier.