Name the Odd Coin

Worked solution

The answer is 13. **Upper bound.** Let R(w) be the largest pool of coins of unknown direction that w weighings can settle when a genuine spare coin is available (we only need the coin's name). In the tipped branch of the first weighing every remaining suspect has a known direction, so each needs its own outcome among the 3^(w-1) left, and in the balanced branch the unweighed coins form a smaller pool of the same kind, so R(w) = 3^(w-1) + R(w-1) with R(0) = 1. This gives R = 1, 2, 5, 14. Now suppose N = 14 and the first weighing puts k coins on each pan. If the pans balance, the 14 - 2k unweighed coins must fit a two-weighing pool, so 14 - 2k ≤ 5 and k ≥ 5. If the pans tip, all 2k weighed coins are suspects of known direction and need distinct outcomes among 9, so 2k ≤ 9 and k ≤ 4. These conflict, so 14 coins cannot be handled; an exhaustive search over coin-class states agrees. **Strategy for 13.** Weigh 4 against 4. If balanced, the 5 unweighed coins are the suspects and 8 genuine coins are available, which fits the 5-coin pool for two weighings. If the pans tip, the 4 coins on the low pan are heavy suspects, the 4 on the high pan are light suspects, and the other 5 coins are genuine. Weigh two heavy suspects and one light suspect against two other heavy suspects and one other light suspect: each outcome leaves at most 3 suspects, which a final weighing separates. The answer is 13.