We are working on the logic problem from IMP Level 1 entitled "Twelve Bags of Gold". We can solve the problem when the first weighing is equal, but if it is unequal we get too many weighings. FYI: the problem states that a king wishes to find the one bag of counterfeit gold out of his 12 bags; he has only a pan balance scale and wants to do it in 3 weighings. He does not know if the counterfeit gold is heavier or lighter than the real gold. Are you familiar with this problem? We have found it very interesting, and have been working at it for a week now. Would appreciate any guidance that you can give. Thank you, C.

(Remark. This problem is often stated as the "Twelve Coins" problem: you are given twelve coins, eleven of them fair and one false, and asked to use three weighings on a balance scale to find the false coin and tell whether it is heavy or light. We'll call this the Odd Weight Coin Problem. If you know in advance whether the false coin is heavy or light the problem is simpler; using n weighings you can distinguish the false coin among 3ⁿ coins; for example, with 3 weighings you can distinguish a false coin among 27 coins instead of only 12. We'll call this the Known Weight Coin Problem. If you're not familiar with this simpler problem, you should study it first. It is written up as another Best of MathNerds item here: The Counterfeit Penny.)

Hint 1

Think small. Twelve coins and three weighings is a lot; can you work a smaller problem? It seems impossible to deduce anything based on one weighing, but with two weighings you can find the false coin and its weight among three coins; do you see how?

Think big. Try to find general method that will work for n weighings. It turns out that you can find the false coin and its weight among (3ⁿ - 3) / 2 coins. The twelve coin case is n=3; you can also find the false coin out of 39 using 4 weighings, or out of 120 using 5 weighings. Note that this is only about half the number of coins the Known Weight Coin Problem can handle; we're at a disadvantage because we don't know whether the false coin is light or heavy. We'll call a problem that allows n weighings an order n problem.

Hint 2

Thinking small: Let's call the three coins A, B, C, and do these two weighings:

A against B
B against C

The interpretation:

If either weighing balances, we know the two coins involved are fair and the third coin is false, and because the third coin participates in the other weighing with a fair coin (as we now know), we can tell whether it is light or heavy.
If neither weighing balances, there are two cases:
- B is the same in both weighings (either both heavy or both light); then B is the false coin and is heavy or light according to the weighing.
- B is light in one weighing and heavy in the other; this is actually impossible, because B would have a weight that is between the weights of A and C, giving us three different weights instead of two.

Notice that we rotate rather than swap for the second weighing: We rotate A out of the pans, rotate B from the right to the left pan, and rotate C into the right pan. This is logically equivalent to swapping A and C, but it turns out that rotation is easier to think about than swapping. We can use this rotation method more generally, to distinguish three equally-sized groups of coins. We can always pick out the group with the false coin, and we can tell whether the false coin is light or heavy. And further: We can even handle the case where all three groups contain only fair coins, because then both weighings will balance (this can't happen if there is a false coin). The rotation method will be our main tool in solving the Odd Weight Coin Problem.

The Known Weight Coin Problem has a recursive structure; that is, it contains a smaller problem of size 3^n-1, and we can reduce the order n problem to an order n-1 problem with one weighing. The Odd Weight Coin Problem also has a recursive structure, although it is less simple, and harder to find. Can you find it?

Hint 3

Just by looking at the sizes, we might speculate that if the Odd Weight Coin Problem contains a smaller version of itself, it would be one step smaller and so would contain (3^n-1 - 3) / 2 coins. This would leave

(3ⁿ - 3) / 2 - (3^n-1 - 3) / 2 = 3^n-1

coins over, which happens to be the same as the Known Weight Coin Problem of order n-1. Coincidence? Perhaps not. It might be possible to step down from an order n Odd Weight Coin Problem to either an order n-1 Odd Weight Coin Problem or an order n-1 Known Weight Coin Problem, probably based on the specific outcome of the weighing. One obvious problem is that we need at least two weighings to conclude anything, while we would are only allowed (on the average) one weighing per step down. In order to make some progress, let's temporarily allow ourselves two weighings per step down. Then later on we'll see if we can fix it up somehow to use only one weighing. (This is a common method in mathematical discovery: make some additional assumptions, or relax some of the constraints, and see if we can get the answer in these more favorable conditions. If we can, then we will have learned something about the problem, that we can use to attack the original problem. If you can't solve a problem, try to find a related simpler problem that you can solve!)

Hint 4

Let's arbitrarily divide the (3ⁿ - 3) / 2 coins into two groups: One with 3^n-1 coins (we'll call this the major group) and one with (3^n-1 - 3) / 2 coins (the minor group). We divide the major group into three subgroups of 3^n-2 coins each, and apply the rotation method to decide whether or not the major group contains the false coin. This takes two weighings.

This doesn't completely solve our problem, because we are still using too many weighings, namely two per step down. But when the major group contains the false coin we are actually OK, because we have spent two weighings (leaving n-2 over), and we have reduced it to a Known Weight Coin Problem of order n-2. We know that we can finish this in n-2 weighings. We aren't so lucky in the minor group case, because we spent two weighings but only cut the order of the problem by one.

Now think about how we could cut down the number of weighings in the first case, where the minor group turned out to have the false coin.

The Rest of the Solution

There's a sneaky way to combine two weighings in one. Just as before, divide the major group in three equal parts (call them A, B, C), but also divide the minor group in three equal parts (call them a, b, c). Now put a major and a minor part on each balance pan, but don't rotate the minor parts. That is, for the first weighing we balance (A and a) against (B and b), and on the second weighing balance (B and a) against (C and b). What happens?

If the major group contains only fair coins, then the rotation has no effect on the balance results. On the other hand, if the major group contains the false coin, then the minor group contains only fair coins, and so has no effect on the results: one weighing balances and one does not, and from that we can tell which major subgroup contains the false coin, and its weight.

What's the advantage of the added groups a and b? When the major group is all fair coins, the result of our weighing is the same as the result of balancing a against b, which is the first weighing we would use in the rotation method for distinguishing a, b, and c! We get a "bonus" weighing (or put another way we are sharing the results of each weighing with two steps), and this allows us to cut down the number of weighings to one per step.

Recap and Example

That was somewhat intricate! Let's work out explicitly the steps for 12 coins to assure ourselves that we haven't tucked away an extra illegal weighing somewhere.

To resolve 12 coins, divide them into a major group of 9 coins and a minor group of 3 coins, and further divide these into three equal groups A, B, C, of 3 coins each and three equal groups a, b, c of one coin each. The weighings are:

(A and a) against (B and b).
(B and a) against (C and b).
There are two cases for the third weighing, according to the results of the first two weighings:
1. If both results are the same, then the false coin is in the minor group, and we already know from the first two weighings the result of a against b. Therefore our third weighing is to rotate the minor group (that is, balance b against c), and we finish as in Hint 2.
2. If the two results differ, then the false coin is in the major group, and we know which of A, B, C it is in, and whether it is heavy or light. The false subgroup contains three coins, so balance any two against each other. If they balance, the false coin is the third one, and if they don't balance, the false coin is the heavy or light side according to whether the false coin is know to be heavy or light.

Industrial-Strength Algorithm for Many Coins

We'll show how to organize this method in a very simple and systematic way that is especially handy when dealing with a large number of coins (for example, 120 coins and 5 weighings).

Divide the (3ⁿ - 3) / 2 coins into three groups of (3^n-1 - 1) / 2 coins each.
Subdivide each group into n-1 subgroups of 3^n-2, 3^n-3, ... 3¹, 3⁰ coins.
For the first weighing, place the first two groups in the two pans.
Starting with the largest subgroups and working down, rotate each subgroup once and observe whether the result of the weighing changed. If not, keep working down. If it did change, then one of the three subgroups has the false coin, and we can tell which one and whether the coin is heavy or light. Break off and apply the solution of the Known Weight Coin Problem to this subgroup. (Optionally you can remove the largest subgroups after each weighing if the result did not change; in this case we know the subgroups contain only fair coins, and having it present or absent does not affect the results.)
If we get all the way to the smallest subgroup, we still rotate it, but we don't need to apply the Known Weight Coin Problem method because we have already isolated the false coin to a group of 1.

We will break off with the group of size 3^n-k, where 2 ≤ k ≤ n-1, and then apply the Known Weight Coin Method to a group of size 3^n-k-1. Therefore the total number of weighings is 1 + k + (n - k - 1) = n.

The algorithm for the Known Weight Coin Problem is to perform this sequence of steps repeatedly:

Divide the coins into three equal groups.
Choose any two groups and place them in the balance pans.
If they balance, put those groups aside and switch to the third group. If they don't balance, one of them contains the false coin, and we can tell which one because we know whether the false coin is light or heavy. Put the other two groups aside and switch to the false group.

The 13-Coin Problem

One variant of the 12-coin problem is the 13-coin problem. As before, you are allowed three weighings, and you don't know whether the false coin is light or heavy; but you are now not required to determine the false coin's weight. This problem can be worked by exactly the same method. Just put one coin aside, and work the 12-coin problem for the remaining coins. The 12-coin solution works even if all coins are fair, so if the put-aside coin was the false coin, we will detect that the other 12 are fair and correctly finger the 13th (although we won't know its weight), and if one if the 12 is false, we will detect it and its weight.

Fewer than 12 Coins

People sometimes ask if this problem can be solved if fewer than twelve coins are given. The naive problem solver would expect that it should be simpler to isolate a false coin from (say) 10 coins than from 12, but our methods depend on having an adequate supply of fair coins, so having a smaller total number of coins is not necessarily an advantage. Experimentally it appears that we can solve the problem for most smaller numbers of coins but not all. For example, 11 coins in three weighings can be solved in almost the same way as the 12-coin problem, because in the 12-coin solution there is one coin (in the minor group) that is not used in the first two weighings. We can pretend it is there, and use a known fair coin for it if needed for the third weighing. On the other hand, if we have only two coins, it is impossible to make any progress regardless of how many weighings we are allowed, because there is one fair and one false coin, and there's no inherent way to tell which is which.

References

You can read C's original question here.
The Known Weight Coin Problem is solved as another Best of MathNerds item The Counterfeit Penny.
There's an extensive discussion of the Twelve Coin Problem at the Cut The Knot! website; there are solutions by Brian D. Bundy, by Donald J. Newman, by W. McWorter, and by Jack Wert. Our solution is by Jack Wert and is a revised version of his solution at Cut The Knot!.