(idea) by colonelmustard Thu Jun 18 2009 at 18:40:56

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.

I like it!