Answer to April 8, 2002 Problem
by Michael Stueben
from Twenty Years Before The Blackboard

The Coin Problem

You have 64 coins, all of which appear identical. However, one of the coins is heavier than the others.

Using a two-pan balance, what is the least number of weighings that you need (in the worst case) to determine the false coin? Explain your process.

Solution:

You need only four weighings.

This proved to be a challenging problem. Most people sent in six for the solution because they divided the coins into two groups of 32.

To solve this in only four weighings,
Divide the coins into groups of 21, 21, and 22 coins.
Weigh the two groups of 21.
If one pan dips, then the false coin must be in that pan.
If the two pans balance, then the false coin must be in the group of 22.
Take the group with the heavier coin and split into 3 groups: 7, 7, and 8 (or 7).

Weigh two groups of 7. If they balance, the false coin is in the other group. If the pan dips, the false coin is in that group of coins.

Take the group of 7 (or 8) coins and split into three groups of 2, 2, and 3 (or 2, 3, and 3). Weigh the two equal groups of coins. If they balance, the false coin is in the other group. If the pan dips, the false coin is in that group.

You are now left with only 2 or 3 coins. Weigh two of them to determine the false coin.

Richard Johnson, Keith Mealy, and David and Judy Dixon all wrote to say that you can solve for up to 81 coins using the same method.

Split into 3 equal piles - 27, 27, 27 = 81
Weigh pile 1 vs. 2
Select the heavier or pile 3 if even.
Split into 3 equal piles - 9, 9, 9 = 27
Weigh pile 1 vs. 2
Select the heavier or pile 3 if even.
Split into 3 equal piles - 3, 3, 3 = 9
Weigh pile 1 vs. 2
Select the heavier or pile 3 if even.
Split into 3 equal piles - 1, 1, 1 = 3
Weigh pile 1 vs. 2
Select the heavier or pile 3 if even.



Correctly solved by:

1. Richard Johnson La Jolla, California
2. Keith Mealy Cincinnati, Ohio
3. Nick von Keller Winchester, Virginia
4. David & Judy Dixon Bennettsville, South Carolina
5. David Stark Winchester, Virginia
6. George Gaither Winchester, Virginia