Adaptive Versus Pre-Committed Weighing Strategies

The classic "find the fake coin among 12 with a balance scale in 3 weighings" puzzle can be solved either adaptively — decide weighing 2 only after seeing the outcome of weighing 1 — or non-adaptively — write down all three weighings in advance, on paper, before doing any of them, and carry them out regardless of outcomes. Both approaches can solve the 12-coin puzzle in exactly 3 weighings. The natural assumption is that seeing results as you go must help; the surprising fact is that, for this particular puzzle, it doesn't need to — a full non-adaptive plan exists that's just as efficient.

The core idea: how much does feedback actually buy you?

Each weighing on a balance scale has three possible outcomes — left heavier, right heavier, balanced — so it can convey up to $\log_2 3 \approx 1.585$ bits of information. With $n$ weighings, an adaptive strategy can in principle extract up to $n \log_2 3$ bits total, choosing each next weighing to squeeze the maximum information out of whatever's still ambiguous. A non-adaptive strategy commits to all its "questions" up front, so it can't react to a lucky or unlucky outcome mid-way — but it can still be designed so that every possible sequence of outcomes maps to a distinct answer, using the full combinatorial structure of the coins across all weighings simultaneously, rather than narrowing down one branch at a time.

Working example: comparing the two approaches on 12 coins, 1 weighing "ahead"

Adaptive approach. Weighing 1 splits the 12 coins into two groups of 4 on the scale (with 4 aside). If the scale balances, the fake is among the 4 set aside, and it's now a smaller subproblem for weighings 2 and 3. If it tips, the fake is among the 8 on the scale, and you know a candidate direction (heavier or lighter) for each. Each subsequent weighing is chosen by looking at this specific outcome and designing the next split around it.

Non-adaptive approach. Instead, assign every coin a fixed label describing what it does in each of the three weighings — for example, coin 1 is on the left pan in weighing 1, on the right pan in weighing 2, and set aside in weighing 3; coin 2 has a different fixed pattern; and so on for all 12 coins, with the patterns chosen so that every coin has a distinct "signature" across the three weighings, and no two coins share a signature or its heavy/light mirror image. All three weighings are then carried out exactly as planned, with no branching. Afterward, the sequence of three outcomes (left/right/balance, left/right/balance, left/right/balance) is looked up against the pre-assigned signatures — one, and only one, coin's signature matches, and its position in that signature tells you whether it's heavy or light. The information is extracted all at once from the joint pattern of three results rather than being carved off one weighing at a time.

Both use exactly 3 weighings because $3^3 = 27$ possible outcome sequences comfortably cover the $12 \times 2 = 24$ possibilities (12 coins, each could be heavy or light) that need to be distinguished — the non-adaptive plan is designed once, offline, to make that mapping work for every branch simultaneously.

What this means in practice

The adaptive/non-adaptive distinction is exactly the difference between a trading strategy that reacts tick-by-tick to fills and one that pre-commits to a fixed execution schedule (like a VWAP or TWAP slice plan) decided before the order starts working. Pre-committed schedules are auditable, easy to communicate, and immune to being gamed by someone watching your reactions — but they only match an adaptive strategy's efficiency when the schedule was designed with enough foresight to cover every branch, exactly as the coin-labelling trick does. When that foresight isn't possible — because the space of future outcomes is too large or open-ended to pre-plan for — adaptivity strictly wins, which is why most real execution algorithms are adaptive rather than fixed.