Four Weighings, Heavy or Light
A pile holds N identical-looking coins, exactly one of which is counterfeit; it is either heavier or lighter than a genuine coin, and you do not know which. You have a two-pan balance with no weights, no coin known to be genuine at the start, and at most four weighings. You must identify the counterfeit coin **and** determine whether it is heavy or light. What is the largest N for which a strategy is guaranteed to succeed?
Related problems & prerequisites
Worth solving first
- Name the Odd Coin 8.0/10
- A Thousand Bottles, Three Rounds 8.0/10
- The Twelve Balls 8.0/10
Source: Generalisation of the classic twelve-coin puzzle; the closed form (3^n - 3)/2 is due to Dyson (1946). Statement written for AxiomIQ.