Sign In

Communications of the ACM

Last byte

Puzzled: Solutions and Sources


View as: Print Mobile App ACM Digital Library Full Text (PDF) In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
Dartmouth College Professor of Mathematics and of Computer Science Peter Winkler

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.

Back to Top

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.

Back to Top

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.

Back to Top

Author

Peter Winkler (puzzled@cacm.acm.org) is William Morrill Professor of Mathematics and Computer Science, at Dartmouth College, Hanover, NH.

Back to Top

Footnotes

All readers are encouraged to submit prospective puzzles for future columns to puzzled@cacm.acm.org.


©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 permissions@acm.org or fax (212) 869-0481.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2012 ACM, Inc.


 

No entries found