Odd Coin Among 90 in 5 Weighings

This puzzle considers a classic odd-coin and balance-scale setup, but scaled up to a large number of coins and paired with a monetary cost per weighing. The candidate must design a weighing algorithm that always identifies which coin is counterfeit and whether it is heavier or lighter, while controlling the worst-case expense. The twist is not just to show that it is possible, but to argue rigorously about the minimal number of weighings that guarantees success, and to translate that into a worst-case cost. Questions like this are common in algorithmic and general-quant interviews, where interviewers want to see structured reasoning under combinatorial constraints.

The solution leans heavily on information-theoretic and combinatorial counting ideas, especially ternary decision trees for a three-outcome scale. It requires understanding how different weighings partition the space of possibilities, and designing symmetric, reusable patterns of comparisons rather than ad hoc moves. An interviewer is watching for a candidate who can bound what is achievable, argue tightness of their bound, and then construct a strategy that actually attains it, all while keeping the reasoning clear, systematic, and free of unjustified leaps.

What it tests

The core structure in these problems is information-theoretic: each weighing on a balance scale with three possible outcomes (left heavier, right heavier, balance) can distinguish among three possibilities, so the process is governed by base-3 (ternary) branching. The maximum number of coins you can resolve in $k$ weighings is determined by the number of distinct outcome sequences, which is $3^k$, but since each coin could be heavier or lighter, the true capacity is $\frac{3^k-1}{2}$. The reason is that each outcome sequence must uniquely identify both the coin and whether it is heavier or lighter, and the balance outcome provides less information than a tilt. This principle holds because each weighing partitions the set of possibilities into three, and the problem is to maximize the number of coins you can distinguish given the number of weighings. The efficiency comes from maximizing the information gained per weighing, which is why ternary splits are optimal.