Communications of the ACM

Last byte

Puzzled: Solutions and Sources

By Peter Winkler
Communications of the ACM, September 2012, Vol. 55 No. 9, Page 117
10.1145/2330667.2330692
Comments

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.

Solution. This beauty, first communicated to me by Noga Alon of Tel Aviv University, was submitted to Math Overflow (http://mathoverflow.net) by Ehud Friedgut of Hebrew University and solved by Alon Amit of Google. Recall that your list of the 1,024 plus-minus-one vectors of length 10 was altered by changing some entries to zeroes and you had to find a set of altered vectors that sum to the zero vector. The trick is to make a list of altered vectors whose partial sums are all 0,1 vectors. How do you do this? Start with the vector that, before altering, was all ones; maybe it now looks like (1,1,0,1,1,1,0,0,1,1). Now add the vector that, before altering, had minus ones where your current partial sum has ones and plus ones where you currently have a zero. In this case, it would be the vector (–1,–1,1,–1,–1,–1,1,1,–1,– 1) that perhaps was altered to (0,–1,1,– 1,0,0,0,1,–1,0). If so, your new partial sum would be (1,0,1,0,1,1,0,1,0,1), and you would next add the vector that started life as (–1,1,–1,1,–1,–1,1,–1,1,– 1). Eventually, you would be called on to use the same vector twice, but that would mean you had the same partial sum twice, so the vectors in between would add up to (0,0,0,0,0,0,0,0,0,0). This elegant argument works with vectors of any fixed length. Moreover, you can easily verify that if any one vector was left off the original list, and the right zeroes were crayoned in, there would be no "magic set."

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

Back to Top

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

---

No entries found