Name the Odd Coin

A bag holds N visually identical coins. Exactly one is counterfeit; it is either slightly heavier or slightly lighter than the genuine coins, and you do not know which. You have a two-pan balance scale (no weights) and at most three weighings, and you have no coin known to be genuine. You must name the counterfeit coin; you do **not** need to say whether it is heavy or light. Each weighing places the same number of coins on each pan. What is the largest N for which a strategy is guaranteed to succeed?

• pigeonhole

Source: Classic family of balance-scale counterfeit-coin puzzles (Dyson's 1946 analysis of the twelve-coin case); no single originator. Statement written for AxiomIQ.