\problemdata       % Takes 5 *mandatory* arguments
        {pigeonhole-3}             % latex-friendly label for the prob.
        {generalizedpigeonhole}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {F00 Practice Final-4;} % Usage (list ones you are aware of).
        {Jack Kwok, S02}        % Last revision info (author, date).

\begin{problem} \textbf{Mall Mania}

For their annual convention, the members of the MIT Antisocial League
rent out the cafeteria at the CambridgeSide Galleria.  The cafeteria
is an $n\times n$ grid of cells, each cell containing exactly one
table and a \textit{single} associated chair.  A chair can be
positioned around its table to face in one of four directions,
corresponding to the axes of the grid.

Due to space considerations, every attendee must sit at a chair.  But,
since this is the Antisocial League, no seated person can directly
face another occupied table (i.e., there can be no one sitting at a
table in a person's direct line of sight).  Use the pigeonhole
principle to prove that this requirement cannot be satisfied if $4n+1$
members attend.

\solution{
  We use the pigeonhole principle to prove the theorem.
  Orient a representation of the grid in some canonical way with one
  axis pointing left-right, and the other pointing up-down.
  
  There are four directions in which people can face.  As a result, by
  the generalized pigeonhole principle, at least $n+1$ people must be
  facing in some direction.  Without loss of generality, assume this
  is downwards.
  
  Create $n$ pigeonholes from the columns of the grid.  By the PP, if
  there are $n+1$ attendees facing downwards, at least two must be in
  the same column, so clearly one must be directly facing another
  occupied table.
  
  It is likely that equality is not achieved (which would be proved by
  demonstrating an arrangement of $4n$ people in which no one directly
  faced another occupied table).  This suggests a stronger theorem can
  be proven.  The best we can do so far is $4n-4$; try to figure out
  such a solution.}

\end{problem}