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?

Need another hint? Click here.

Click here for the complete solution.