Let
\(\sigma=(x_1,x_2,x_3,\dots,x_{mn+1})\) be a sequence of
\(mn+1\) distinct real numbers. For each
\(i=1,2,\dots,mn+1\text{,}\) let
\(a_i\) be the maximum number of terms in a increasing subsequence of
\(\sigma\) with
\(x_i\) the first term. Also, let
\(b_i\) be the maximum number of terms in a decreasing subsequence of
\(\sigma\) with
\(x_i\) the last term. If there is some
\(i\) for which
\(a_i\ge m+1\text{,}\) then
\(\sigma\) has an increasing subsequence of
\(m+1\) terms. Conversely, if for some
\(i\text{,}\) we have
\(b_i\ge n+1\text{,}\) then we conclude that
\(\sigma\) has a decreasing subsequence of
\(n+1\) terms.
It remains to consider the case where
\(a_i\le m\) and
\(b_i\le n\) for all
\(i=1,2,\dots,mn+1\text{.}\) Since there are
\(mn\) ordered pairs of the form
\((a,b)\) where
\(1\le a\le m\) and
\(1\le b\le n\text{,}\) we conclude from the Pigeon Hole principle that there must be integers
\(i_1\) and
\(i_2\) with
\(1\le i_1\lt i_2\le mn+1\) for which
\((a_{i_1},b_{i_1})=(a_{i_2},b_{i_2})\text{.}\) Since
\(x_{i_1}\) and
\(x_{i_2}\) are distinct, we either have
\(x_{i_1}\lt x_{i_2}\) or
\(x_{i_1}>x_{i_2}\text{.}\) In the first case, any increasing subsequence with
\(x_{i_2}\) as its first term can be extended by prepending
\(x_{i_1}\) at the start. This shows that
\(a_{i_1}>a_{i_2}\text{.}\) In the second case, any decreasing sequence of with
\(x_{i_1}\) as its last element can be extended by adding
\(x_{i_2}\) at the very end. This shows
\(b_{i_2}>b_{i_1}\text{.}\)