## The Twelve Coins, Revisited

by Jerry Avins

There is a relatively old puzzle that requires the solver to isolate a counterfeit coin from among 11 genuine ones, and to discover whether it is lighter or heavier than the others: it definitely differs in weight. Only three comparisons on an equal-arm balance are allowed, and no other weights are available. (When I first heard this puzzle in 1948 at MIT, it seemed new to that community.)

The problem is underconstrained: there is more than one distinct solution. All published solutions I know use decision trees: some coins are compared with an equal number of others, the outcome determining which coins are to be compared next or providing the answer. In the 1960s, Manny Greenblatt showed that the number of questionable coins can be thirteen if there is a fourteenth coin known to be genuine.

The solution sought here is different. The three comparisons are to be determined before any are carried out. A solution using a look-up table is feasable, but the one I give is computed. Moreover, it is permitted that there be no counterfeit at all.

To reiterate:

• All comparisons are to be specified before any are carried out.
• The comparisons so determined may be carried out in any order.
• While there remains at most one counterfeit, there may be none at all.

In other words, the the particular coins to be on each of the pans for each of the comparisons are already determined before any comparisons are made. Incidentally, my solution also accommodates Greenblatt's expansion.