Opinion
Computing Applications Last byte

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.
Posted
  1. Author
  2. Footnotes
Peter Winkler scrambled
ACM Digital Library

Communications of the ACM
Volume 55, Number 8 (2012), Pages 120-120
Last byte: Puzzled
Peter Winkler
DOI: 10.1145/2240236.2240263

Table of Contents

back to top  

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

Back to Top

Back to Top

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More