Puzzled: Parsing Partitions

Welcome to three new puzzles. Solutions to the first two will be published next month; the third is (as yet) unsolved. In each, the issue is how your intuition matches up with the mathematics.

By Peter Winkler

Posted Feb 1 2011

The theme is partitions. Recall from freshman year that a set A is a subset of a set B if every element of A is also in B. A partition of a set S is a collection of subsets of S such that every element of S is in exactly one of the subsets in the collection. Pretty basic, right? But "basic" is not the same as "easy." Try proving the following reasonable-looking statements about partitions of a fifth-grade class.

On Monday, Ms. Feldman partitioned her fifth-grade class into k subsets (of various sizes) to work on different projects. On Tuesday, she repartitioned the same students into k+1 subsets. Show that at least two students were in smaller subsets on Tuesday than they were on Monday.
On Wednesday, Ms. Feldman divided her class into just two parts, but a little too much socialization emerged in each of them, distracting the students from the work at hand. The next day (Thursday) she is again determined to partition the class into two subsets but this time in such a way that no student has more than half of his/her own friends in his/her own subset. Show that such a partition always exists.
Now it’s Friday, and all other fifth-grade teachers are out sick. This means Ms. Feldman is in charge of the entire fifth grade, which, to her consternation, has (countably) infinitely many students. Persevering, she is again determined to partition the students into two subsets in such a way that no student has more friends in his/her own subset than in the other subset.

Is it guaranteed that no matter how the friendships are structured there is always a way to do this?

In Puzzles 2 and 3, we assumed that friendship is a symmetric relation; that is, if student X is a friend of student Y, then the reverse is true as well. In Puzzle 3, some students may have infinitely many friends; it is OK if such a student has infinitely many friends in his/her own subset, provided infinitely many friends are also in the other subset. So it shouldn’t be difficult to find a partition with the desired property. Right? So why can’t anyone prove it?