last byte

DOI: 10.1145/1897852.1897878
Peter Winkler
Puzzled
solutions and sources
Last month (February 2011, p. 112) we posted a trio of brainteasers, including
one as yet unsolved, concerning partitions of Ms. Feldman’s fifth-grade class.
Here, we offer solutions to at least two of them. How did you do?

1. Monday, tuesday. Solution. Recall that on Monday, Ms. Feldman partitioned her class into k subsets and on Tuesday repartitioned the same students into k+ 1 subsets. We were asked to show that at least two students were in smaller subsets on Tuesday than they were on Monday.

It turns out that a nice way to see this is to consider how much work each student contributed to his or her assigned project. Assume that all projects (both days) were equally demanding, with each requiring a total of one unit of effort. Assume, too, that the work was divided perfectly equitably, so a student in a subset of size m contributed 1/m units of effort. The total effort contributed on Monday was, of course, k and on Tuesday k+ 1, so some students must have contributed more of their effort on Tuesday than on Monday. But no individual student could have made up the full unit difference; the difference between 1/m and 1/n is less than 1 for any positive integers m and n. At least two students thus put in more effort on Tuesday and were therefore in smaller groups the second day.

This surprisingly tricky puzzle was brought to my attention by Ori Gurel-Gurevich of the University of British Columbia; it had appeared in the 1990 Australian Mathematics Olympiad.

2.unfriendly Partitions. Solution. A partition of the kind Ms. Feldman wants, into two subsets, such that no student has more than half his/her friends in that student’s own group, is called an “ unfriendly partition.” To see that an unfriendly partition exists, consider, for any partition, the number of broken friendships; that is, the number of pairs of friendly students who have been separated. Now choose a partition that maximizes this number; it must be unfriendly. Why? Because if student X has more friends in his/her subset than in the other subset, moving X from one to the other subset would yield a partition with more broken friendships.

3.countably infinite Graphs. Unsolved. On Friday, when the class suddenly has a countably infinite number of students, Ms. Feldman can no longer apply these arguments to show that an unfriendly partition exists. The difficulty is that now there may be no partition with the maximum number of broken friendships. Moreover, even if there is a partition that breaks infinitely many friendships, the argument fails because switching student X as in Solution 2 doesn’t give a contradiction.

Amazingly, no substitute argument has been found, nor has anyone come up with an example where no unfriendly partition exists. For (much) more information, see the marvelous article by Saharon Shelah and the late Eric Milnor, “Graphs with No Unfriendly Partitions,” in A Tribute to Paul Erdős, A. Baker, B. Bollobás, and A. Hajnal, Eds., Cambridge University Press, 1990, 373– 384. Shelah and Milnor constructed an “uncountable” graph with no unfriendly partitions; they also showed that every graph has an unfriendly partition divided into three subsets. The case of countably infinite graphs, when seeking to divide an unfriendly partition into two subsets, remains tantalizingly open—until, perhaps, you solve it.

 

Peter Winkler ( [e-mail]) is Professor of mathematics and of Computer science and albert bradley third Century Professor in the sciences at Dartmouth College, hanover, nh.

All readers are encouraged to submit prospective puzzles for future columns to [e-mail].