solutions and sources
Last month (November 2012) we posted a trio
of brainteasers concerning the use of a balance scale
to determine the weight of various numbers of coins.
Here, we offer solutions to all three. How did you do?
1.same weight. This lovely puzzle was from a
Russian competition and included in
The USSR Problem Book by D.O. Shklar-sky 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 vec-
tor 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),
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 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
All readers are encouraged to submit prospective
puzzles for future columns to email@example.com.
Peter Winkler ( firstname.lastname@example.org) is William morrill
Professor of mathematics and Computer Science,
at dartmouth College, Hanover, NH.