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.

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), 1–14. 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 2ⁿ 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 2ⁿ 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

Back to Top