Question

There are 12 coins before you, one of which is fake. The fake coin is either heavier than or lighter than the other 11 coins. The legitimate coins all weigh the same. You have a balance scale you can use to weigh the coins. You can use the scale at most three times. How do you find the fake coin?

Answer

Number the coins 1-12. Separate the coins into a pile of 1,2,3,4, a pile of 5,6,7,8, and a pile of 9,10,11,12. Let "f" denote the fake coin. Let the predicate "H" denote heavy and the predicate "L" denote light.

Weigh 1: 1,2,3,4 x 5,6,7,8. There are three possible outcomes:
Outcome I: 1,2,3,4 = 5,6,7,8. f is among 9,10,11,12.
Weigh 1.2: 1,9 x 10,11, where 1 is clearly not f. There are three possible outcomes:
Outcome I: 1,9 = 10,11. f is 12. DONE.
Outcome II: 1,9 > 10,11. Either H(9) or L(10) or L(11).
Weigh 1.2.3: 10 x 11. There are three possible outcomes:
Outcome I: 10 = 11. Then f is 9. DONE.
Outcome II: 10 > 11. Then f is 11. DONE.
Outcome III: 10 < 11. Then f is 10. DONE.
Outcome III: 1,9 < 10,11. Either L(9) or H(10) or H(11).
Weigh 1.2.3: 10 x 11. There are three possible outcomes:
Outcome I: 10 = 11. Then f is 9. DONE.
Outcome II: 10 > 11. Then f is 10. DONE.
Outcome III: 10 < 11. Then f is 11. DONE.
Outcome II: 1,2,3,4 > 5,6,7,8. f is either H(1), H(2), H(3), H(4), L(5), L(6), L(7), or L(8).
Weigh 1.2: 4,5,6,7 x 8,9,10,11. There are three possible outcomes:
Outcome I: 4,5,6,7 = 8,9,10,11. Then f is either H(1) or H(2) or H(3).
Weigh 1.2.3: 1 x 2. There are three possible outcomes:
Outcome I: 1 = 2. Then f is 3. DONE.
Outcome II: 1 > 2. Then f is 1. DONE.
Outcome III: 1 < 2. Then f is 2. DONE.
Outcome II: 4,5,6,7 > 8,9,10,11. Then f is either H(4) or L(8).
Weigh 1.2.3: 1 x 4. There are two possible outcomes:
Outcome I: 1 = 4. Then f is 8. DONE.
Outcome II: 1 < 4. Then f is 4. DONE.
Outcome III: 4,5,6,7 < 8,9,10,11. Then f is either L(5) or L(6) or L(7).
Weigh 1.2.3: 5 x 6. There are three possible outcomes:
Outcome I: 5 = 6. Then f is 7. DONE.
Outcome II: 5 < 6. Then f is 5. DONE.
Outcome III: 5 > 6. Then f is 6. DONE.
Outcome III: 1,2,3,4 < 5,6,7,8. f is either L(1), L(2), L(3), L(4), H(5), H(6), H(7), or H(8).
Weigh 1.2: 10,11,12,1 x 2,3,4,5. There are three possible outcomes:
Outcome I: 10,11,12,1 = 2,3,4,5. Then f is either H(6) or H(7) or H(8).
Weigh 1.2.3: 6 x 7. There are three possible outcomes:
Outcome I: 6 = 7. Then f is 8. DONE.
Outcome II: 6 > 7. Then f is 6. DONE.
Outcome III; 6 < 7. Then f is 7. DONE.
Outcome II: 10,11,12,1 > 2,3,4,5. Then f is either L(2) or L(3) or L(4).
Weigh 1.2.3: 2 x 3. There are three possible outcomes:
Outcome I: 2 = 3. Then f is 4. DONE.
Outcome II: 2 > 3. Then f is 3. DONE.
Outcome III: 2 < 3. Then f is 2. DONE.
Outcome III: 10,11,12,1 < 2,3,4,5. Then f is either L(1) or H(5).
Weigh 1.2.3: 1 x 4. There are two possible outcomes:
Outcome I: 1 = 4. Then f is 5. DONE.
Outcome II: 1 < 4. Then f is 1. DONE.