Tough Puzzles to Start the School Year
Sept. 7, 2003 -- 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.
In fact, by reading off the possible ordered pairs of H's, L's, and E's, we can determine which of the coins is heavier: 4 if LH; 5 if LL; 6 if LE; 7 if EH; 8 if EL.
The 12 Coins Puzzle
The branching cases approach to the 12 coin problem in which the counterfeit coin may be either heavier or lighter than the other 11 coins is very difficult. (Try it.) In his novel approach to the puzzle, however, Newman demonstrates a natural and easy way to determine three nondependent weighings that work. One set that does the job for the 12 coin problem is the following: Number the coins from 1 to 12 and balance coins (1, 2, 3, 4) against (5, 6, 7, 8); coins (1, 8, 9, 11) against (3, 4, 5, 10); and coins (3, 7, 9, 12) against (1, 4, 6, 11).
If the three weighings result, respectively, in the left side of the balance being heavier, heavier, and lighter (HHL) than the right, then coin 1 is heavier than the others because it's the only one on the left side for the first two weighings and on the right for the third weighing. If the weighings result in the left side being lighter, lighter, and heavier (LLH) than the right, then coin 1 is lighter than the others.
Likewise, a result of HEE, means that coin 2 is heavier because it's the only one on the left side for the first weighing and missing from the next two weighings. A result of LEE means that coin 2 is lighter. For similar reasons a result of HLH means that coin 3 is heavier, whereas LHL means that coin 3 is lighter. For each of the twelve coins a particular sequence of H's, L's, and E's tells us if it is the counterfeit coin and whether it's heavier or lighter than the others.
If you're intrigued, you can explore this further or, as suggested, try to find one of the standard branching solutions to the 12 coins problem. On the other hand, if you have a headache already, you can always cheat and use a scale rather than a balance. Just weigh each of the 12 coins individually and get on with the new semester or job.
Professor of mathematics at Temple University and adjunct professor of journalism at Columbia University, John Allen Paulos is the author of several best-selling books, including Innumeracy, and the just released A Mathematician Plays the Stock Market. His Who’s Counting? column on ABCNEWS.com appears the first weekend of every month.