12 Coins with 1 Defective of Unknown Weight in 3 Weighings

Scenario

You are given 12 visually identical coins numbered 1 to 12. Exactly one coin is counterfeit, but it is unknown whether the fake coin is heavier or lighter than the normal coins. You have an uncalibrated two-pan balance scale that shows only Left Pan Heavy, Right Pan Heavy, or Equal.

Your Task

1. State the information-theoretic capacity: With 12 coins and 2 potential states each (heavy or light), there are $24$ distinct possibilities. Three ternary weighings provide $3^3 = 27$ states.
2. Construct the weighing algorithm that identifies both the counterfeit coin and whether it is heavy or light in at most 3 weighings.
3. Implement the decision tree and verify that all 24 possible failure modes are correctly resolved.

Constraints

• Exactly 3 weighings maximum.
• Relative weight direction (heavy/light) must be determined.

Examples Weighing 1 compares {1, 2, 3, 4} vs {5, 6, 7, 8}. If balanced, fake is in {9, 10, 11, 12}.