Puzzles/Decision puzzles/12 Coins/Solution

Puzzles |Decision puzzles|12 Coins|Solution

You need 3 weighings.

There are 12 possible places for the fake coin to be and it can either be heavy or light, leaving 24 possibilities. Each weighing can give 3 results. (One side heavier, other side heavier, or both sides equal.) 2 weighings can at most only differentiate between 9 possibilities, therefore 2 or less weighings is not sufficient.

Label the coins with the symbols αβγδABCD$£€¤. Start at state S00.

State | Weighings | Pile L | Pile R | if L<R   | if L=R   | if L>R   | Candidates in
      |    left   |        |        |          |          |          |  αβγδABCD$£€¤
 S00  |  3        | αβγδ   | ABCD   | goto S01 | goto S02 | goto S03 |  ????????????
 S01  |  2        | αβC    | Bγδ    | goto S04 | goto S05 | goto S06 |  LLLLHHHH    
 S02  |  2        | αβγ    | $£€    | goto S07 | goto S08 | goto S09 |          ????
 S03  |  2        | αβC    | Bγδ    | goto S10 | goto S11 | goto S12 |  HHHHLLLL    
 S04  |  1        | α      | β      | α light  | B heavy  | β light  |  LL   H      
 S05  |  1        | A      | D      | D heavy  |  error   | A heavy  |      H  H    
 S06  |  1        | γ      | δ      | γ light  | C heavy  | δ light  |    LL  H     
 S07  |  1        | $      | £      | £ heavy  | € heavy  | $ heavy  |          HHH 
 S08  |  1        | α      | ¤      | ¤ light  |  error   | ¤ heavy  |             ?
 S09  |  1        | $      | £      | $ light  | € light  | £ light  |          LLL 
 S10  |  1        | γ      | δ      | δ heavy  | C light  | γ heavy  |    HH  L     
 S11  |  1        | A      | D      | A light  |  error   | D light  |      L  L    
 S12  |  1        | α      | β      | β heavy  | B light  | α heavy  |  HH   L

Reasoning

Since one of the coin is fake, and it can be lighter or heavier, that gives 2 X 12 = 24 possible answers. Also notice that each weighing can have 3 possible outcomes (left lighter, right lighter, equal), and with 3 weighting there are 3³ = 27 possible outcome. Because 27 > 24, it is possible (although not certainly) to have a solution.

First weighing

Suppose we put x coins on both side of the weigh, we want to ensure that no matter what the outcome is, the remaining case still satisfy the condition of possible outcomes > possible answers, otherwise the plan fails. In case the result is equal, only the coins not on weigh can be faked, since we don't know yet whether it is lighter or heavier, that leaves 2(12-2x) possible answers. With 2 weighing lefts, there are 3² = 9 possible outcomes. Hence 2(12-2x)<9. When one side is lighter, it can be that one of the coins on the lighter side is lighter, or one of the coins on the heavier side is heavier, which leaves 2x possible answers. Hence we have 2x<9. Solving the equation, we get x=4.