\problemdata      
        {functions-relations-7} % latex-friendly label for the prob.
        {Dilworth's theorem} % The topic(s) of the problem content.
        {Karger tutorial spring 01} % Source (if known)
        {S02 cp3F, F00 pset} % Usage (list ones you are aware of).
        {Radhika Nagpal, S02} % Last revision info (author, date).


\begin{problem}
At last count, our 6.042 session contained approximately 60 students.
Prove that the class must contain either: 

\begin{enumerate} 
\item A set $S$ of 7 students such that, if they line up according to
increasing height, they are also arranged in increasing order of age,
or

\item a set $T$ of 7 students such that, if they line up according to
increasing height, they are also arranged in decreasing order of age.
\end{enumerate}

To eliminate some confusion: the sequence $\{2, 2, 3, 4\}$ is in
increasing order, but not in strictly increasing order.

\solution{
For each student, we can assign a pair $(s,a)$ where $s$ represents
the size (height) of the student and $a$ represents the age of the
student. We then get a set $U$ of 60 such pairs. We can define the
following binary relation $R$, denoted by $\preceq$, between two pairs
$P_{1}$ and $P_{2}$: $P_{1}\preceq P_{2}$ iff $s_{1}\leq s_{2}$ and
$a_{1}\leq a_{2}$.

For example, if $P_{1}=(60, 20)$, $P_{2} = (60, 21)$, $P_{3}= (65,
19)$, we have $P_{1}\preceq P_{2}$ but $P_{3}$ and $P_{1}$ are
incomparable.

It is easy to check that $R$ is reflexive, transitive and
antisymmetric. Thus, it defines a partial order on the set $U$. By
Dilworth's Theorem, since $U$ has 60 elements, it must either have a
chain of size$>7$ or an antichain of size $\geq \frac{60}{7}$.

\subparagraph{Case 1}
$U$ has a chain of size $> 7$. Then it has a chain of size at least
7. This means that we can find 7 pairs which satisfy the relation
$P_{1}\preceq P_{2}\preceq P_{3}\ldots \preceq P_{7}$. From the
definition of our binary relation $(\preceq)$, this implies that
$s_{1}\leq s_{2}\leq s_{3}\leq \ldots \leq s_{7}$ AND $a_{1} \leq
a_{2} \leq a_{3}\leq\ldots\leq a_{7}$. Therefore, if we place the
corresponding 7 students in the same order, they will be lined up in
in increasing order of size AND in increasing order of age.

\subparagraph{Case 2} 
$U$ has an antichain of size $\geq\frac{60}{7}$, so, since
antichains only come in integer lengths, it has an antichain of size
at least 8. Therefore, we can find 8 pairs which are
incomparable. We can line them up in order of increasing size
(ignoring age), and come up with an order $P_{1}\ldots P_{8}$ so that
$s_{i} \leq s_{i+1} (i= 1\ldots 12)$. Since for all $i$, $s_{i}\leq
s_{i+1}$ and $P_{i}, P_{i+1}$ are incomparable, we can conclude that
$a_{i}> a_{i+1}$ (because if not, $a_{i}\leq a_{i+1}$ so for that $i$,
$s_{i}\leq s_{i+1},$ $a_{i}\leq a_{i+1}$, therefore $P_{i}\preceq
P_{i+1}$, so $P_{i}$ and $P_{i+1}$ would NOT be incomparable.) If we
take the students corresponding to $P_{1}\ldots P_{8}$ and line them
up in that order, they will be in increasing order of size (since
$s_{i}\leq s_{i+1}$) and in decreasing order of age (since we
established that $a_{i}>a_{i+1}$).

} % end solution
\end{problem} 
