12 pennies

Here are two ways to do the 12 pennies problem. The first is mathematically more elegant; the second is procedurally more elegant.

1. This is the elegant (but tedious) mathematics approach. Consider the numbers 0, 1, …, 12 expressed in ternary notation.

 0. 0 0 0
 1. 0 0 1
 2. 0 0 2
 3. 0 1 0
 4. 0 1 1
 5. 0 1 2
 6. 0 2 0
 7. 0 2 1
 8. 0 2 2
 9. 1 0 0
10. 1 0 1
11. 1 0 2
12. 1 1 0

Now, replace the digits with L, N, R (for left pan, no pans, and right pan).

 0. L L L
 1. L L N
 2. L L R
 3. L N L
 4. L N N
 5. L N R
 6. L R L
 7. L R N
 8. L R R
 9. N L L
10. N L N
11. N L R
12. N N L

The basic idea is to use each of the three weighings to determine one of the three digits of the bad coin. To follow that strategy blindly we would do the following weighings.

1. 0, 1, 2, 3, 4, 5, 6, 7, 8 - <empty>
2. 0, 1, 2, 9, 10, 11        - 6, 7, 8
3. 0, 3, 6, 9, 12            - 2, 5, 8, 11

If we could do these weighings, this would tell us the answer. If the results were, for example, L, R, R, (meaning that those sides went down on the three weighings) that would mean coin 8 is heavy. Of course we can’t do the weighings as indicated. The pans don’t have the same number of coins on each side. We’ll get to that in a minute.

Note that with 3 ternary digits, one can count from 0 .. 26. Since we are counting from 0 .. 12, there are 14 numbers that we aren’t using (13 .. 26). That also means that the complement of each number below 13 refers to a non-assigned number greater than 13. (Note L and R are complements. N is its own complement.) So let’s assign each of the unassigned numbers to the coin whose number is its complement. So R, L, L and L, R, R now both correspond to coin 8, for example, and the coin 7 corresponds to both L R N and R L N. So each coin now corresponds to two numbers, where each number is the complement of the other.

Now to fix up the weighings. We have to convert coins into their complements so that each weighing has 4 coins on each side. For the first weighing, since we have 9 coins, we have to throw one out. Since we started with 13 numbers (0 .. 12) let’s throw out coin 8, leaving 12 coins. Then lets complement coins 0, 1, 2, 7, and 12. When we complement coins we move them from one side of each weighing to the other. The result is as follows.

1. 3, 4, 5, 6     - 0’, 1’, 2’, 7’
2. 7’, 9, 10, 11  - 0’, 1’, 2’, 6,
3. 2’, 3, 6, 9    - 0’, 5, 11, 12’

With these weighings we can now determine the bad coin. Suppose coin 0 is heavy. Then the results will be R, R, R. Suppose coin 0 was light. The results will be L, L, L. In either case, L, L, L, and R, R, R correspond to coin 0. The same holds for any of the other coins.

2. This is the elegant procedural approach. In this approach we start with unlabelled coins and label them as we go along.

In the first weighing, weigh 4 coins against another 4 coins. There are two possibilities. The two pairs of 4 coins balance, in which case we mark each coin G for Good. Or the two pairs of coins don’t balance, in which case we mark the coins on the heavy side H for heavy and coins on the light side L for light.

Let’s continue with case 1: the original weighing balanced. Now weigh three of the unknown coins against 3 of the good coins. Again, there are two cases. The coins may balance, in which case the 4th unknown coin is now known to be bad. The coins may not balance, in which case one of the three previously unknown coins is bad. Mark those three coins H or L depending on whether they were heavy or light compared to the good coins. Now weigh one of those potentially bad coins against a second of them. If they do not balance, the coin that was consistent with its previous weighing is the bad coin. If they do balance, the unweighed bad coin is the bad coin.

Now to continue with case 2. Weigh 2 of the H coins and one of the L coins against the other 2 H coins and another L coin. If they balance, we know that one of the other 2 L coins is bad. Weigh them against each other. The one that is consistent is bad.

If the second weighing doesn’t balance, the bad coin is either one of the two consistent H coins or the consistent L coin. Weight the two consistent H coins against each other. If they balance the consistent L coin is bad. If they don’t balance, the consistent H coin is bad.