lix. Bags of Coins in One Weighing

Problem. $n$ bags of coins; one bag contains only fakes, each 1 gram lighter. With one weighing on a scale that shows the weight, find the fake bag.

Solution: take $i$ coins from bag $i$ ($i=\mathrm{1..}n$) and weigh them together; the deficit from the expected weight is the index of the fake bag.

int fakeBag(int n, int good, function<long long(vector<int>)> weigh) {   // fake coins weigh good - 1; one weighing
    vector<int> take(n); for (int i = 0; i < n; i++) take[i] = i + 1;         // i + 1 coins from bag i
    long long expected = (long long)good * n * (n + 1) / 2;
    return (int)(expected - weigh(take)) - 1;                                 // deficit = index + 1
}

Proof: the deficit identifies the bag

The expected weight with all genuine coins is $g{\sum }_{i=1}^{n}i$. If bag $j$ is fake, the $j$ coins taken from it each weigh one gram less, so the measured weight is exactly $j$ grams lighter. Different bags give different deficits, so the bag is determined. Variant: if any number of bags may be fake, take $2^{i-1}$ coins from bag $i$; the deficit’s binary representation lists the fake bags. Checked for every fake bag with $n\le 15$.

Related: Counterfeit Coin.