Friday, February 5, 2010

The Counterfeit Coin


One of twelve coins is counterfeit: it is either heavier or lighter than the rest. Is it possible to identify the counterfeit coin in three weighings on a beam balance?


Solution:

This solution is first presented by "BRIAN D. BUNDY":


We may label the coins 1, 2, ..., 12 so that we can distinguish between and identify them using these labels.

1.            1. Weigh 1, 2, 3, 4 against 5, 6, 7, 8.
  1. They balance, so 9, 10, 11, 12 contain the odd coin. Weigh 6, 7, 8 against 9, 10, 11.
    1. They balance, therefore 12 is the odd coin and so weigh 12 against any other to discover whether it is heavy or light.
    2. 9, 10, 11 are heavy and so they contain an odd heavy coin. Weigh 9 against 10. If they balance, 11 is the odd heavy coin, otherwise the heavier of 9 and 10 is the odd coin.
    3. If 9, 10, 11 are light, we use the same procedure to reach the same conclusion for the odd light coin.
  2. 5, 6, 7, 8 are heavy and so either they contain an odd heavy coin or 1, 2, 3, 4 contain an odd light coin. Weigh 1, 2, 5 against 3, 6, 10.
    1. They balance, so the odd coin is 4 (light) or 7 or 8 (heavy). Thus weigh 7 against 8. If they balance 4 is light, otherwise the heavier of 7 and 8 is the odd heavy coin.
    2. 3, 6, 10 are heavy, so the odd coin can be 6 (heavy) or 1 or 2 (light). Thus weigh 1 against 2. If they balance 6 is heavy, otherwise the lighter of 1 and 2 is the odd light coin.
    3. 3, 6, 10 are light, so the odd coin is 3 and light or 5 and heavy. We thus weigh 3 against 10. If they balance 5 is heavy, otherwise 3 is light.
  3. If 5, 6, 7, 8 are light we use a similar procedure to that in 2.

No comments:

Post a Comment