Four Weighings, Heavy or Light

Worked solution

The answer is 39. **A useful fact.** Suppose $m$ suspects remain whose direction is unknown, a genuine coin is available, and $w$ weighings are left. Each suspect still carries two hypotheses (heavy or light), and every hypothesis needs its own outcome sequence, so $2m \le 3^w$. For $w = 3$ this gives $m \le 13$. Likewise, $s$ suspects whose direction is known need $s \le 3^w$. **40 coins are too many.** The first weighing must be $k$ coins against $k$, since there is no genuine coin to pad with. If it tips, all $2k$ weighed coins are suspects of known direction (the coins on the heavy pan can only be heavy, those on the light pan only light), so $2k \le 27$, i.e. $k \le 13$. If it balances, the $40 - 2k$ unweighed coins are suspects of unknown direction, so $40 - 2k \le 13$, i.e. $k \ge 14$. Both cannot hold, so 40 coins (and any larger number) cannot be guaranteed. A crude count already gives at most $(3^4 - 1)/2 = 40$; it is the forced equal split of the first weighing that costs the fortieth coin. **A strategy for 39.** Weigh 13 against 13. *Balanced:* the 13 unweighed coins are suspects, and 26 genuine coins are now available. Weigh 5 suspects against 4 suspects plus 1 genuine. If this balances, 4 suspects remain: weigh 2 of them against 1 suspect plus 1 genuine; a balance leaves one suspect, whose direction one weighing against a genuine coin reveals, and a tip leaves 3 suspects of known direction, settled by one more weighing. If instead the 5-against-4 weighing tips, we have 9 suspects of known direction for 2 weighings, handled as below. *Tipped:* say the left pan is heavy. Then the 13 left coins are heavy-suspects, the 13 right coins light-suspects, and the 13 unweighed coins are genuine. Put 5 heavy-suspects and 5 light-suspects on the left, and 4 heavy-suspects, 4 light-suspects and 2 genuine coins on the right. Left heavy leaves the 5 left heavy-suspects and 4 right light-suspects (9 coins); right heavy leaves 4 heavy and 5 light (9 coins); a balance leaves the 4 heavy and 4 light suspects left off (8 coins). *Nine (or fewer) suspects of known direction in two weighings:* split them into three groups of at most 3, arranged so that each group is one outcome of the next weighing (heavy-suspects on the left pan and light-suspects on the right pan point to "left heavy", and so on, padding with genuine coins). Three suspects of known direction are then separated by a single weighing: for two heavy-suspects and a light-suspect, weigh the two heavy-suspects against each other; the heavier one is counterfeit, and a balance points to the light-suspect. Every branch uses at most four weighings and names the coin together with its direction, so 39 is the maximum.