Odd Marble Out with 12 and a Scale

This classic brain teaser asks the candidate to identify an anomalous marble using a limited number of weighings on a balance scale. The twist is that the odd marble might be heavier or lighter, and this is unknown at the start. The task is to design a small sequence of weighings such that, whatever the outcomes, one can always pinpoint the unique odd marble and determine in which direction it differs. Variants of this puzzle appear in logic interviews and high-end tech or quant screening, where the focus is less on mechanical calculation and more on structuring a constrained search.

Answering it well relies on combinatorial reasoning, information theory intuition, and constructing a decision tree with ternary outcomes. Strong solutions show careful partitioning of possibilities, symmetric design of weighings, and explicit tracking of which marbles could still be heavy or light after each step. Interviewers look for systematic reasoning rather than guesswork, the ability to map outcomes to remaining states, and awareness of edge cases that might break a naïve weighing plan.

What it tests

This problem class is governed by the principle of information maximization through partitioning and outcome mapping. Each weighing on a balance scale with three possible outcomes (left heavier, right heavier, or balanced) can distinguish among three states, so $k$ weighings can distinguish among $3^k$ possibilities. The challenge is to design weighings so that, regardless of the outcome at each step, the set of remaining candidates and their possible statuses (heavier or lighter) is reduced as efficiently as possible. This requires careful initial partitioning and strategic reassignment of marbles between weighings to ensure that every possible outcome leads to a unique identification path. The underlying structure is not about the objects themselves, but about encoding and decoding information through the outcomes of each weighing, treating the problem as a search through a decision tree with branching factor three.