Communications of the ACM
Last byte
Puzzled: Parsing Partitions
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?
Footnotes
All readers are encouraged to submit prospective puzzles for future columns to [email protected].
DOI: http://doi.acm.org/10.1145/1897816.1897845
©2011 ACM 0001-0782/11/0200 $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.
No entries found