(thing) by /dev/joe Mon Apr 17 2000 at 0:59:14
Answer to old chestnut: twelve coins:

For the twelve coins, begin by weighing four coins against four other ones. There are two possible outcomes:

  1. These eight coins balance. This indicates that the bad coin is among the other four. In this case, proceed by weighing two of the other four (call them 1, 2) against a third (call it 3) of the other four and one known good coin. There are three possible outcomes:
    1. These coins balance. In this case, the one coin which has not been placed on the balance is the bad coin. Weigh it against a good coin to determine whether it is heavy or light.
    2. Coins 1 and 2 are heavier. In this case, we now know that either one of these two coins is heavy, coin 3 is light. Determine which by weighing coins 1 and 3 against two known good coins. The possible outcomes are:
      1. These coins balance. Coin 2 is bad and the second weighing tells us it is heavy.
      2. Coins 1 and 3 are heavier. Since coin 3 could only be bad by being light, we know coin 1 is bad, and it is heavy.
      3. Coins 1 and 3 are lighter. As above, coin 3 is bad and it is light.
    3. Coins 1 and 2 are lighter. This is the same as the previous case, but swap the words "heavy" and "light" throughout.
  2. The first eight coins do not balance. Call the four light ones a, b, c, d and the four heavy ones A, B, C, D. Weigh A, B, a against C, D, b. There are three possible outcomes:
    1. These coins balance. One of c and d must be bad. Weigh them against each other. The side that is lighter is the bad coin (which is of course light).
    2. A, B, a are heavier. Now we know that either A or B is heavy or b (on the other side of the balance) is light. Weigh A against B. If these balance, b is bad and light; else the heavier one of A and B is bad and heavy.
    3. C, D, b are heavier. Now we know that either C or D is heavy or a (on the other side of the balance) is light. Weigh C against D. If these balance, a is bad and light; else the heavier one of C and D is bad and heavy.
Now, if you have 13 coins plus a known good coin, follow the same steps as above, except weigh 5 coins vs. 5 coins at the beginning, including the known good coin as one of the ones weighed.
  1. If they balance, proceed exactly as above.
  2. If not, take note of whether the side with 5 unknown coins was heavy or light.
    1. If the side with 5 unknown coins was heavy, proceed as above and label the 5th possibly-heavy coin E. If you reach case 2-1, either c or d is light or E is heavy, and if c and d balance, E is bad and heavy.
    2. If the side with 5 unknown coins was light, proceed as in case 2 above but swap "heavy" and "light" throughout (so a, b, c, d are the heavy coins). Label the 5th light coin E. If you reach case 2-1, either c or d is heavy or E is light, and if c and d balance, E is bad and light.

I like it!