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
editSince 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 33 = 27 possible outcome. Because 27 > 24, it is possible (although not certainly) to have a solution.
First weighing
editSuppose 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 32 = 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.