xii. Counterfeit Coin and 12 Coins

Problem. Among $n$ coins one is counterfeit. With a balance scale (left heavier / right heavier / equal), find it in as few weighings as possible.

Variant	Answer
fake is known to be heavier	$\lceil {\log }_{3}n\rceil$ weighings: split into three near-equal groups
fake heavier or lighter, must also tell which	$n\le \frac{3^w-3}{2}$ coins with $w$ weighings: 12 coins in 3, 39 in 4
fake heavier or lighter, one extra genuine coin available	$n\le \frac{3^w-1}{2}$: 13 coins in 3
non-adaptive (all weighings fixed in advance)	same bounds, via ternary codes with balanced columns
several fakes, or a scale that returns the weight difference	group testing / coin weighing with a spring scale (Lindström)

int heavyCoin(int n, function<int(vector<int>, vector<int>)> weigh) {   // weigh: -1 left heavier, 1 right heavier, 0 equal
    vector<int> c(n); iota(all(c), 0);
    while (sz(c) > 1) {                            // split into three near-equal groups; ceil(log3 n) weighings
        int t = (sz(c) + 2) / 3;
        vector<int> A(c.begin(), c.begin() + t), B(c.begin() + t, c.begin() + 2 * t), R(c.begin() + 2 * t, c.end());
        int r = weigh(A, B);
        c = r < 0 ? A : r > 0 ? B : R;
    }
    return c[0];
}

Proof: the bounds

Lower bound. A weighing has 3 outcomes, so $w$ weighings distinguish at most $3^w$ cases. With a known-heavy fake there are $n$ cases, so $w\ge \lceil {\log }_{3}n\rceil$, and splitting into groups of sizes $\lceil n/3\rceil ,\lceil n/3\rceil ,\text{rest}$ shrinks the candidates to at most $\lceil n/3\rceil$ each time (the two pans must have equal size, which the code keeps). Heavier or lighter. There are $2n$ cases; the outcome “all weighings balanced” cannot be used (it would identify no coin), and the first weighing must use the same number of coins on each pan, which loses one more case per symmetry; this gives $2n\le 3^w-3$. The classical 12-coin, 3-weighing solution: label the coins with the 12 ternary words of length 3 that are not constant, chosen so that each position has four coins on each pan; the outcome word identifies the coin and its sign. Tested: the heavy-coin search uses at most $\lceil {\log }_{3}n\rceil$ weighings for all $n\le 200$ and every fake position.