\problemdata                                                             
        {Lining ppl by age/height} % latex-friendly label for the prob.
        {Dilworth} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 4, 4} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
At last count, our 6.042 class contains 180 students.
Prove that the class must contain either: \begin{enumerate} \setlength{\itemsep}{0pt} %\setlength{\itemsep}{0cm}
\item A set $S$ of 15 students such that, if they line up in size
places, they are also arranged in increasing order of age,
or
\item a set $T$ of 13 students such that, if they line up in size
places, 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 180 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}=(180, 20)$, $P_{2} = (180, 21)$, $P_{3}= (185, 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 180 elements, it must either have a chain of size$>14$ or an antichain of size $\geq \frac{180}{14}$. 
\subparagraph{Case 1} $U$ has a chain of size $> 14$. Then it has a chain of size at least 15. This means that we can find 15 pairs which satisfy the relation $P_{1}\preceq P_{2}\preceq P_{3}\ldots \preceq P_{15}$. From the definition of our binary relation $(\preceq)$, this implies that $s_{1}\leq s_{2}\leq s_{3}\leq \ldots \leq s_{15}$ AND $a_{1} \leq a_{2} \leq a_{3}\leq\ldots\leq a_{15}$. Therefore, if we place the corresponding 15 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{180}{14}$, so, since antichains only come in integer lengths, it has an antichain of size at least 13. Therefore, we can find 13 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_{13}$ 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_{13}$ 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{problem}

                                 