Communications of the ACM
Puzzled: Solutions and Sources
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.
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, 373384. 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 openuntil, perhaps, you solve it.
Footnotes
All readers are encouraged to submit prospective puzzles for future columns to [email protected].
©2011 ACM 0001-0782/11/0300 $10.00
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from [email protected] or fax (212) 869-0481.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2011 ACM, Inc.