last byte
DOI: 10.1145/2240236.2240263
Peter Winkler
Puzzled
Find the Magic Set
Welcome to three new puzzles. Each involves a collection of items, and your job is to find
a subset of them that is characterized by a particular property. Since solving the puzzles
is not easy, here are a couple of hints: For the first, think about averages; for the other two,
try constructing your sets sequentially, bearing in mind that if two partial sums are equal,
the terms between them must add up to zero.
1.A balance scale sits on
a teacher’s desk,
currently tipped to the
right. A set of weights
is on the scales, and
on each weight is
the name of at least
one student. Class
is about to begin,
and on entering the
classroom, each
student moves each
weight carrying his
or her name to the
opposite side of the
scale. Now show there
is a set of pupils that
you, the teacher, can
let in the classroom
that will tip the scales
to the left.
2.You have two sets (blue
and red) of n n-sided
dice, with each die
labeled with the
numbers 1 to n.
You roll all 2n dice
simultaneously.
Now find a nonempty
subset of the red
dice and a nonempty
subset of the blue dice
with the same sum.
3.You begin with a list of
all 1,024 possible
vectors of length 10
with entries + 1 or – 1.
Your crayon-wielding
three-year-old child
has got hold of the
list and unfortunately
changed some of the
entries in some of
the vectors to zeroes.
Now find a non-empty
subset of the altered
vectors that add up
to the all-zero vector
(0,0,0,0,0,0,0,0,0,0).
Readers are encouraged to submit prospective puzzles for future columns to puzzled@cacm.acm.org.
Peter Winkler ( puzzled@cacm.acm.org) is William morrill professor of mathematics and Computer science
at Dartmouth College, hanover, nh.
