9 Coins with 1 Counterfeit in 2 Balance Weighings

Scenario

You are given 9 coins that are visually indistinguishable. Eight coins have identical normal weight $w$, and exactly one coin is counterfeit and strictly heavier than normal ($w + \delta$ with $\delta > 0$). You have access to an uncalibrated two-pan balance scale that indicates only whether the left pan is heavier, the right pan is heavier, or both pans are equal in weight.

Your Task

1. State the information-theoretic upper bound on the number of coins distinguishable in $k$ weighings on a balance scale.
2. Construct the ternary decision tree algorithm that guarantees identification of the heavy coin in at most 2 weighings.
3. Trace all possible weighing outcomes across the 9 candidate coin positions.

Constraints

• Exactly 2 weighings maximum.
• Counterfeit coin is known to be heavier.

Examples With $k=2$ weighings, each weighing has 3 outcomes, allowing identification of at most $3^2 = 9$ coins.