Select Page

Finding the Counterfeit Coin

Mar 31, 2014

I wrote about a brain teaser I encountered as a kid and challenged you to figure out if it has a solution, and if so, what that solution is.

That brain teaser works like this:

You have 12 identical coins. One of them is counterfeit. The counterfeit coin may be heavier or lighter than the others. Using a simple balance scale, and in just 3 weighings, identify the counterfeit coin, and determine whether it is lighter or heavier than the others.

It’s a tricky problem, and I remember being stumped for a long time when I first encountered it as a kid. But it can be solved.

There are twenty-four possible cases. Our solution must uniquely identify each possible case.

Here is the solution.

We start by weighing coins 1,2,3 and 4 against coins 5,6,7, and 8:

  1. If 1,2,3,4 equal 5,6,7,8, then coins 1-8 are real. So we need to test 9-12 and can use 1-8 as controls.
    1. Weigh 9,10 vs. 11,1:
      1. If 9,10 is equal to 11,1, then coin 12 is the counterfeit.
        1. Weigh 12 vs 1:
          1. If 12 is heavier, then 12 is a Heavy Counterfeit
          2. If 12 is lighter, then 12 is a Light Counterfeit
      2. If 9,10 are lighter than 11,1, then either 9 or 10 is light, or 11 is heavy.
        1. Weigh 9,11 vs 1,2:
          1. If 9,11 is equal to 1,2, then 10 is a Light Counterfeit
          2. If 9,11 is heavier, then 11 is a Heavy Counterfeit
          3. If 9,11 is lighter, then 9 is a Light Counterfeit
      3. If 9,10 are heavier than 11,1, then either 9 or 10 is heavy, or 11 is light.
        1. Weigh 9,11 vs 1,2:
          1. If 9,11 is equal to 1,2, then 10 is a Heavy Counterfeit
          2. If 9,11 is heavier, then 9 is a Heavy Counterfeit
          3. If 9,11 is lighter, then 11 is a Light Counterfeit
  2. If 1,2,3,4 is heavier than 5,6,7,8, then coins 9-12 are real. We need to find the counterfeit among 1-8. Either one of 1,2,3,4 is a heavy counterfeit, or one of 5,6,7,8 is a light counterfeit.
    1. Weigh 1,2,5 vs 3,6,9:
      1. If 1,2,5 is equal to 3,6,9, then either 4 is heavy, or 7 or 8 is light
        1. Weigh 7 vs 8:
          1. If 7 equals 8, then 4 is a Heavy Counterfeit
          2. If 7 is heavier than 8, then 8 is a Light Counterfeit
          3. If 7 is lighter than 8, then 7 is a Light Counterfeit
      2. If 1,2,5 is heavier than 3,6,9, then either 1 or 2 is heavy, or 6 is light
        1. Weight 1 vs 2:
          1. If 1 equals 2, then 6 is a Light Counterfeit
          2. If 1 is heavier than 2, then 1 is a Heavy Counterfeit
          3. If 1 is lighter than 2, then 2 is a Heavy Counterfeit
      3. If 1,2,5 is lighter than 3,6,9, then either 5 is light, or 3 is heavy
        1. Weight 5 vs 9:
          1. If 5 equals 9, then 3 is a Heavy Counterfeit
          2. If 5 is lighter than 9, then 5 is a Light Counterfeit
  3. If 1,2,3,4 is lighter than 5,6,7,8, then coins 9-12 are real. We need to find the counterfeit among 1-8. Either one of 1,2,3,4 is a light counterfeit, or one of 5,6,7,8 is a heavy counterfeit.
    1. Weigh 1,2,5 vs 3,6,9:
      1. If 1,2,5 is equal to 3,6,9, then either 4 is light, or 7 or 8 is heavy
        1. Weigh 7 vs 8:
          1. If 7 equals 8, then 4 is a Light Counterfeit
          2. If 7 is heavier than 8, then 7 is a Heavy Counterfeit
          3. If 7 is lighter than 8, then 8 is a Heavy Counterfeit
      2. If 1,2,5 is heavier than 3,6,9, then either 5 is heavy, or 3 is light
        1. Weigh 5 vs 9:
          1. If 5 equals 9, then 3 is a Light Counterfeit
          2. If 5 is heavier than 9, then 5 is a Heavy Counterfeit
      3. If 1,2,5 is lighter than 3,6,9, then either 1 or 2 is light, or 6 is heavy
        1. Weigh 1 vs 2:
          1. If 1 equals 2, then 6 is a Heavy Counterfeit
          2. If 1 is heavier than 2, then 2 is a Light Counterfeit
          3. If 1 is lighter than 2, then 1 is a Light Counterfeit

And there you have it.