12 coins problem

This problem is originally stated as:

You have a balance scale and 12 coins, 1 of which is counterfeit. The counterfeit weigh less or more than the other coins. Can you determine the counterfeit in 3 weightings, and tell if it is heavier or lighter? A harder and more general problem is:

The solution for 3 coins

For n = 2, there are 3 coins, the weighings are:

    1 against 2
    1 against 3

Both of these can have three outcomes: fall to the left (l), fall to the right (r), or balance (b). The following table gives the answer for each of these outcomes:

  outcome  fake coin:
-----------------------
   l l     1 too heavy
   l b     2 too light
   l r     (not possible)
   b l     3 too light
   b b     no fake coin
   b r     3 too heavy
   r l     (not possible)
   r b     2 too heavy
   r r     1 too light

The solution for 12 coins

Now, what to do for n = 3. We replace coin c by coins 3c-2, 3c-1 and 3c If we do the experiments:

   1 2 3  against  4 5 6
   1 2 3  against  7 8 9

We know which group of three coins ({1,2,3}, {4,5,6} and {7,8,9}) contains the fake coin (if there is one) and whether it is heavier or lighter. By means of a simple weighing, we can determine which one is the fake coin, by putting one coin of each group on the left, and one the right:

   1 4 7  against  2 5 8

But 9 is three smaller then 12 (= (3^3 - 3)/2). We note however that the outcomes `l r' and `r l' are not possible in the above table. The idea is to use this, by adding another 3 coins to our weighings:

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

We give the table, with only those outcomes for these weightings, that start with `l r', `r l' and `b b' (as all other cases already have been dealt with):

  outcome  fake coin:
-----------------------
   l r l       10 too heavy
   l r b       11 too light
   l r r     (not possible)
   b b l       12 too light
   b b b       no fake coin
   b b r       12 too heavy 
   r l l     (not possible)   
   r l b       11 too heavy
   r l r       10 too light

Intermezzo

Another, interesting weighing schema is:

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

for which outcomes `l l l' and `r r r' are not possible. This is a rather symmetric solution.

Open question: how many weighing schema are there? (should be a multiple of 12!, I suspect)

The solution for 39 (and more) coins

Now, what for the case n = 4. Again we replace coin c by coins 3c-2, 3c-1 and 3c, resulting in 36 coins, which is 3 less (4^3 - 3)/2 (= 39). Again we notice that two outcomes are not possible `l r r' and `r l l'. So, again we can add 3 coins, resulting in the weighings:

 ........... 37  against ........... 38
 ........... 38  against ........... 37
 ........... 38  against ........... 37
 1 4 7 .. 34 38  against 2 5 8 .. 35 39

The dots of the first 3 three weighings are filled in using the weighings for n = 3 (where coin c is replaced by 3c-2, 3c-1 and 3c). Notice that we have placed 37 and 38 according to the patrons `l r r' and `r l l' respectively. If we write out the complete table, there will be again two impossible answers.

This proves there can be a weighing strategy for any n > 1, by step-wise induction.

Alternative solution

Martin Gardner gave a neat solution to this problem.

Tom Maglierygry has a 12-coins page, which prints this solution for n up to 6.

Another alternative solution by Frank Cole

Probably in the early 60's, we enjoyed a pre-determined solution which enabled mental calculation of the result; pre-determined in the sense that the 3 set-ups are in writing before any weighings, thus eliminating adjustments at weighings II and III. In addition, once the 3 set-ups are written and the 3 weighings are done, one can orally and immediately announce the number of the odd ball and whether it is light or heavy. The derivation is readily extendable to any number of weighings (>= 2) and the appropriate number (>= 3) of balls.

              Left Pan    Right Pan
Weighing I    4 8 10 11   1 2 5 7
Weighing II   2 4 7 12    3 5 6 11
Weighing III  5 6 10 12   7 8 9 11

Start with a Sum = 0 in the mind. Perform the 3 weighings, observing the tilt, if any.

Weighing I:   Add -1 if tilt is left pan down, +1 if tilt is left pan up.
Weighing II:  Add -3 if tilt is left pan down, +3 if tilt is left pan up.
Weighing III: Add -9 if tilt is left pan down, +9 if tilt is left pan up.

The number of the odd ball is the absolute value of Sum, and it is light or heavy depending on its appearance on the light or heavy side.

Yet another alternative solution by Barry Wolk

His solution uses letters (the letters A, C, D, E, F, I, K, L, N, M, O, and T) instead of numbers:

weigh  MADO versus LIKE
weigh  METO versus FIND
weigh  FAKE versus COIN

Variations

The following variations were posted by Marge to rec.puzzles:

You have a balance scale and 13 coins, 2 of which are counterfeit. The counterfeits weigh the same as each other, but are lighter than the rest. Can you determine the counterfeits in 4 weighings? Here's another:

You have a balance scale and 16 coins, 2 of which are counterfeit. The counterfeits weigh the same as each other, but this time you don't know whether they're light or heavy. Can you determine the counterfeits (as well as their comparative weight) in 5 weighings?

Bennet Haselton has an interesting "http://www.peacefire.org/staff/bennett/coins.html" page about the following variation: You have a balance scale and 13 coins, 1 of which are counterfeit. The counterfeit weigh less or more than the other coins. Can you determine the counterfeit in 3 weightings, if you do not have determine whether it is heavier or lighter? Back to my hacker page