Home → Magazine Archive → August 2012 (Vol. 55, No. 8) → Puzzled: Find the Magic Set → Full Text

Puzzled: Find the Magic Set

By Peter Winkler

Communications of the ACM, Vol. 55 No. 8, Page 120
10.1145/2240236.2240263

[article image]

Save PDF
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

Author

Peter Winkler ([email protected]) is William Morrill Professor of Mathematics and Computer Science at Dartmouth College, Hanover, NH.

Back to Top

Footnotes

Readers are encouraged to submit prospective puzzles for future columns to [email protected].


©2012 ACM  0001-0782/12/0800  $10.00

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from [email protected] or fax (212) 869-0481.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2012 ACM, Inc.