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:
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.
To see the solution, click HERE.
Copyright © 2000 by Jerry Avins