2010:10: October Conundrum: Calling the Great Pumpkin

Each year, the Great Pumpkin rises out of the pumpkin patch that he thinks is the most sincere.  Well, what could be more sincere than a community garden?  Your entry has planted a community pumpkin patch, and each of you is responsible for caring for all of the pumpkins in some rectangular portion of the patch.  (All sides of these rectangular regions run either north-south or east-west.)  To guarantee that you have at least a few healthy pumpkins in the crop, these rectangular regions are organized so that given any two students, there is at least one pumpkin which both students must water.  Prove that there is then at least one pumpkin in the patch which should get watered by every single member of the entry!

He’s gotta pick this one.  He’s got to!  I don’t see how a pumpkin patch can be more sincere than this one.

Congratulations to Daniel Phelps for submitting a correct solution to this month’s puzzle!

Solution:

Draw the rectangular regions in the plane, and consider the projections of the east-west sides onto the x-axis.  This projection results in a collection of closed intervals, say [a_i, b_i], on the real line.   Consider the maximum of all of the a_i and the minimum of all of the b_i, which we denote by a_max and b_min.  Then the intervals [a_max, b_j] and [a_k, b_min] share a common interval (corresponding to the projection of their common pumpkin) by hypothesis.  Now, since all other a values lie to the left of a_max and all other b values to the right of b_min, this common interval also lies in every other interval [a_i, b_i].  Similarly, projecting the north-south sides of the regions onto the y-axis yields a in interval which is common amongst these projections, corresponding to the projection of a pumpkin that must then be common to all of these intervals.  The preimage of these two common intervals on the x- and y-axes contains a pumpkin that is scheduled to be watered by all entry members.  (You might be interested to know that this question is a reformulation of the one-dimensional version of a more general result called Helley’s Theorem!)