Solution to "Find the fake coin"

See the original puzzle

Reader DeralterChemiker was able to solve the first problem:

Take any three coins and weigh them against any other three coins. If they weigh the same, the heavy coin is one of the other two; weigh those two coins against each other, and the heavier coin will be identified.

If one set of three coins is heavier than the other, take two coins from the heavier set and weigh them against each other. If one of those is heavier than the other, the heavy coin has been identified. If those two coins weigh the same, the heavy coin is the third coin from that set of three.

And Secret Squïrrel solved the second problem:

Ok, the bonus problem requires a bit more work and a more elaborate decision tree but I'll try to be as succinct as I can. I'll label the coins with letters (A to L) so they don't get confused with my numbering of the steps.

Step 1. Weigh any four coins against any other four, say ABCD - EFGH. The three possible results are: (a) balance, (b) ABCD is heavier, (c) EFGH is heavier.

(a) If they balance, then the fake coin must be one of the others (IJKL). Go to Step 2.1.

OR

(b) If ABCD is heavier, then either one of ABCD is fake and it's heavy OR one of EFGH is fake and it's light. Go to Step 2.2.

OR

(c) If EFGH is heavier, then either one of ABCD is fake and it's light OR one of EFGH is fake and it's heavy. Go to Step 2.3.

Step 2.1. (ABCD balanced EFGH).
Now weigh three known genuine coins (say ABC) against IJK. The three possible results are (a) balance, (b) ABC is heavier, (c) IJK is heavier.

(a) If they balance then L must be the fake. For your 3rd weighing, weigh it against any other coin to see whether it's heavy or light. DONE.

OR

(b) If ABC is heavier then one of IJK is the fake and it's light. For your 3rd weighing, weigh two of them against each other (say I - J). If one of them is lighter then that is the fake, otherwise it is the other one (K) and it's lighter. DONE.

OR

(c) Very similar to (a), if IJK is heavier then one of IJK is the fake and it's heavy. For your 3rd weighing, weigh two of them against each other (say I - J). If one of them is heavier then that is the fake, otherwise it is the other one (K) and it's heavier. DONE.

Step 2.2. (ABCD heavier than EFGH).
Weigh two coins from each group against one from each group plus two known genuine coins; eg IJKL are known to be not fake so weigh ABEF against CGIJ. The three possible results are (a) balance, (b) ABEF is heavier, (c) CGIJ is heavier.

(a) If they balance then the fake is one of the others, either D (and it's heavy) or H (light). For your 3rd weighing, weigh DH against IJ. If DH is heavier then D is the fake, if lighter then H is the fake. DONE.

OR

(b) If ABEF is heavier then either A or B are fake and heavy or G is fake and light. For your 3rd weighing, weigh A against B to see if one of them is the fake. If they balance then G is fake. DONE.

OR

(c) If CGIJ is heavier then either E or F are fake and light or C is fake and heavy. For your 3rd weighing, weigh E against F to see if one of them is the fake. If they balance then C is fake. DONE.

Step 2.3. (EFGH heavier than ABCD).
Perform the same weighing as for step 2.2 - weigh ABEF against CGIJ (IJ known to be genuine). The same three possible results are (a) balance, (b) ABEF is heavier, (c) CGIJ is heavier (however, the implications of these results are different from 2.2).

(a) If they balance then the fake is one of the others, either D (and it's light) or H (heavy). For your 3rd weighing, weigh DH against IJ. If DH is heavier then H is the fake, if lighter then D is the fake. DONE.

OR

(b) If ABEF is heavier then either E or F are fake and heavy or C is fake and light. For your 3rd weighing, weigh E against F to see if one of them is the fake. If they balance then C is fake. DONE.

OR

(c) If CGIJ is heavier then either A or B are fake and light or G is fake and heavy. For your 3rd weighing, weigh A against B to see if one of them is the fake. If they balance then G is fake. DONE.

If I may offer a more general tip relating to this sort of weighing problem...

It is useful to think of the problem in terms of information and possibilities. Think about how many possibilities you need to distinguish. In the first problem, there are 8 possibilities, because the fake coin can be any one of 8. In the second problem, there are 24 possibilities, since there are 12 coins which could be fake, and the fake coin could either be lighter or heavier. Every time you use the scale, there are three possible results: tilt left, tilt right, or balance. By observing the result, you have received a piece of information, basically a 0, 1, or 2.

With two weighings, you can distinguish between up to 9 possibilities. With three, you can distinguish between up to 27 possibilities.

What would have happened if, in the second problem, you tried weighing three against three instead of four against four? If the scale tilted left or right, then 6 possibilities would remain. If the scale balanced, then 12 possibilities would remain. Since you can only use the scale two more times, it is impossible to distinguish between all 12 of these possibilities. So you know you were on the wrong track.

Trial and error should get you the rest of the way.