The Counterfeit Coin

The classic puzzle of the counterfeit coin has long served as a stiff test of one's reasoning power and ingenuity.

In its standard form, the problem concerns 12 coins identical in size, shape, and appearance. One coin, however, is counterfeit, having a slightly different weight than the other 11 coins. Using only a two-pan balance, what is the smallest number of weighings that would guarantee that you would find the counterfeit coin?

Tom Banchoff, the noted geometer at Brown University in Providence, R.I., recalls that he first came across the problem many years ago when he was in the seventh grade. An acquaintance told him about a variant of the puzzle that involves 12 billiard balls, one of which is either lighter or heavier than the rest. How can you find the "odd ball" in three weighings using just a balance scale?

Banchoff couldn't solve the puzzle right away. Three years later, inspired by a pattern on a stained-glass window, he found the answer. "It made me feel good to know that I could solve a problem that took a long time, [unlike] the usual problems that you can do either immediately or not at all," Banchoff says.

The problem of the counterfeit coin (or odd ball) has circulated in many guises over the years. I have seen versions involving 8, 10, 12, or 13 coins. In many cases, you also have to determine whether the counterfeit coin is lighter or heavier than the rest. Finding an algorithm to solve the general problem of determining the minimum number of weighings given m coins, one of which is counterfeit, is a popular computer programming exercise.

In the November 1997 College Mathematics Journal, Mario Martelli and Gerald Gannon of California State University, Fullerton address the following question: What is the largest number, m, of otherwise identical coins among which a single odd coin can be detected using a balance scale n times?

Suppose that the odd coin weighs less than the others. If there are three coins, you can find the light one by putting one coin on each side of the balance while holding the third. With four or more coins, one weighing isn't enough because two coins must be either held or set on both pans. Hence, the largest number of coins among which it is possible to detect the lighter one using the scale twice (n = 2) is 3^2. You place three coins on each pan and hold the remaining three. If neither pan rises, the coin is among the three in your hand. Otherwise, the pan that rises contains the light coin. In either case, a second round of weighing detects the counterfeit.

In general, 3^n is the largest number of coins among which a lighter one can be detected using the balance n times.

Martelli and Gannon go on to demonstrate that, in general, n weighings are needed to detect the counterfeit one among (3^n - 3)/2 coins. For example, four weighings will detect the odd one among 39 coins. You divide 39 by 3 to get 13. Setting aside 13 coins, you divide the remaining 26 equally between the two pans of the scale. If the pans remain level, the odd coin is among the 13 set aside.

You can then choose a test coin of the correct weight from the 26 coins that balanced. To find the odd one among the remaining 13 coins, set aside four, put five on the left pan and the other four together with the test coin on the right pan. Suppose the right side is lighter. Taking away the test coin, the odd coin is either among the five on the left (heavier) or the four on the right (lighter).

With two more tries, it's possible to detect the counterfeit coin and determine whether it is lighter or heavier than the others. Call the five coins on the left "red" and the four on the right "black." Set aside one red coin and two black coins, leaving four red and two black for the balance. Put two red and a black on each pan. If the right rises, the counterfeit coin is among the two red on the left or it is the black on the right.

With just three coins, two red and one black, just put a red on each pan and keep the black in your hand. Whatever the outcome of the weighing, you can pick out the counterfeit.

Variations of that method produce the required result in the other possible cases.

Martelli and Gannon note that their approach "demonstrates the strategic value of the old principle divide et impera: to solve a difficult problem, break it into simpler problems."

References:

Albers, Donald J. 1996. Tom Banchoff: Multidimensional mathematician. Math Horizons (February):18-22.

Martelli, Mario, and Gerald Gannon. 1997. Weighing coins: Divide and conquer to detect a counterfeit. College Mathematics Journal 28(November):365-367.

Comments are welcome. Please send messages to Ivars Peterson at ipeterson@maa.org.