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
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 ( email@example.com) 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 firstname.lastname@example.org.