Opinion
Last byte

# Puzzled: Solutions and Sources

Last month (August 2012) we posted a trio of brainteasers concerning "magic sets." Here, we offer solutions to all three. How did you do?
Posted

1. Tipping the scales.

Solution. A balance scale carrying weights, currently tipped to the right, sits on a teacher’s desk. Each time a student enters the classroom, the weights labeled with his or her name switch sides. You were asked to find a set of students that, if admitted to the classroom, would tip the scales to the left.

Consider all subsets of students, including the empty set and the full set. Each weight would end up on the left half the time, so the total weight on the left for all these subsets would be the same as the total weight on the right. Since the empty set results in a tip to the right, some other set must tip to the left. (Source: Second All Soviet Union Mathematical Competition, Leningrad, 1968.)

2. Tumbling dice.

Solution. David Kempe of the University of Southern California, who brought me this puzzle, needed the result for a computer science paper. As it turned out, variations of Kempe’s problem had been solved earlier by notable mathematicians Persi Diaconis of Stanford University, Ron Graham of the University of California, San Diego, and Bernd Sturmfels of the University of California, Berkeley. Assume the red dice are the ones with the greater (or equal) sum and organize them into a horizontal line in any order you want, and do the same with the blue dice, below the reds. Now draw n slanted (or vertical) lines such that each red die has one line immediately to its right, and the sum of the red dice to the left of any line minus the sum of the blue dice to the left of the same line is always between 0 and n−1. These lines can be drawn in left-to-right order. If any of the differences is 0, the red and blue sets to the left of that line are just what the doctor ordered. Otherwise, since there are n lines and only n−1 possible differences (the numbers 1 through n−1), two lines must have the same difference. The red and blue sets between the two lines do the trick.

3. Summing to the all-zero vector.

All readers are encouraged to submit prospective puzzles for future columns to puzzled@cacm.acm.org.

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