Problem:
a school class of children is taking several group pictures. For every group with at least one child, there is exactly one picture containing this specific group. The pictures are now hung up in different rooms in the school, such that every child appears in at most one photo per room.
a. Show that this is possible if the school has rooms.
b. Show that this is not possible if the school has less than rooms.
Solution:
a.
One way of doing this is to pair each photo with its complement and put the photo with all children in a room by itself. Indeed, this is the only way (see appendix).
b.
The simplest way of doing this is to provide a set of photos, of which no two are disjoint. There are many ways of doing so (taking all the photos containing a given child is one example, amongst many others) and these all provide the desired proof, as all these photos have to be in different rooms.
Otherwise, a more general counting argument also suffices: as at most kids appear per room, and there must be appearances in total, we need at least rooms.