Last byte

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. 1. Monday, Tuesday.
  2. 2. Unfriendly Partitions.
  3. 3. Countably Infinite Graphs.
  4. Author
  5. Footnotes

Solution. Recall that on Monday, Ms. Feldman partitioned her class into k+1 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.

Back to Top

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.

Back to Top

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 cacm5403_d.gif 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.

Back to Top

Back to Top

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

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.

Learn More