answer: twelve coins

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.

Alternate solution:

Here is an alternate solution I came up with, which is significantly different than /dev/joe's that I thought it worth-while to write it up. It is a far more "analytical thinking" solution, rather than a "lateral thinking" solution, but that's the kind of thinking I prefer, really. The advantage of my solution algorithm is that it does not require branching: all weighings can be planned in advance. First, here is the solution to the first problem, with 12 coins: if the coins are numbered from 1 to 12, the weighings should be

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

Do the analysis, and you will see that no two assignments of the fake coin (which one it is, and whether it is heavy or light) give the same set of results in the three weighings.

The key to designing the weighing schedule is to describe each coin by a signature triplet of numbers, one number for each weighing: -1 if the coin sits in the left-hand dish, +1 if it sits in the right-hand dish, or 0 if it is not weighed at this weighing. The designed schedule of weighings gives a definite answer if no two coins have the same signature nor have signatures that are the complements of each other (e.g. (-1,1,0) and (1,-1,0)). Also, no signature can be (0,0,0), since then we will have no information on whether the fake is heavy or light (though we will know whether it was the fake, by elimination).

There are 13 possible signatures if we avoid the zero-triplet and complements (there are 26 = 3^3 - 1 non-zero triplets in 13 complementary pairs), so it would seem we should be able to make a determination even with 13 coins, but there is an extra constraints to be considered. Every weighing should be balanced; i.e it should have the same number of coins on each side, or else it would always tip to the more numerous side, giving no information. Therefore, the sum of all the triplets should give the zero-triplet. However, there is no way to pick 13 complement-free triplets in a way that satisfies this constraint. The best we can do is 12. The weighings above come from picking the following signatures (+ stands for +1, - for -1):

1. 00-
2. 0-0
3. -00
4. 0++
5. +0+
6. ++0
7. 0-+
8. +0-
9. -+0
10. --+
11. -+-
12. +--

The extra triplet which we did not use (+++ or ---) will come in handy to solve the second part of the problem. Since we know that the guaranteed-genuine coin is genuine, we do not have to worry about its signature clashing with another coin's signature. Therefore, we will give the 13th coin the signature +++ and give the guaranteed-genuine coin the signature ---. Balance is preserved and the puzzle is solved.