From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search

Question: You are given 12 coins. One of them is heavier or lighter than the rest. Identify this coin in just three weighings

Solution: Number the coins 1 through 12 and divide them coins into 4 sets of 3...

There are multiple comparison sets possible. This is an acceptable template to find a few of them. (This template is NOT definitive, there are other solutions that don't follow this template)

Compare   (set 1 & 1st coin from set 4)  against  (set 2 + 2nd coin from set 4)
Compare   (set 1 & 2nd coin from set 4)  against  (set 3 + 1st coin from set 4)
Compare   (1st coin from each set)       against  (3rd coin from each set)

A more concise example:

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

Each weighing can have 3 possible outcomes: Left Heavy, Right Heavy, or Balanced (L,R or B)

Build a truth table to interpret outcomes...many outcomes are not possible. Note: THE TABLE VALUES ARE DERIVED FROM THE CHOSEN COMPARISON SETS!

outcome:    fake coin:
l l l       1 is heavy
r r r       1 is light
l l b       2 is heavy
r r b       2 is light
l l r       3 is heavy
r r l       3 is light
r b l       4 is heavy
l b r       4 is light
r b b       5 is heavy
l b b       5 is light
r b r       6 is heavy
l b l       6 is light
b r l       7 is heavy
b l r       7 is light
b r b       8 is heavy
b l b       8 is light
b r r       9 is heavy 
b l l       9 is light
r l r       10 is heavy
l r l       10 is light
l r b       11 is heavy
r l b       11 is light
b b r       12 is heavy
b b l       12 is light 

There are multiple comparison set possibilities, each with their own comparison table solution.

A simpler solution #2:

  • put 6 coins on each side of the scale, one side will be heavier.
  • use the heavier side from the first weighing and put 3 coins on each side of the scale.
  • using the heavier side from the 2nd weighing, pick 2 coins and put 1 on each side of the scale.

If the scale is balanced then the coin you didn't weigh is the heavier one. Otherwise, the scale will show which one of the other 2 is the heavy coin.

Since we do not know if the faulty coin is heavier or lighter , the soluition #2 is not correct

The only solution is solution nr 1, for which we can also use a binary tree

I found the explanation at mathforum.org/library/drmath/view/55618.html to be helpful. The key is to build a truth table, but how that table was built is a little tricky because you can't just write out all possible combinations of results and use that. I tried writing a truth table and found that I had to swap some values around to make sure that each measurement step had exactly 4 on each side.

Back to Chapter 4