Communications of the ACM

Table of Contents

• Author
• Footnotes

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).