The Counterfeit Coin Problem Revisited
Nathan Linial, Michael Tarsi · SIAM Journal on Computing · 1982
We find the optimal algorithm in the sense of average run time for the counterfeit coin problem: Given n coins, one of which is heavier or lighter than the rest. Using a balance scale, find the counterfeit coin and whether it is heavy or light. An interesting feature of the solution is that our algorithm is a straight line algorithm. We also find the optimal algorithm if a standard coin is available for the first weighing.