Communications of the ACM
Last byte
Puzzled: Solutions and Sources
This lovely puzzle was from a Russian competition and included in The USSR Problem Book by D.O. Shklarsky et al., W.H. Freeman and Co., San Francisco, 1962. We wanted to show that if 13 coins have the property that any 12 of them can be divided into two stacks of six coins each that balance on the scale, then all the coins would have the same weight.
Now suppose the weights are not all the same. If the weights are all integers, we can reach the following contradiction: Shift the weights down (does not affect either the weighing property or the conclusion) so the lightest coin has weight 0. Now keep dividing all the weights by two until there is a coin of odd weight. If we leave the odd-weight coin behind, the sum of the weights of the other coins must be even, since we can balance them. However, the same must be true if we leave the weightless coin behind, which is impossible.
This argument also works if all the weights are rational numbers, since we can change units so the weights are integers. If the weights are irrational, we would be tempted to replace each weight with a nearby rational number, then proceed as above. Annoyingly, however, the contradiction we arrived at earlier does not materialize in the presence of approximations. Instead, we express the real numbers as a vector space over the rationals; the rest we leave to the intrepid reader.
2. Three weighings
This puzzle was brought to my attention by Noga Alon of Tel Aviv University, and much more about it can be found in the article "Coins and Cones" by Dmitry Kozlov and Van Vu in the Journal of Combinatorial Theory (Series A) 78, 1 (1997), 114. The problem was to determine whether, in three weighings, eight coins with at most two different weights actually all weigh the same. We can handle 2n coins in n steps, in particular eight coins in three steps, by first dividing the coins into two equal stacks; assuming they balance, now divide one of the stacks into two equal stacks and weigh them, then repeat. If there are coins of two weights, then one of these weighings must fail to balance.
3. Vectors that sum to zero.
For years mathematicians thought the algorithm just outlined is optimal; that is, that no more than 2n coins can be handled by n weighings. Kozlov and Vu found a beautiful way to look at the problem using sets of vectors that sum to zero; for other applications of such sets, see the "Puzzled" column "Find the Magic Set" (Aug. 2012). Among other things, their work uncovered counterexamples to the previous view; in particular, the following way to do 10 coins in three weighings: 1, 2, 3, 4, 5 vs. 6, 7, 8, 9, 10; 1, 2, 3, 4 vs. 5, 6, 7, 8; and 6, 7, 8 vs. 5, 9, 10.
Give yourself a pat on the back if you solved this puzzle, with or without mathematical machinery.
Footnotes
All readers are encouraged to submit prospective puzzles for future columns to [email protected].
©2012 ACM 0001-0782/12/12
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from [email protected] or fax (212) 869-0481.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2012 ACM, Inc.
No entries found