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:

To experiment with this puzzle, you can try out the 12 coins puzzle game (made with Flash) which is (being) developed by Joseph Howard.

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) Answer.

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. Search for "logic/weighing/balance.s" in the puzzles FAQ.

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

Number of solutions

Jon Seymour thought about the question I stated in the intermezzo about how many solutions there are. He thought about this for a while and came to the conclusion that there is either 1, 5, 22, 176 or 84304281600 or 12!*176*(4!)^6 solutions to the problem, depending on what kinds of symmetries you care about.

The argument for 1 solution is that any valid solution has the following properties:

3 coins repeated in all 3 weighings (the triples)
3 coins unique to 3 distinct weighings (the singletons)
3 pairs of 2 coins, each pair of coins shared by a different pair of 2 weighings
each pair split by one weighing and joined by one weighing
3 coins appearing on the same side of a single weighing at most once
each weighing has 4 coins in each pan

Excluding mirror symmetries where the pans of each weighings are exchanged (a factor of 8) there are 5 distinct ways to choose coins from each of the triples, singletons and pairs. If each of these 5 ways of choosing is labeled, then there are 125 ways to choose 3 weighings, but of these only 22 are both distinct and valid and 17 of these are permutations of the other 5. If we allow all 22 variations and all 8 mirror symmetries there are 22 * 8 = 176 solutions for each partitioning of 12 coins into an ordered sets of triples, ordered set of singletons and ordered set of 3 ordered pairs.

There, are of course, 12! ways to partition 12 coins in that way. So, 12! * 22 * 8 = 84304281600 solutions, excluding the 4!^6 trivial variants of each solution generated simply by permuting the coins in each pan.

He wrote a tool in go that allows you to assign a unique number to each solution or given a solution derive a unique number for that solution. So, for example:

$ echo "0 1 4 10 16" | tr ' ' \\012 | ./tools/tools --decode

{"weighings":[[[1,4,10,11],[12,5,6,7]],[[2,6,11,12],[10,7,8,9]],[[3,8,12,10],[11,9,4,5]]],"unique":[1,2,3],"pairs":[[4,5],[6,7],[8,9]],"triples":[10,11,12],"structure":["p","p","p"],"S":0,"F":0,"P":[0,1,2,3,4,5,6,7,8,9,10,11],"N":0}

{"weighings":[[[10,11,12,4],[5,6,7,1]],[[2,6,11,12],[10,7,8,9]],[[3,8,12,10],[11,9,4,5]]],"unique":[1,2,3],"pairs":[[4,5],[6,7],[8,9]],"triples":[10,11,12],"structure":["q","p","p"],"S":1,"F":0,"P":[0,1,2,3,4,5,6,7,8,9,10,11],"N":1}

{"weighings":[[[1,4,10,11],[12,5,6,7]],[[11,12,6,8],[10,7,9,2]],[[12,10,4,5],[11,8,9,3]]],"unique":[1,2,3],"pairs":[[4,5],[6,7],[8,9]],"triples":[10,11,12],"structure":["p","r","s"],"S":4,"F":0,"P":[0,1,2,3,4,5,6,7,8,9,10,11],"N":4}

{"weighings":[[[1,4,10,11],[12,5,6,7]],[[11,12,6,8],[10,7,9,2]],[[12,10,11,3],[8,9,4,5]]],"unique":[1,2,3],"pairs":[[4,5],[6,7],[8,9]],"triples":[10,11,12],"structure":["p","r","t"],"S":10,"F":0,"P":[0,1,2,3,4,5,6,7,8,9,10,11],"N":10}

{"weighings":[[[10,11,12,4],[5,6,7,1]],[[11,12,6,8],[10,7,9,2]],[[12,10,4,5],[11,8,9,3]]],"unique":[1,2,3],"pairs":[[4,5],[6,7],[8,9]],"triples":[10,11,12],"structure":["q","r","s"],"S":16,"F":0,"P":[0,1,2,3,4,5,6,7,8,9,10,11],"N":16}

Yields 5 structurally distinct solutions where (1,2,3) are the singletons, ((4,5),(6,7),(8,9)) are the pairs and (10,11,12) are the triples.

While:

    cat examples/iwriteiam.json  | ./tools/tools --encode

shows that the numbers assigned to 2 of the solutions on this page are:

41981248865
45956768

{
"weighings":[
[[1,2,3,10], [4,5,6,11]],
[[1,2,3,11], [7,8,9,10]],
[[1,4,7,10], [2,5,8,12]]
]
}
{
"weighings":[
[[1,4,6,10],[5,7,9,12]],
[[2,5,4,11],[6,8,7,10]],
[[3,6,5,12],[4,9,8,11]]
]
}

For a more detailed description of the analyses, with some Venn-diagrams, see his code project on GitHub.

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 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