School begins this month and so a well-known puzzle with a surprising new solution may be a good way to adjust to the beginning of the semester. And it's not just schools that put a premium on puzzle-solving. A recent book by William Poundstone, How Would You Move Mount Fuji?, discusses the increasing use of puzzles during employment interviews at high-tech companies and elsewhere.
The classic puzzle, which has given headaches to countless math students, involves 12 coins, one of which is slightly heavier or lighter than the other 11. By using a simple balance just three times, how can you determine the counterfeit coin and whether it is heavier or lighter than the others? (The balance tells you which of two quantities is heavier, but doesn't specify their weights.)
A Simpler Puzzle
Let me begin with a related, but simpler puzzle that Poundstone includes in his book. It involves only eight coins, one of which you know to be slightly heavier than the other seven. By using a simple balance just twice, how can you determine the counterfeit coin? (Try it before reading on.)
The standard approach to the problem goes something like the following:
Separate the eight coins into three groups containing three, three, and two coins, respectively, and call these groups 1, 2, and 3. Begin by balancing the coins in group 1 against those in group 2.
Case 1.1: If the coins from group 1 and 2 balance, then the counterfeit coin is in group 3.
Case 1.2: Balance the two coins in group 3 against each other to determine which is heavier.
Case 2.1: If the coins from group 1 weigh more than the coins from group 2, then the counterfeit coin is in group 1.
Case 2.2: Choose any two coins from group 1 and balance them against each other. Whichever is the heavier is the counterfeit coin.
Case 2.3: If they balance, the last coin from group 1 is the counterfeit.
Case 3: If the coins from group 2 weigh more than the coins from group 1, the case is analyzed in the same way as case 2.
A Different Solution
This approach via branching cases is fine for this problem, but as my former colleague, Donald J. Newman, has stressed, there should be an approach in which the second weighing is not dependent on the outcome of the first. That there is such a solution follows from the fact that the left side of the balance can be heavier (H), lighter (L), or equal (E) in weight to the right side. Since there are three possibilities for each of the two weighings, there are nine discriminations (3 x 3) possible, enough to determine which of the eight coins is heavier.
First let's number the coins from 1 to 8 to help us describe a pair of weighings that work. In the first weighing, balance coins (1, 2, 3) on the left against coins (4, 5, 6) on the right. Whatever the outcome, in the second weighing balance coins (1, 4, 7) against (2, 5, 8). That's it.
If the left side of the balance is heavier for both weighings (HH), then coin 1 is the heavier coin because it's the only one on the left side for both weighings. If the left side is heavier for the first weighing, but lighter for the second (HL), then coin 2 is the heavier coin because it's the only one that's on the left side for the first weighing and the right side for the second. If the left side is heavier for the first weighing and equal in weight for the second, then coin 3 is the heavier coin for similar reasons.