|
|
|
|
|
|
|
|
|
Weighing 12 coinsI thank W.McWorter for the following discussion. Here are two playful applications of numbers in the base 3 - also known as the ternary number system.
A preliminary answer might be 15, using counterweights of 1, 2, 4, and 8 ounces. However, if the counterweights are allowed to be placed on either pan, then the answer is 40, using weights of 1, 3, 9, and 27 ounces. (Ternary numbers with "digits" -1, 0, and 1) A problem with which I had a delicious struggle when I was an undergraduate is the famous Counterfeit Coin Problem:
After much struggle I came up with a solution in which I put coins on the pans of the balance for the next weighing based on the outcome of the previous weighing. It was a solution I had to keep on a sheet of paper because it was too hard to remember all the cases. Much later, while on the faculty at Ohio State, I heard that the graduate student Rick Wilson (of Lucky 7 fame) had discovered a solution of the Counterfeit Coin Problem based on the finite projective plane of order 3. His solution had the wonderful feature that what coins go on which pan does not depend on the outcome of any weighing; moreover, once the three weighings are completed, the counterfeit coin is immediately identified. I never wrote down Rick's solution (if I ever knew it) and some years later tried to rediscover it. I failed; but the following idea came to me. For each of the three weighings three things can happen; the left pan goes down, the right pan goes down, or the pans balance. With three weighings, that's 27 possible outcomes. Each possible outcome can be represented by an ordered triple ... or a three-digit number in base 3! If I can place the coins on the pans in the right way, the base 3 number representing the outcome of the three weighings would be the label of the counterfeit coin, and its sign, positive or negative, would tell me whether the counterfeit was lighter or heavier than the good coins! I organized things as follows. The first weighing would represent the nines place, the second weighing the threes place, and the final weighing the units place. I chose "the left pan goes down" to represent the digit 1 and "the right pan goes down" represents the digit -1. The digit 0 represents the pans balancing. Then I placed the 12 coins on the pans in such a way that, if any one of them turned out to be counterfeit and heavy, the outcome of the weighing would be a positive number in balanced ternary notation. Here is how the numbers are placed on the pans according to these rules.
Obviously this assignment of coins to pans cannot work because the number of coins per pan in the first two weighings are not equal. However, if we interpret the sign of the outcome for certain coins oppositely, we can insure that the coin assignment to the pans is four coins per pan. Accordingly, I chose to place the coins 7, 9, 11, and 12 to be placed so that the outcome weighing would have a sign opposite to the correct sign. This produced the assignment
For example, if the counterfeit coin is 6 and heavier than the other coins, then, in the first weighing, the left pan goes down, in the second weighing the right pan goes down, and in the last weighing the pans balance. This produces the base three number (1,-1,0)=9-3+0=6, indicating that the counterfeit coin is the sixth coin and it is heavier than the other coins because 6 is positive. If the counterfeit coin is 5 and lighter than the other coins, then, in the first weighing, the right pan goes down, in the second weighing the left pan goes down, and in the last weighing the left side goes down. This produces the base three number (-1,1,1)=-9+3+1=-5, indicating that the counterfeit coin is the fifth coin and it is lighter than the other coins. The coins 7, 9, 11, and 12 are treated oppositely. If the counterfeit coin is 7 and is heavier than the other coins, then, in the first weighing, the right pan goes down, in the second weighing the left pan goes down, and in the last weighing the right pan goes down. This produces the base three number (-1,1,-1)=-9+3-1=-7, indicating, for this special case, that the counterfeit coin is the seventh coin and it is heavy because we reverse the sign for the specially treated coins. You cannot fail to notice that this method should be able to handle thirteen coins. However, to maintain the same number of coins per pan, we need a coin guaranteed to be good. The table below takes care of this situation with G representing the known good coin.
 Incidentally, I found essentially the same proof in five other sources. Brian D. Bundy published his proof in Mathematical Spectrum, while Donald Newman contributed his to David Gale's column in the Mathematical Intelligencer. John Conway discussed a variant he found in Dan Pedoe's book in an online forum. So here is the same proof in 4 guises by 5 people with slightly different motivations. Noteworthy is the fact that each of the five made a step beyond finding a solution to the 12 coins problem. W. McWorter as we saw, expanded his approach to a 13 coin collection. Brian Bundy generalized the problem to an arbitrary number of weighings, as did John Conway and Dan Pedoe. (Don Greenwell prepared a Java demonstration for the case of 4 weighings.) Donald Newman looked into other problems that could be solved in a similar manner. An absolutely beautiful solution of a completely different sort has been sent by Jack Wert.
Copyright © 1996-2008 Alexander Bogomolny |
| 28774848 |  |
|