# Puzzled: Solutions and Sources

By Peter Winkler

Communications of the ACM, Vol. 55 No. 9, Page 117
10.1145/2330667.2330692

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 n1. 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 n1 possible differences (the numbers 1 through n1), 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 [email protected].

### Author

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