2011:12: December Conundrum: Stuffing the Trunk

It’s that time of year again!  You’ve blown your savings on the holiday shopping, having purchased a total of 7 gifts for the relatives who will make an appearance during the winter break.  You’ve made it through the exam and final paper push–all that remains is to pack the car and hit the road for a well-deserved break.  Since you’re sharing a ride to the airport with your suitemate, who drives a ’99 Honda Civic and tends to overpack, you knew trunk space would be tight.  You overstuffed your belly during Thanksgiving, and now you have to overstuff the trunk of this car to make it home for yet another holiday extravaganza.  However, you cleverly anticipated this problem by using gift bags this year instead of wrapping gift boxes.  As you prepare to pack the trunk as efficiently as possible, prove that amongst your 7 gift bags there must be either 3 gift bags that will fit one inside the other, or 4 gift bags amongst which none fits inside any other.

Solution:

The key is to think about the seven gift bags as elements in a partially ordered set: to say that bag A fits inside bag B means that A < B, and if neither bag A fits in bag B nor bag B fits in bag A, then there is no comparison between them.  You can represent the seven elements as vertices in a graph, putting an edge from A to B whenever there is a comparison A < B.  If you assume that there do not exist 3 bags which fit one inside the other, then this graph is bipartite, with one collection of bags into which some bags fit and another collection of bags which fit inside larger bags.  Here is an example:

The green vertices represent bags which fit into the bags represented by red vertices, whenever there is an edge.  Observe that if there is no chain of three bags A, B, C such that A < B < C, then there must be exactly two “colors” of vertices.  The only ways to group 7 vertices into two colored collections would color at least 4 vertices the same color, say red.  The bags corresponding to the red vertices necessarily form an “anti-chain” (a collection among which there are no relations whatsoever) since we are assuming that there is no chain of three bags which fit one inside the other.   (You might be interested to know that this is an application of Dilworth’s Theorem!)