Why four weighings handle thirty-nine coins

Question

With one fake coin of unknown direction (heavier or lighter) among n coins, a balance and no reference coin, three weighings can handle 12 coins, identifying the fake and its direction. 1. How many coins can four weighings handle? 2. Derive the general formula for w weighings. 3. Describe the first weighing in the four-weighing case and check the branch sizes.

Accepted Answer

Four weighings handle 39 coins. In general, w weighings handle (3 to the w minus 3)/2 coins with no reference coin. The counting bound. With w weighings there are 3 to the w outcome sequences. One of them, "balanced every time", can only occur if the fake was never on the scale, and then its direction cannot be known, so that outcome is unusable for a full answer. Each remaining outcome sequence has a mirror image (swap the pans in every weighing), and the fake's two directions use up a mirror pair. So at most (3 to the w minus 1)/2 coins could ever be handled, and with no reference coin the …

Why four weighings handle thirty-nine coins

Your answer

Discussion

Learn the concepts

Related questions